Um sistema de pesquisa da Physical Superintelligence (PSI), laboratório de física com sede em Cambridge, Massachusetts, encontrou uma prova da conjectura de Aaronson-Ambainis, um dos problemas abertos mais conhecidos da computação quântica, sem solução desde 2008. A PSI anunciou o resultado nesta sexta-feira, 6 de novembro.
Segundo a PSI, o sistema — desenvolvido internamente e executado com instâncias de um modelo não público da Anthropic — chegou a uma prova completa no terceiro dia de execução. A equipe formalizou a prova no assistente de provas Lean, que verifica cada passo por computador, e o núcleo do Lean aceitou a formalização. A equipe então direcionou o sistema a problemas abertos relacionados e afirma ter melhorado o resultado duas vezes, com o Lean aceitando a versão final. O manuscrito e a formalização em Lean 4 são públicos.
O que a prova de Aaronson-Ambainis estabelece
A conjectura de Aaronson-Ambainis, proposta por Scott Aaronson e Andris Ambainis, trata de quando os computadores quânticos podem ser exponencialmente mais rápidos que os clássicos. Em termos práticos, a prova estabelece que, para perguntas de sim ou não sobre entradas aleatórias, um computador comum pode estimar a probabilidade de resposta do computador quântico com um número de leituras que cresce apenas polinomialmente — e não exponencialmente. Em outras palavras: sem estrutura especial no problema, não há atalho exponencial quântico nesse cenário. O resultado formal mostra que, se um polinômio varia com variância v e tem grau d, alguma variável tem influência de pelo menos c·v^(5/2)/d^6, com c em torno de 0,0025.
A prova segue um plano de Shachar Lovett e Jiapeng Zhang e substitui uma desigualdade que o plano deixava como conjectura por uma nova desigualdade, demonstrada por meio de um emparelhamento de configurações de entrada obtido com um determinante. Pesquisadores de Stanford — Guy Blanc, Jordan Docter, Carmen Strassle e Li-Yang Tan —, que em agosto de 2026 haviam resolvido um caso especial da conjectura de Aaronson-Ambainis, leram a prova, enviaram comentários e estão escrevendo uma exposição mais curta para especialistas. Eles escreveram à PSI: "Este é um resultado enorme. Ele resolve uma conjectura de décadas com implicações importantes para a natureza dos problemas que admitem acelerações quânticas."
Ressalvas: o que ainda falta confirmar
Ressalvas importantes: a prova ainda não passou por revisão por pares. O Lean verifica os passos formais, mas especialistas ainda precisam confirmar que a afirmação formalizada corresponde exatamente à conjectura de Aaronson-Ambainis, como os autores a formularam. O modelo usado não é público e não foi identificado, e o artigo legível por humanos não é, ele próprio, verificado por máquina. David Turturean, da equipe técnica da PSI, liderou o trabalho, com auditoria da prova por Jim Halverson e comentários sobre a formalização por Phiala Shanahan.
Crédito da imagem: computador quântico IBM Quantum System One — foto de divulgação da IBM, via Fraunhofer-Gesellschaft.
Fontes: Physical Superintelligence (PSI); Unite.AI; The Quantum Insider
Transparência: esta matéria foi produzida com auxílio de inteligência artificial, com cruzamento de publicações públicas no X e de fontes da internet. Consulte as fontes originais para verificar as informações.
Muse
