An efficient Pauli decomposition algorithm for structured matrices

Resumo Técnico: Um Algoritmo Eficiente de Decomposição de Pauli para Matrizes Estruturadas

Enunciado do Problema
A decomposição de matrizes clássicas de $2^n \times 2^n$ em combinações lineares de strings de Pauli é um gargalo crítico para implementações de ponta a ponta de algoritmos quânticos de curto prazo (near-term), particularmente em química, aprendizado de máquina e finanças. Muitos algoritmos, como o VQE (Variational Quantum Eigensolver) e resolvedores de álgebra linear, assumem que os dados de entrada são fornecidos como uma Combinação Linear de Unitários (LCU) de strings de Pauli. No entanto, para matrizes gerais especificadas classicamente, essa decomposição não é conhecida a priori.

Algoritmos existentes para matrizes densas genéricas escalam exponencialmente com o número de qubits $n$. A abordagem mais direta requer $O(32^n)$ de tempo, enquanto os melhores métodos conhecidos atualmente (por exemplo, no PennyLane) escalam como $O(n4^n)$. Esse custo exponencial surge porque, no pior caso, uma matriz possui suporte em todas as $4^n$ bases de Pauli, exigindo a recuperação de todos os coeficientes.

Este artigo aborda uma versão com promessa (promise version) do problema de decomposição de Pauli. Ele assume que a matriz de entrada $M$ tem a garantia de possuir suporte em apenas $k = \text{poly}(n)$ strings de Pauli. Além disso, a matriz é acessada via um modelo de consulta esparsa clássica, onde um algoritmo pode recuperar as entradas não nulas de uma linha ou coluna específica sem construir a matriz completa de $2^n \times 2^n$ na memória. O objetivo é recuperar a decomposição de Pauli exata (o conjunto de strings de Pauli e seus coeficientes) com alta probabilidade usando recursos polinomiais em $n$, $k$ e $\log(1/\delta)$.

Metodologia
Os autores propõem um algoritmo clássico aleatório que explora a esparsidade prometida ($k$) e a estrutura das strings de Pauli em forma simplética binária. O algoritmo decompõe o problema em três etapas principais:

1. Descoberta das Partes Ativas de Pauli-X ($x$):
   Usando o Lema 1, que relaciona o índice da linha $v$, o índice da coluna $u$ e a parte Pauli-X $x$ via $x = u \oplus v$, o algoritmo consulta linhas aleatórias da matriz. Ao coletar os índices das colunas das entradas não nulas e realizar o XOR com os índices das linhas, o algoritmo identifica o conjunto $X$ de strings de bits $x$ distintas presentes na decomposição. Esta etapa baseia-se no princípio da incerteza booleano (Fato 1) para garantir que consultas aleatórias revelem as strings $x$ ativas com alta probabilidade.

2. Decodificação de Strings $x$ Únicas:
   Para cada $x$ descoberto, o algoritmo verifica se ele é "único" (ou seja, associado a exatamente uma string de Pauli, de modo que $p_x = 1$). Se for único, a função de consulta $b_x(u) = M_{x \oplus u, u}$ reduz-se a um único caractere de Walsh $\beta_x(z)(-1)^{z \cdot u}$. O algoritmo recupera a parte Pauli-Z $z$ associada e o coeficiente $\beta$ avaliando $b_x$ no vetor zero e em vetores da base padrão. Uma etapa de certificação usando entradas aleatórias verifica se a solução candidata não é um caso degenerado que coincida acidentalmente com os pontos consultados.

3. Decodificação de Strings $x$ Degeneradas:
   Se um $x$ for "degenerado" (associado a $p_x \geq 2$ strings de Pauli), o problema reduz-se à recuperação de um espectro de Walsh-Hadamard esparso. O algoritmo emprega uma técnica de dobramento aleatório (random folding):

   • Ele mapeia os índices espectrais de $n$ bits ($z$) em compartimentos (bins) de $m$ bits usando uma matriz binária aleatória $R$, onde $m \ll n$.
   • Este "dobramento" isola strings $z$ individuais em "compartimentos de elemento único" (singleton bins) com alta probabilidade.
   • Para um compartimento de elemento único, o algoritmo utiliza consultas deslocadas para determinar os bits da string $z$ e seu coeficiente.
   • Os termos recuperados são subtraídos da função residual, e o processo se repete até que todos os termos para aquele $x$ sejam encontrados.
   • Uma verificação aleatória final garante que nenhum termo foi perdido.

Principais Contribuições

• Design do Algoritmo: O artigo apresenta um algoritmo clássico aleatório (Algoritmo 1) que resolve o problema de decomposição de Pauli sob a promessa de esparsidade $k$ e acesso por consulta esparsa.
• Melhoria de Complexidade: Diferente dos métodos existentes que escalam exponencialmente em $n$, o algoritmo proposto alcança uma complexidade de consulta e de tempo que é polinomial em $n$, $k$ e $\log(1/\delta)$.
• Garantias Teóricas: O algoritmo tem sucesso com probabilidade de pelo menos $1-\delta$ para qualquer $\delta \in (0, 1)$ escolhido pelo usuário. Os autores fornecem limites rigorosos para as probabilidades de falha em cada etapa (descoberta, decodificação única e decodificação degenerada).
• Técnicas de Walsh-Hadamard Esparsas: O trabalho adapta técnicas de recuperação esparsa do cubo booleano (especificamente a decodificação de Walsh-Hadamard esparsa) para o contexto da decomposição de Pauli, utilizando dobramento aleatório e recuperação de bits baseada em deslocamento.

Resultados

• Benchmarks Numéricos: Os autores testaram o algoritmo em instâncias aleatórias para $n = 2$ a $30$ com $k = 2^n$.
  • Para $n$ pequenos ($n < 10$), o overhead do algoritmo aleatório torna-o mais lento que a rotina PauliDecompose existente do PennyLane.
  • Ocorre um ponto de intersecção (crossover) em torno de $n=10$. Para $n > 10$, o algoritmo proposto supera significativamente o baseline de tempo exponencial.
  • O tempo de execução e as contagens de consulta observados escalam polinomialmente com $n$, consistentes com os limites teóricos.
  • Em todas as execuções testadas, o algoritmo recuperou com sucesso a decomposição completa sem falhas.
• Escalabilidade: O algoritmo lidou com sucesso com instâncias de até $n=30$, um regime onde construir a matriz completa ou executar algoritmos de decomposição densa torna-se computacionalmente intratável.

Significância e Alegações
O artigo afirma que, embora encontrar a decomposição de Pauli seja exponencialmente difícil para matrizes gerais, isso se torna eficientemente solucionável para matrizes conhecidas por serem esparsas na base de Pauli. Este regime é altamente relevante para algoritmos quânticos de curto prazo operando sobre dados clássicos estruturados.

Os autores enfatizam que seu algoritmo é projetado especificamente para o problema com promessa onde $k = \text{poly}(n)$. Eles não alegam resolver o caso denso geral. A significância reside em permitir o pré-processamento clássico eficiente para algoritmos quânticos que exigem decomposições de Pauli, potencialmente removendo um grande gargalo nos fluxos de trabalho quânticos de ponta a ponta. O trabalho também destaca contextos de aplicação específicos, como matrizes definidas por regras clássicas sucintas ou dados mantidos por servidores não confiáveis onde apenas o acesso por consulta está disponível.

O artigo conclui de forma modesta, observando que os limites superiores derivados podem ser frouxos e que trabalhos futuros poderão explorar limites mais estreitos, limites inferiores e extensões para matrizes aproximadamente esparsas.