⚛️ quantum physics

Evaluating QAOA expectation values can be as hard as counting optimal solutions

Este artigo estabelece que avaliar valores esperados exatos ou exponencialmente precisos de QAOA para o problema MaxCut para profundidade $p \geq 2$ é #P-duro, demonstrando que a dificuldade computacional transita da tratabilidade para a contagem de soluções ótimas em vez de meramente otimização.

Autores originais: Stuart Hadfield

Publicado 2026-08-13

📖 8 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Stuart Hadfield

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um mundo onde os computadores não apenas processam números, mas dançam com probabilidades. Este é o reino da computação quântica, um campo que promete resolver problemas tão emaranhados e complexos que os supercomputadores de hoje levariam mais tempo do que a idade do universo para decifrar. No coração desta dança está uma rotina popular chamada Algoritmo de Otimização Aproximada Quântica, ou QAOA. Pense no QAOA como uma caça ao tesouro de alta tecnologia. Você tem um mapa (um problema) com muitos caminhos possíveis, e quer encontrar o caminho que leva ao maior tesouro (a melhor solução). O computador quântico prepara um estado especial de "superposição" — uma mistura mágica de todos os caminhos possíveis ao mesmo tempo — e então, através de uma série de etapas chamadas "camadas" ou "profundidade", ele tenta inclinar as chances para que o melhor caminho brilhe mais intensamente quando você finalmente olhar.

Para saber se a caça ao tesouro está indo bem, os cientistas precisam verificar o "valor de expectativa". Em termos simples, isso é como dar uma rápida espiada na dança do computador quântico para ver o quão perto ele está de encontrar o ouro, sem realmente parar a dança para contar cada única moeda. Por muito tempo, os pesquisadores sabiam que, se a dança tivesse apenas um passo (profundidade $p=1$ ), verificar essa pontuação era fácil, como ler uma receita simples. Mas o que acontece quando a dança se torna mais complicada, com dois ou mais passos? Um estudo recente de Wang e colegas mostrou que verificar a pontuação para essas danças mais profundas é incrivelmente difícil — tão difícil quanto resolver a própria caça ao tesouro original. Mas será que é apenas tão difícil quanto encontrar um bom caminho, ou é ainda mais difícil?

Este artigo, escrito por Stuart Hadfield, mergulha fundo nessa questão. O autor prova que, para o QAOA com duas ou mais camadas, verificar a pontuação não é apenas tão difícil quanto encontrar uma única melhor solução; é tão difícil quanto contar cada uma das melhores soluções existentes. No mundo da ciência da computação, encontrar uma solução é um desafio difícil, mas contar todas elas é um monstro de um tamanho diferente, frequentemente considerado ainda mais impossível de ser lidado por computadores clássicos. Hadfield mostra que este "monstro da contagem" aparece no momento em que você adiciona uma segunda camada ao algoritmo. O artigo não apenas sugere isso; ele fornece uma prova matemática rigorosa, construindo um tipo específico de grafo de problema que força qualquer computador que tente calcular a pontuação do QAOA a essencialmente resolver o problema de contagem impossível. Isso significa que, para esses algoritmos quânticos mais profundos, o próprio ato de verificar o quão bem eles estão indo é, no pior cenário, uma tarefa que pode estar fundamentalmente além do alcance dos computadores clássicos, mesmo que tenhamos uma máquina quântica perfeita para executar a dança.

A Caça ao Tesouro Fica Complicada

Vamos decompor o truque de mágica. O algoritmo QAOA é projetado para resolver o problema "MaxCut". Imagine um grupo de amigos em uma festa, e você quer dividi-los em dois times (Time Vermelho e Time Azul) para jogar um jogo. O objetivo é organizar os times para que o número máximo de amizades seja rompido entre os dois lados. Este é o "MaxCut". Alguns arranjos são melhores que outros, e encontrar o arranjo absolutamente melhor é um quebra-cabeça clássico que se torna mais difícil à medida que você adiciona mais amigos.

O algoritmo QAOA tenta encontrar esse melhor arranjo girando uma moeda quântica. Ele começa com todos em uma superposição (tanto Vermelho quanto Azul ao mesmo tempo) e então aplica uma série de "giros" (as camadas). Quanto mais giros você adiciona, mais sofisticada se torna a dança. Para ver se a dança está funcionando, os cientistas calculam um "valor de expectativa". Pense nisso como uma "pontuação" que diz, em média, quantas amizades são rompidas na dança quântica.

Para um único giro ( $p=1$ ), calcular essa pontuação é fácil. Você pode escrevê-la em um guardanapo. Mas quando você adiciona um segundo giro ( $p=2$ ), as coisas ficam estranhas. Pesquisas anteriores mostraram que calcular essa pontuação era "NP-difícil", o que significa que era tão difícil quanto encontrar um único melhor arranjo de times. Mas o artigo de Hadfield diz: "Espere, é na verdade pior do que isso".

O Monstro da Contagem

A principal descoberta de Hadfield é uma atualização nítida em nossa compreensão da dificuldade. Ele prova que calcular a pontuação para $p \ge 2$ não é apenas "NP-difícil" (encontrar uma solução); é #P-difícil.

Para entender a diferença, imagine que você é um detetive.

NP-difícil é como ser perguntado: "Você consegue encontrar um suspeito que cometeu o crime?" É difícil, mas se você tiver sorte ou tentar o suficiente, pode encontrar um.
#P-difícil é como ser perguntado: "Quantos suspeitos no total cometeram o crime?" Você tem que encontrar cada um deles e contar.

No mundo da ciência da computação, contar é geralmente considerado muito mais difícil do que apenas encontrar um. Hadfield mostra que, para o QAOA com duas ou mais camadas, a matemática necessária para calcular a pontuação força você a contar o número de soluções perfeitas.

O Dispositivo Mágico

Como ele provou isso? Hadfield construiu um "gadget" inteligente, que é como uma armadilha projetada para pegar o computador. Ele pegou um problema MaxCut padrão e construiu um grafo gigante e complexo ao redor dele. Este grafo possui pontos de "âncora" especiais e blocos de "variáveis".

O truque está no design. Quando o computador quântico executa sua dança neste grafo específico, a pontuação final (o valor de expectativa) transforma-se em uma grande expressão matemática chamada "polinômio de Laurent". Esta expressão é como uma longa sequência de termos, cada um com uma potência diferente de uma variável (como $z^1, z^2, z^3...$ ).

Hadfield mostrou que a maior potência nesta sequência (o "coeficiente extremo") guarda um segredo. Se você puder calcular a pontuação perfeitamente, você pode extrair essa maior potência. E aqui está o detalhe: o tamanho desse número específico é diretamente proporcional ao número total de soluções perfeitas do problema original.

Portanto, se você pudesse calcular facilmente a pontuação do QAOA para este grafo, você saberia instantaneamente a resposta para o problema do "monstro da contagem". Como se acredita que a contagem é impossível para computadores clássicos fazerem de forma eficiente, calcular a pontuação do QAOA também deve ser impossível para eles.

A Surpresa da "Uma Aresta"

O artigo torna-se ainda mais surpreendente. Você pode pensar: "Ok, calcular a pontuação total é difícil, mas talvez calcular a pontuação para apenas uma amizade específica (uma única aresta) seja fácil?"

Hadfield diz que não. Ele prova que mesmo se você pedir ao computador quântico para lhe dizer a correlação entre duas pessoas específicas (um "correlacionador de dois qubits" como $\langle Z_r Z_s \rangle$ ), o problema permanece #P-difícil. A dificuldade não está apenas no quadro geral; ela está gravada nos menores detalhes do algoritmo.

O Que Isso Significa para o Futuro

O artigo traça uma linha clara na areia:

Profundidade $p=1$ : Fácil. Podemos calcular a pontuação eficientemente.
Profundidade $p \ge 2$ : Difícil. Calcular a pontuação é tão difícil quanto contar todas as soluções ótimas.

Isso tem implicações enormes. Muitos algoritmos modernos usam QAOA para treinar a máquina, ajustando os "giros" (parâmetros) para obter uma pontuação melhor. Se calcular a pontuação é tão difícil, então treinar esses algoritmos em um computador clássico (para ver como a máquina quântica está se saindo) pode ser impossível para circuitos profundos.

O autor também observa que isso não significa que os computadores quânticos sejam inúteis. Na verdade, pode significar que eles são mais úteis. Se um computador clássico não consegue sequer verificar a pontuação, talvez o computador quântico seja o único que consegue. No entanto, o artigo também alerta que esta "dificuldade" é um cenário de pior caso. Não significa que todo grafo seja impossível de resolver; apenas significa que existem grafos específicos e complicados onde a matemática falha para os computadores clássicos.

A Conclusão

O artigo de Stuart Hadfield é um chamado de atenção para a comunidade quântica. Ele nos diz que, à medida que tornamos o QAOA mais poderoso ao adicionar mais camadas, não estamos apenas tornando o problema mais difícil de resolver; estamos tornando o problema de verificar nosso trabalho exponencialmente mais difícil. Passamos de um mundo onde podíamos verificar facilmente a dança quântica para um mundo onde verificar a dança exige resolver um quebra-cabeça de contagem que pode ser a coisa mais difícil da ciência da computação. É um lembrete de que, no reino quântico, quanto mais fundo você vai, mais misteriosa a matemática se torna.

Resumo Técnico: Avaliar Valores de Esperança do QAOA é #P-Difícil

Enunciado do Problema
O artigo aborda a complexidade computacional da avaliação de valores de esperança para o Algoritmo de Otimização Aproximada Quântica (QAOA) aplicado ao problema MaxCut. Embora a avaliação do valor de esperança do custo $F_p(G; \gamma, \beta) = \langle \psi_p | C_G | \psi_p \rangle$ seja conhecida por ser computável eficientemente para a profundidade $p=1$ em grafos arbitrários, trabalhos recentes estabeleceram que a avaliação exata torna-se NP-difícil para qualquer profundidade fixa $p \ge 2$ . A questão central investigada aqui é se a dificuldade para $p \ge 2$ limita-se à otimização (encontrar uma solução) ou se estende à contagem (determinar o número de soluções ótimas). Especificamente, o autor pergunta se computar esses valores de esperança é #P-difícil, uma classe de complexidade geralmente considerada mais difícil que NP, correspondendo à dificuldade de contar o número de soluções de um problema de satisfação de restrições.

Metodologia
O autor refina o mecanismo de prova de dureza introduzido por Wang et al. [5], que utilizou polinômios de Laurent para recuperar o valor do corte máximo a partir do maior expoente. A abordagem do autor envolve as seguintes etapas:

Construção de Grafo (Gadget de Contagem Balanceada): Em vez dos gadgets assimétricos usados no trabalho anterior, o autor constrói um grafo específico $G(H)$ a partir de um grafo de entrada $H$ . Esta construção emprega:
- Gadgets de Variáveis: Para cada vértice em $H$ , um grafo bipartido completo balanceado $K_{L,L}$ é criado, onde $L = O(n)$ .
- Arestas Síncronas: Arestas conectando vértices correspondentes nos gadgets $K_{L,L}$ de vértices adjacentes em $H$ para preservar a estrutura original do grafo.
- Vértices de Âncora: Dois vértices universais, $r$ e $s$ , conectados a todos os vértices nos gadgets de variáveis e entre si.
- Esta construção garante que o grafo $G(H)$ tenha um diâmetro de 2 e que seus cortes máximos sejam rigidamente restringidos: os gadgets $K_{L,L}$ devem ser cortados completamente, e as âncoras devem estar em lados opostos.
Análise de Polinômio de Laurent: O valor de esperança do custo (ou um correlador de dois qubits específico $\langle Z_r Z_s \rangle$ ) é expresso como um polinômio de Laurent em uma variável de fase $z = e^{i\phi}$ . O autor analisa os coeficientes deste polinômio.
- Eles identificam um "coeficiente extremo" correspondente ao expoente de maior grau $D^*$ .
- Através de uma análise de "soma de caminhos reduzida", eles provam que o coeficiente $a_{D^*}$ é não nulo e diretamente proporcional ao número de cortes máximos do grafo original $H$ , denotado por $|\# \text{MC}(H)|$ .
- Especificamente, $a_{D^*} = \kappa \cdot |\# \text{MC}(H)|$ , onde $\kappa$ é um fator algébrico conhecido e não nulo que depende dos ângulos do mixer e do tamanho do grafo.
Redução via Interpolação: O autor demonstra que, ao consultar o oráculo de valor de esperança do QAOA em muitos valores de fase distintos (raízes da unidade) de ordem polinomial, é possível usar a transformada discreta de Fourier inversa para recuperar exatamente os coeficientes de Laurent. Como o coeficiente extremo codifica a contagem de cortes máximos, um oráculo capaz de avaliação exata (ou avaliação com precisão exponencial) permite a recuperação desta contagem, estabelecendo assim uma redução de Turing determinística de tempo polinomial do problema #P-difícil de contar cortes máximos para o problema de avaliar valores de esperança do QAOA.

Principais Contribuições e Resultados

Dicotomia de Complexidade: O artigo estabelece uma transição de complexidade nítida para valores de esperança do QAOA em grafos simples não ponderados:
- $p=1$ : O problema está em FP (computável em tempo polinomial).
- $p \ge 2$ : O problema é #P-difícil sob reduções de Turing determinísticas de tempo polinomial.
Contagem vs. Otimização: Ao contrário do resultado de NP-dureza que recuperava o valor do corte máximo, este trabalho mostra que avaliar o valor de esperança permite recuperar o número de cortes máximos. Isso eleva a dificuldade de otimização para contagem.
Dureza Restrita: A #P-dureza mantém-se mesmo sob restrições significativas:
- Aplica-se à avaliação de um único correlador de dois qubits designado $\langle Z_r Z_s \rangle$ , em vez da função de custo global.
- Mantém-se para um conjunto altamente restrito de parâmetros do algoritmo (ângulos de mixer fixos $\beta_1 = \arctan(1/2)$ , $\beta_2 = \pi/4$ , e ângulos de custo vinculados $\gamma_1 = \gamma_2 = \phi$ ).
- Aplica-se a grafos com diâmetro 2 (embora estes grafos possuam alto grau).
Derivadas e Hessianas: O autor estende estes resultados para mostrar que computar gradientes e Hessianas exatos da função de custo do QAOA em relação aos parâmetros também é #P-difícil.
Precisão Exponencial: A dureza estende-se ao problema de aproximar o valor de esperança com erro aditivo exponencialmente pequeno ( $2^{-\alpha N}$ ), pois esta precisão é suficiente para distinguir o coeficiente extremo e recuperar a contagem inteira via arredondamento.

Significância e Alegações
O artigo afirma fornecer uma "classificação de complexidade exata limpa" para valores de esperança do QAOA. A principal significância reside em demonstrar que a transição de $p=1$ para $p=2$ não é meramente uma mudança de tratabilidade para dureza de otimização (NP-difícil), mas sim uma mudança para dureza de contagem (#P-difícil).

O autor enfatiza que seus resultados são declarações de pior caso referentes a famílias específicas de grafos de alto grau e não implicam que avaliar o QAOA seja difícil para todos os grafos ou instâncias típicas. Eles observam que a dureza depende de avaliação exata ou de precisão exponencial; eles não alegam dureza para regimes de erro aditivo constante ou polinomialmente pequeno, que são mais relevantes para os atuais dispositivos quânticos de escala intermediária ruidosa (NISQ).

Além disso, o artigo distingue suas descobertas dos resultados de supremacia quântica relacionados à amostragem. Embora a amostragem de saídas do QAOA em $p=1$ já seja classicamente difícil sob certas condições, este trabalho mostra que avaliar o valor de esperança em $p=2$ é suficiente para resolver problemas de contagem #P-difíceis. O autor conclui que seus resultados implicam que, se fosse possível avaliar eficientemente os valores de esperança do QAOA com precisão exponencial, a hierarquia polinomial colapsaria para seu nível mais baixo ($P=PH$). Isso tem implicações para algoritos híbridos que dependem de processamento clássico de valores de esperança quânticos, sugerindo que tais abordagens podem enfrentar barreiras computacionais fundamentais no pior caso se alta precisão for necessária.