A sharp interaction-degree threshold for simulating QAOA

Resumo Técnico: Um Limiar Agudo de Grau de Interação para Simular QAOA

Enunciado do Problema
O Algoritmo de Otimização Aproximada Quântica (QAOA) é um candidato líder para vantagem quântica no curto prazo. Embora trabalhos anteriores de Farhi e Harrow tenham estabelecido que amostrar a partir da distribuição de saída de QAOA de profundidade 1 com erro multiplicativo suficientemente pequeno é computacionalmente difícil (implicando um colapso da hierarquia polinomial), as condições estruturais sob as quais essa dificuldade persiste não foram totalmente delimitadas. Especificamente, não estava claro como o "grau de interação" da função de custo — o número máximo de outras variáveis acopladas a qualquer variável única em uma função de custo 2-local — impacta a simulabilidade clássica. Este artigo investiga o limiar onde a complexidade da amostragem transita de tratável classicamente para intratável.

Metodologia
Os autores analisam funções de custo 2-local $C(x_1, \dots, x_n) = \sum C_i$, parametrizando as instâncias pelo seu grau de interação $d$. Eles empregam duas abordagens metodológicas principais:

1. Redução de Dificuldade (Grau 3): Para provar a dificuldade para grau de interação $d=3$, os autores constroem uma redução de $\text{PostBQP}$ (a classe de problemas solucionáveis por computadores quânticos com pós-seleção) para QAOA de profundidade 1. Eles utilizam uma técnica de "redução de grau" onde portas Hadamard intermediárias em um circuito universal são substituídas por acoplamentos diagonais pós-selecionados a qubits auxiliares. Ao pré-processar cuidadosamente o circuito para garantir que portas diagonais consecutivas sejam separadas e usando uma substituição de acoplamento específica, eles demonstram que qualquer circuito $\text{PostBQP}$ pode ser compilado em um circuito QAOA de profundidade 1 com um grau de interação de no máximo 3. Eles também mostram que as funções de custo resultantes podem ser tornadas trivialmente otimizáveis (monótonas).
2. Tratabilidade via Redes de Tensores (Grau 2): Para grau de interação $d=2$, os autores aproveitam o algoritmo de Markov–Shi para simular circuitos quânticos com pequena largura de corte. Eles observam que um grafo com grau máximo 2 decompõe-se em caminhos, ciclos e vértices isolados. Ao ordenar os qubits linearmente, eles limitam a "largura de corte" (o número de portas cruzando qualquer corte na ordenação) do circuito QAOA. Eles aplicam o resultado de Markov–Shi, que afirma que um circuito de tamanho $T$ e largura de corte $r$ pode ser simulado em tempo $T^{O(1)} \exp[O(r)]$.

Principais Contribuições e Resultados

• Limiar Agudo no Grau 3: O artigo estabelece que QAOA de profundidade 1 com grau de interação 3 é computacionalmente difícil de amostrar com erro multiplicativo. Especificamente, se um algoritmo clássico pudesse amostrar a partir de tais distribuições com erro multiplicativo $c < \sqrt{2}$, a hierarquia polinomial (PH) colapsaria para seu terceiro nível ($\Delta_3$). Este resultado vale mesmo para instâncias onde a função de custo é trivial de otimizar classicamente, indicando que a dificuldade de amostragem não implica automaticamente uma vantagem quântica para otimização.
• Simulação Eficiente no Grau 2: Por outro lado, os autores provam que, para grau de interação 2, as probabilidades marginais de saída de um circuito QAOA de profundidade-$p$ em $n$ qubits podem ser computadas deterministicamente em tempo $(np)^{O(1)} \exp(O(p))$. Consequentemente, a amostragem clássica exata é de tempo polinomial ($n^{O(1)}$) sempre que a profundidade $p = O(\log n)$.
• Trivialidade da Função de Custo: Uma descoberta significativa é que as instâncias "difíceis" de grau 3 construídas para a prova de dificuldade possuem funções de custo que são monótonas e maximizadas na string de todos uns ($x=1^n$). Isso demonstra que a dificuldade computacional da amostragem é distinta da dificuldade de encontrar a solução ótima.
• Conexão com Complexidade Clássica: Os autores traçam um paralelo com problemas clássicos de satisfação de restrições, notando a similaridade entre a transição 2-SAT/3-SAT (onde grau 2 está em P e grau 3 é NP-completo) e o limiar de simulação QAOA.

Significado e Alegações
O artigo alega identificar um "limiar agudo de grau de interação" separando a simulabilidade clássica da dificuldade de amostragem para QAOA 2-local. O significado reside em esclarecer as limitações estruturais da vantagem quântica do QAOA:

• Limitações da Dificuldade de Amostragem: Os resultados sugerem que a dificuldade de amostragem por si só é insuficiente para garantir uma vantagem quântica para otimização, uma vez que as instâncias difíceis identificadas possuem problemas de otimização trivialmente solucionáveis.
• Precisão dos Limites de Simulação: O trabalho fornece limites assintóticos precisos para a simulação clássica, mostrando que a transição de fácil para difícil ocorre estritamente entre os graus 2 e 3.
• Questões Abertas: Os autores modestamente observam que, embora a simulação de grau 2 seja eficiente para profundidade logarítmica, ela permanece exponencial em $p$. Eles também afirmam que estender os resultados de dificuldade para erro aditivo para grafos de grau 3 permanece um problema aberto, pois exigiria um limite de anticoncentração e uma conjectura de dificuldade no caso médio, que não estão atualmente disponíveis para essas estruturas de grafo específicas.

Em resumo, o artigo delimita a fronteira da simulabilidade clássica para QAOA, provando que o grau de interação 3 é o ponto em que a amostragem se torna computacionalmente intratável classicamente (sob suposições padrão de complexidade), enquanto o grau 2 permanece eficientemente simulável para circuitos rasos.