Automorphism-Assisted QAOA: A Classical-Estimator Speedup for QAOA Simulation on Graphs with Non-Trivial Symmetry

Resumo Técnico: AA-QAOA (Automorphism-Assisted QAOA)

Definição do Problema
O Algoritmo de Otimização Aproximada Quântica (QAOA) é uma abordagem híbrida quântico-clássica proeminente para resolver problemas de otimização combinatória NP-difíceis, como o problema MaxCut não ponderado. Um gargalo significativo na pesquisa de QAOA, particularmente para grupos que dependem de simuladores de estado vetorial clássicos devido ao acesso limitado a Unidades de Processamento Quântico (QPUs), é o custo computacional do loop de otimização clássica. Especificamente, em cada iteração do otimizador clássico, o valor de expectativa do Hamiltoniano do problema $H_C$ deve ser calculado. Para um grafo com $|E|$ arestas, o estimador de estado vetorial padrão agrega $|E|$ termos da forma $\langle Z_i Z_j \rangle$. Como cada termo requer uma passagem $O(2^n)$ sobre as amplitudes do estado vetorial (onde $n$ é o número de qubits), o custo de tempo de execução por iteração do otimizador escala como $O(|E| \cdot 2^n)$. Esse custo de agregação frequentemente domina o tempo total de simulação, especialmente para grafos com muitas arestas, mesmo em profundidades de circuito baixas ($p$).

Metodologia: AA-QAOA (Automorphism-Assisted QAOA)
O artigo propõe o AA-QAOA, um método para acelerar a simulação de estado vetorial clássica do QAOA explorando as simetrias do grafo subjacente. A ideia central é que, para grafos com um grupo de automorfismo $\text{Aut}(G)$ não trivial, o ansatz do QAOA prepara um estado $|\psi(\vec{\beta}, \vec{\gamma})\rangle$ que é invariante sob a ação de $\text{Aut}(G)$.

A metodologia procede da seguinte forma:

1. Identificação de Órbita de Arestas: Utilizando o pacote Nauty, o algoritmo calcula os geradores do grupo de automorfismo do grafo. Esses geradores são usados para particionar o conjunto de arestas $E$ em classes de equivalência (órbitas), denotadas por $\tilde{S}_m$. Arestas dentro da mesma órbita são estruturalmente idênticas sob as simetrias do grafo.
2. Substituição do Observável: Em vez de avaliar o Hamiltoniano de custo completo $H_C = \frac{1}{2} \sum_{(i,j) \in E} (1 - Z_i Z_j)$, o método o substitui por um observável reduzido $H_{\text{red}}$. Este Hamiltoniano reduzido retém apenas um termo ZZ representativo por órbita de aresta, ponderado pelo tamanho dessa órbita:
   $$H_{\text{red}} = \frac{1}{2} \sum_{m=1}^{|O_E|} |\tilde{S}_m| (1 - Z_{i_m} Z_{j_m})$$
   onde $|O_E|$ é o número de órbitas de arestas.
3. Equivalência Exata: Os autores provam que, para o estado invariante em $\text{Aut}(G)$ preparado pelo ansatz padrão do QAOA, os valores de expectativa são idênticos: $\langle H_{\text{red}} \rangle = \langle H_C \rangle$. Consequentemente, o cenário de otimização, os parâmetros variacionais ótimos $(\vec{\beta}^*, \vec{\gamma}^*)$ e a razão de aproximação final permanecem inalterados.
4. Implementação do Pipeline: O circuito do ansatz QAOA é construído usando o Hamiltoniano completo $H_C$ (garantindo que a preparação do estado seja idêntica ao QAOA padrão). No entanto, durante o loop de otimização clássica, o estimador calcula o valor de expectativa usando apenas os $|O_E|$ termos de $H_{\text{red}}$.

Principais Contribuições

• Aceleração de Agregação Clássica: A principal contribuição é uma redução no custo de pós-processamento clássico do estimador de estado vetorial. O custo de agregação cai de $O(|E| \cdot 2^n)$ para $O(|O_E| \cdot 2^n)$ por iteração. O fator de aceleração é determinado pela razão de órbita $|E|/|O_E|$.
• Desacoplamento do Cone Causal Reverso (RCC): O artigo distingue explicitamente seu mecanismo de trabalhos anteriores que utilizam o Cone Causal Reverso (RCC) para reduzir a profundidade do circuito ou o span de qubits. Os autores demonstram que a aceleração do AA-QAOA é independente do span de qubits dos RCCs representativos. Mesmo que o RCC de uma única aresta representativa abranja todos os qubits (como em grafos completos), a aceleração persiste porque a economia ocorre na soma clássica dos termos, não na execução do circuito quântico ou na evolução do estado.
• Exatidão: O método fornece uma substituição exata, não uma aproximação. A otimização contra $H_{\text{red}}$ converge para a mesma solução exata que a otimização contra $H_C$.

Resultados
Os autores testaram o AA-QAOA em várias famílias de grafos usando camadas $p=1$ e $p=2$:

• Grafos Estruturados em Árvore: Em árvores binárias e balanceadas de até 34 vértices, o método alcançou reduções significativas de tempo de execução. Para uma árvore binária de 34 vértices, o tempo do otimizador caiu de $>3600$ segundos (Hamiltoniano completo) para $360,56$ segundos (reduzido), uma redução de mais de 90%. O uso de pico de memória também diminuiu significativamente.
• Controles Diagnósticos: Para isolar o mecanismo, os autores testaram:
  • Grafos Completos ($K_n$): Apesar de possuírem uma única órbita de aresta ($|O_E|=1$) e um RCC representativo que abrange cada qubit, o $K_{16}$ mostrou uma aceleração de $\approx 8\times$. Isso refuta a hipótese de que a aceleração depende da redução do span de qubits do RCC.
  • Grafos Estrela: Mostraram acelerações consistentes com a razão de órbita uma vez que o overhead foi minimizado.
  • Grafos Aleatórios 3-Regulares: Para grafos com grupos de automorfismo triviais ($|O_E| \approx |E|$), nenhuma aceleração foi observada, confirmando que o benefício está estritamente ligado à simetria.
• Independência de Arquitetura: Testes em ambos os backends de CPU e GPU confirmaram que a aceleração é intrínseca à etapa de agregação clássica e não é um artefato de aceleradores de hardware específicos.
• Razões de Aproximação: Em todas as instâncias testadas, as razões de aproximação $R_{\text{red}}$ e $R_{\text{full}}$ foram idênticas dentro da variância do otimizador, validando a afirmação teórica de equivalência exata.

Significado e Escopo
O artigo posiciona o AA-QAOA como um acelerador especializado para pipelines de simulação de estado vetorial clássica, que são a principal ferramenta para grupos de pesquisa de QAOA sem acesso a QPUs.

• Limitações: Os autores declaram explicitamente que o AA-QAOA não oferece aceleração em um processador quântico (QPU). No hardware, o circuito completo executa independentemente do observável medido, e a agregação de termos diagonais ZZ é um passo de pós-processamento trivial em bitstrings clássicas que não incorre no custo $O(|E| \cdot 2^n)$ encontrado na simulação de estado vetorial.
• Aplicabilidade: O método é mais benéfico para grafos estruturados com alta simetria (ex: árvores, ciclos, grafos completos, hipercubos) onde a razão de órbita $|E|/|O_E|$ é grande. É menos eficaz para grafos genericamente assimétricos (ex: grafos aleatórios 3-regulares) onde o grupo de automorfismo é trivial.
• Overhead: A pré-computação de automorfismos (usando Nauty) tem um custo que não é amortizado nos tempos de execução relatados por iteração. No entanto, para estudos típicos de QAOA envolvendo muitas iterações de otimização ou varreduras sobre parâmetros, esse custo de pré-computação é insignificante comparado às economias acumuladas de simulação.

Em resumo, o AA-QAOA fornece um método rigoroso e exato para reduzir o gargalo computacional da simulação clássica de QAOA, aproveitando as simetrias do grafo para reduzir o número de termos na agregação da expectativa do custo, sem alterar o circuito quântico ou a qualidade da solução.