Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation

Resumo Técnico: Somas Quadráticas de Potências para Simulação de Circuitos Quânticos com Tratabilidade de Parâmetro Fixo

Declaração do Problema
A simulação clássica forte de circuitos quânticos — o cálculo de amplitudes de saída específicas $\langle z|C|y\rangle$ — é uma tarefa fundamental para otimização de circuitos, análise de ruído e identificação de regimes de dificuldade quântica. A dificuldade surge porque um estado de $n$ qubits requer $2^n$ amplitudes. Embora a contração de redes de tensores ofereça uma rota padrão, sua complexidade é governada pela largura de árvore do grafo de linha da rede de tensores ($cc(N_C) = \text{tw}(L(N_C))$). Abordagens recentes que utilizam ferramentas de representação de conhecimento (Diagramas de Decisão Binária e Contagem de Modelos Ponderados) codificam a amplitude como uma Soma de Potências (SOP) sobre caminhos de Feynman. No entanto, o parâmetro estrutural que governa a dificuldade desses métodos baseados em SOP não foi totalmente caracterizado, e os métodos existentes frequentemente dependem de ordenações lineares de variáveis (largura de rank linear) ou largura de árvore, o que pode ser subótimo para certas famílias de circuitos.

Metodologia
O artigo reformula a simulação forte de circuitos sobre o conjunto de portas $\{H, T, CZ\}$ (e extensões) como a avaliação de uma Soma Quadrática de Potências (SOP).

1. Formulação SOP: Ao inserir resoluções da identidade entre as portas, a amplitude é expressa como uma soma sobre variáveis de caminho booleanas $x \in \{0,1\}^V$:
   $$Z = \frac{1}{R} \sum_{x \in \{0,1\}^V} \omega_r^{f(x)}$$
   onde $f(x)$ é um polinômio de grau 2 sobre $\mathbb{Z}_r$ (com $r=8$ para $\{H, T, CZ\}$). O polinômio consiste em uma constante, termos lineares (de portas $T$ e fronteiras fixadas) e termos cruzados quadráticos (de portas $H$ e $CZ$).
2. Representação em Grafo: As interações quadráticas definem um grafo de variáveis SOP $G_C = (V, E)$, onde os vértices são as variáveis de caminho livres e as arestas representam os termos cruzados quadráticos.
3. Parâmetro Estrutural: Os autores identificam a largura de rank ($\text{rw}$) de $G_C$ como o parâmetro estrutural crítico que governa a dificuldade da simulação, em vez da largura de árvore ou da largura de rank linear.
4. Algoritmo: Um algoritmo de programação dinâmica (PD) é construído que processa uma decomposição de rank de $G_C$ das folhas até a raiz.
   • Representação de Estado: Em cada nó da árvore de decomposição, o algoritmo mantém uma tabela de "assinaturas de fronteira" (a paridade dos vizinhos no corte) e "resíduos" (a soma parcial do polinômio).
   • Complexidade: O tamanho do espaço de assinaturas é limitado por $2^k$, onde $k$ é a largura de rank. O algoritmo calcula todas as contagens de resíduos $N_j$ (e, portanto, a amplitude) no tempo $O(n r^4 4^k \text{poly}(n) + r \log r)$. Para $r$ fixo, isso é $2^{O(k)} \text{poly}(n)$, estabelecendo Tratabilidade de Parâmetro Fixo (FPT) em relação à largura de rank.
   • Otimização: Uma implementação em modo de Fourier reduz a dependência de $r$ na etapa de junção, alcançando o limite de tempo declarado.

Principais Contribuições

1. Algoritmo FPT de Largura de Rank: O artigo fornece um programa dinâmico explícito de decomposição de rank para avaliar SOPs quadráticas. Este é o primeiro algoritmo a alcançar simulação FPT para circuitos quânticos parametrizados especificamente pela largura de rank do grafo de variáveis SOP.
2. Separação Teórica de Parâmetros: Os autores provam que a largura de rank é estritamente mais poderosa do que parâmetros concorrentes para famílias específicas de circuitos. Eles constroem uma família de circuitos $C_{h,t}$ onde:
   • $\text{rw}(G_C) = O(1)$ (limitado).
   • $\text{lrw}(G_C) = \Omega(h)$ (cresce com a altura, governando diagramas de decisão lineares).
   • $\text{cc}(N_C) = \Omega(t)$ (cresce com o tamanho do clique, governando a contração de tensores).
     Isso demonstra que o novo algoritmo pode simular circuitos com largura de rank constante, enquanto métodos de diagramas de decisão e redes de tensores enfrentam explosão exponencial.
3. Unificação de Limites:
   • O artigo estabelece que o grafo de variáveis SOP $G_C$ é um menor do grafo de linha da rede de tensores $L(N_C)$, implicando $\text{tw}(G_C) \leq \text{cc}(N_C)$. Isso recupera o limite de rede de tensores de Markov–Shi como um caso especial de uma PD baseada em largura de árvore em $G_C$.
   • Mostra que a garantia de largura de rank linear de simuladores recentes de diagramas de decisão (por exemplo, FeynmanDD) é um caso especial do resultado de largura de rank, pois $\text{rw}(G) \leq \text{lrw}(G)$.
4. Generalização para Clifford+T: A metodologia estende-se além de $\{H, T, CZ\}$. Qualquer circuito construído a partir de portas Hadamard, portas diagonais arbitrárias de um único qubit e portas CZ (ou CX) produz uma SOP quadrática. Como as portas diagonais contribuem apenas com termos lineares (fases unárias) e não alteram a estrutura do grafo $G_C$, a garantia FPT de largura de rank aplica-se a todo o conjunto de portas Clifford+T.

Resultados

• Eficiência: O algoritmo avalia amplitudes em tempo exponencial apenas na largura de rank do grafo de variáveis SOP e polinomial no tamanho do circuito.
• Vantagem Comparativa: Na família construída $C_{h,t}$, o algoritmo de largura de rank opera com sobrecarga polinomial fixa, enquanto a contração de redes de tensores e as abordagens de diagramas de decisão degradam-se exponencialmente com $t$ e $h$, respectivamente.
• Aplicabilidade Prática: Os autores observam que contadores de modelos ponderados de propósito geral e ferramentas de diagramas de decisão podem servir como "motor de trabalho", com a PD especializada de largura de rank acionada quando o grafo associado exibe pequena largura de rank.

Significado
O artigo afirma que a largura de rank é a "medida estrutural correta" para a dificuldade de avaliar SOPs quadráticas na simulação quântica. Ao deslocar o foco da largura de árvore (redes de tensores) ou da largura de rank linear (diagramas de decisão) para a largura de rank, o trabalho fornece uma rota de simulação comprovadamente superior para famílias específicas de circuitos. Ele preenche a lacuna entre ferramentas de representação de conhecimento (IA) e teoria estrutural de grafos, oferecendo um quadro unificado onde a dificuldade da simulação é precisamente determinada pela largura de rank do grafo de interação. Os resultados sugerem que, para circuitos com estrutura de baixa largura de rank, a simulação clássica é mais eficiente do que indicado anteriormente apenas pelos limites de redes de tensores ou diagramas de decisão.