Counting anticommuting Pauli pairs in linear time

Resumo Técnico: Contagem de Pares de Pauli Anticomutantes em Tempo Linear

Formulação do Problema
O artigo aborda um sub-rotina clássica fundamental necessária em fluxos de trabalho de computação quântica: processar uma lista de $m$ strings de Pauli esparsas de $n$ qubits, $P^{(1)}, \dots, P^{(m)}$, onde cada string possui um peso (localidade) limitado $k$ (ou seja, age de forma não trivial em no máximo $k$ qubits). O objetivo é determinar as propriedades de comutação par a par dessas strings. Especificamente, o algoritmo deve realizar uma das três tarefas:

1. Contagem Exata: Calcular o número preciso de pares não ordenados anticomutantes $\{i, j\}$ tais que $P^{(i)}P^{(j)} = -P^{(j)}P^{(i)}$.
2. Certificação: Verificar se todas as strings no conjunto comutam par a par.
3. Encontrar Testemunha: Se nem todas as strings comutam, identificar um par específico $(i, j)$ que anticomuta.

A abordagem padrão representa strings de Pauli na forma simplética binária e verifica cada par, resultando em uma complexidade de tempo de $O(m^2)$ (ou $O(m^2 k)$ para strings esparsas). Embora listar todas as arestas anticomutantes em um grafo denso inerentemente exija tempo $\Omega(m^2)$, os autores observam que a contagem exata e a certificação frequentemente exigem apenas saídas de tamanho constante ou logarítmico, sugerindo o potencial para melhoria sub-quadrática.

Metodologia: O Algoritmo Zeta de Localidade
Os autores propõem um algoritmo que opera em tempo $O(m)$ para $k$ fixo, deslocando o paradigma da comparação par a par para a agregação de padrões. O núcleo do método é uma estrutura de dados chamada estrutura de dados zeta de localidade, que mantém contagens de subpadrões rotulados de strings previamente inseridas.

1. Definição de Padrão: Um padrão de Pauli rotulado é um par $(A, a)$, onde $A$ é um subconjunto de posições de qubits e $a$ atribui uma letra de Pauli não identidade ($X, Y, Z$) a cada posição em $A$.
2. Inserção: Quando uma nova string de Pauli $Q$ é inserida, o algoritmo enumera todos os subconjuntos $A \subseteq \text{supp}(Q)$ e incrementa a contagem para o padrão $(A, Q|_A)$ em um dicionário. Para uma string de peso $w$, isso envolve $2^w$ atualizações.
3. Consulta via Identidade Zeta de Subconjuntos: Para consultar uma nova string $P$ contra o conjunto de strings previamente inseridas $G$, o algoritmo calcula uma soma ponderada sobre todos os subconjuntos $A \subseteq \text{supp}(P)$.
   • Calcula $F_G(P, A)$, o número de strings em $G$ que conflitam com $P$ em cada coordenada em $A$.
   • Calcula uma "soma zeta" $Z_G(P) = \sum_{A \subseteq \text{supp}(P)} (-2)^{|A|} F_G(P, A)$.
   • O número de strings anticomutantes é derivado como $\text{anti}_G(P) = (|G| - Z_G(P)) / 2$.

A correção baseia-se no princípio da inclusão-exclusão (especificamente uma identidade zeta de subconjuntos) para isolar a paridade do tamanho do conjunto de conflitos. Se o tamanho do conjunto de conflitos $|\text{conf}(P, Q)|$ for ímpar, os termos na soma se cancelam para resultar em $-1$; se par, somam-se a $+1$.

Contribuições e Resultados Chave

• Complexidade de Tempo Linear: O artigo apresenta um algoritmo com complexidade de tempo esperada de $O(\sum_{i=1}^m w_i 3^{w_i})$, onde $w_i$ é o peso da $i$-ésima string. Para o regime de localidade limitada onde $w_i \leq k$ para todo $i$, a complexidade é $O(m k 3^k)$. Como $k$ é tratado como uma constante fixa, o algoritmo executa em tempo linear $O(m)$ em relação ao número de strings $m$.
• Complexidade de Espaço: O algoritmo requer espaço $O(\sum_{i=1}^m w_i 2^{w_i})$ para as chaves do dicionário, o que se simplifica para $O(m k 2^k)$ para localidade limitada.
• Optimalidade: Os autores afirmam que, para $k$ fixo no modelo de entrada esparsa, este algoritmo é ótimo até um fator constante dependendo de $k$.
• Encontrar Testemunha: O algoritmo pode ser estendido para retornar um par de testemunha específico $(i, j)$ se existir. Embora as etapas de contagem e certificação sejam lineares, encontrar a testemunha específica envolve uma varredura das strings anteriores, adicionando um custo de $O(mk)$, o que permanece eficiente em comparação com a linha de base de $O(m^2)$.

Significado e Alegações
O artigo posiciona este trabalho como uma solução para o "problema de agrupamento" em software quântico, onde muitos pares de strings de Pauli devem ser filtrados ou conjuntos comutantes candidatos verificados. Os autores argumentam que, embora a saída densa (listar todas as arestas) seja inerentemente quadrática, muitas etapas de verificação em algoritmos quânticos — como redução de medição em solucionadores variacionais de autovalores quânticos (VQE), computação baseada em Pauli e fluxos de trabalho de Hamiltonianos locais — exigem apenas contagem ou certificação.

O significado reside em transformar um problema de grafo par a par em um problema de contagem de padrões. Ao agregar subpadrões locais e usar a identidade zeta de subconjuntos, o algoritmo evita o gargalo quadrático da abordagem simplética binária padrão. Os autores concluem que este método é instrumental para escalar as sub-rotinas clássicas necessárias para simulação quântica de alto desempenho e mitigação de erros, particularmente em fluxos de trabalho envolvendo grandes coleções de strings de Pauli esparsas e locais. O artigo não propõe novo hardware experimental ou aplicações futuras específicas além dessas sub-rotinas clássicas, mas enfatiza o ganho de eficiência algorítmica para pilhas de software quântico existentes.