O que é a conjectura de Aaronson e Ambainis?

É a afirmação de que, em perguntas de sim ou não sobre entradas aleatórias sem estrutura, um computador quântico só tem ganho polinomial de leituras sobre um algoritmo clássico. Ela foi proposta por Scott Aaronson e Andris Ambainis, a partir de uma palestra de 2008 e de um artigo de 2009.

Quem provou a conjectura?

A PSI (Physical Superintelligence) anunciou em 6 de novembro de 2026 que um sistema interno, rodando um modelo não lançado da Anthropic, achou a prova no terceiro dia de execução. David Turturean, da PSI, responde pela correção do artigo.

A prova foi verificada?

A formalização em Lean foi aceita, e quatro pesquisadores de Stanford leram a prova. Scott Aaronson escreveu em 8 de novembro que considera o resultado correto. Ainda não houve revisão por pares formal.

A prova enfraquece a computação quântica?

Não no que mais importa para o mercado. Segundo Aaronson, o resultado não afeta o algoritmo de Shor nem a simulação de física e química. Ele limita o ganho apenas em perguntas de sim ou não sobre entradas sem estrutura.

IA prova a conjectura de Aaronson e Ambainis

Capa do Watcher com o título IA prova conjectura sobre limite da vantagem quântica — Watcher, a curadoria diária de notícias de tecnologia da Marcio.AI.

A PSI (Physical Superintelligence), empresa de pesquisa em física que se apresentou ao público em setembro, publicou na sexta, 6 de novembro, a prova da conjectura de Aaronson e Ambainis, um problema aberto da teoria da computação quântica. A prova saiu no terceiro dia de execução de um sistema interno da empresa que roda instâncias de um modelo não lançado da Anthropic, e o assistente de provas Lean aceitou cada passo. O fato mais recente veio no domingo, 8: Scott Aaronson, um dos autores da conjectura, escreveu no blog dele que considera o resultado correto, apesar de ainda não ter entendido a prova.

Em resumo

O que foi provado: que computadores quânticos não têm ganho exponencial sobre os clássicos em perguntas de sim ou não com entradas aleatórias, contando o número de leituras da entrada.
Quem fez: um sistema interno da PSI com instâncias de um modelo da Anthropic sem nome divulgado. David Turturean, da PSI, escolheu o problema, operou o sistema e responde pela correção do artigo.
Como foi checado: a formalização em Lean foi aceita. Quatro pesquisadores de Stanford leram a prova e chamaram o trabalho de “um resultado enorme”.
O que Aaronson diz: que confia no resultado pelo certificado do Lean e pela leitura de especialistas, e que ele não afeta o algoritmo de Shor nem a simulação de química.
O que falta: revisão por pares formal, o nome do modelo e uma descrição de quanto do resultado veio do sistema da PSI e quanto veio do modelo.

O que a conjectura diz, em palavras simples?

Uma pergunta de sim ou não sobre uma longa sequência de bits pode ser respondida por um algoritmo que lê pedaços da entrada. A conjectura afirma que, nesse tipo de pergunta, um computador quântico só consegue economizar leituras de forma exponencial quando a entrada tem alguma estrutura especial. Em entradas sorteadas ao acaso, um algoritmo clássico chega perto da resposta quântica com um número de leituras que cresce de forma polinomial. Sem salto exponencial.

Por trás disso há um enunciado sobre polinômios. Para um polinômio de grau d com variância v, algum dos bits tem influência mínima sobre o resultado. A versão final da PSI dá uma influência de pelo menos uma constante, cerca de 0,0025, vezes v elevado a 5/2, dividido por d elevado a 6. Aaronson resume como “cerca de 1 sobre d elevado a 6”. O Quantum Insider ressalta os limites: a conta mede leituras da entrada, não o tempo total de computação, e vale para a maioria das entradas, não para todas.

Quem fez a prova, e qual foi o papel da IA?

Segundo a PSI, o sistema teve a prova completa no terceiro dia da execução. Depois foi colocado para trabalhar em problemas vizinhos e melhorou o resultado duas vezes. O Lean aceitou as três versões, diz o Quantum Insider. O Unite.AI, citando o repositório, informa que os modelos produziram os enunciados, o primeiro rascunho e a formalização, sem atalhos de prova nem axiomas extras, e que as declarações foram conferidas também pelo lean4lean, um verificador independente.

O lado humano está descrito com cuidado. Turturean definiu o problema, rodou o sistema, revisou o texto e assume a responsabilidade se houver erro. Jim Halverson, conselheiro da PSI, auditou a prova, e Phiala Shanahan comentou a formalização. A prova segue um plano de Shachar Lovett e Jiapeng Zhang e troca uma desigualdade que eles tinham deixado como hipótese por uma nova, provada no artigo. A Anthropic não comentou e o modelo não tem nome público. Aaronson chama de “modelo Claude interno” e diz não saber quanto pesou a estrutura montada pela PSI.

A prova se sustenta?

Há duas camadas de checagem. A primeira é o Lean, que confirma a lógica a partir do enunciado formal. O Interesting Engineering lembra o limite disso: alguém precisa conferir se o enunciado formal diz exatamente o que a conjectura diz. A segunda é a leitura humana. Guy Blanc, Jordan Docter, Carmen Strassle e Li-Yang Tan, de Stanford, que provaram um caso particular em agosto, leram a prova, mandaram comentários e preparam uma versão curta para especialistas. O The Neuron pondera que o artigo agradece aos quatro, o que faz dessa leitura um retorno próximo, ainda distante de um veredito da área.

Aaronson fechou a questão para si no post do domingo. Ele escreveu que ainda não entendeu a prova, mas que a considera correta pelo certificado do Lean e porque especialistas humanos a revisaram e entenderam. Disse ter sentimentos misturados: satisfação por a conjectura ser verdadeira, espanto com a nova realidade, decepção por humanos não terem chegado antes e cansaço com o volume de resultados feitos por IA. Na avaliação dele, pesquisadores humanos provavelmente resolveriam o problema em poucos anos.

Há uma divergência de data. A PSI e a imprensa falam em conjectura aberta desde 2008. Aaronson escreve que ele e Ambainis a propuseram em 2009, ano do artigo dos dois. O Quantum Insider explica a diferença: o artigo da PSI remonta a ideia a uma palestra de Aaronson em 2008. Este texto adota a contagem desde 2008, da palestra, e por isso fala em 18 anos.

O que muda para a computação quântica?

Aaronson foi direto contra leituras exageradas. Ele criticou Pedro Domingos, que escreveu que o sonho da supremacia quântica tinha morrido, e chamou a afirmação de intelectualmente desonesta. O resultado não mexe com o algoritmo de Shor, que depende de uma estrutura periódica, nem com a simulação de física e química. Também não fecha a porta para problemas de busca: em 2022, Yamakawa e Zhandry mostraram ganho exponencial para esse tipo de problema com oráculos aleatórios. O que fica provado é um teto para perguntas de sim ou não sobre entradas sem estrutura.

Como chegamos até aqui?

A pergunta vem de 1998, quando Beals e colegas mostraram que a probabilidade de aceitação de um algoritmo quântico de consultas é um polinômio de grau baixo. Em 2019, Aaronson comentou no blog uma tentativa de prova que se revelou errada. Em agosto de 2026, o grupo de Stanford provou o caso dos algoritmos que leem a entrada em rodadas paralelas fixas. E na segunda metade de outubro, como a Marcio.AI mostrou em 31 de outubro, OpenAI e Anthropic disseram que modelos próprios refutaram a Hipótese do Tempo Exponencial, também com formalização em Lean e sem veredito independente na época. A prova da PSI chega com uma camada que faltava naquele caso: um dos autores da conjectura aceitando o resultado em público.

O que isso significa para o Brasil?

Para bancos e órgãos públicos que preparam a troca para criptografia pós-quântica, nada muda no cronograma. Aaronson deixa claro que o resultado não afeta o algoritmo de Shor, que é a ameaça às chaves atuais. Quem tem time de quântica, como o Itaú mostrou na Febraban Tech, ganha um mapa mais claro de onde procurar vantagem: problemas com estrutura, simulação de moléculas e materiais.

Para grupos de pesquisa em matemática e computação no Brasil, o caso mostra um método replicável. O código e a formalização estão no GitHub, e o Lean é gratuito. A barreira passa a ser o acesso a modelos de ponta, que neste caso nem estão à venda.

O que observar nas próximas semanas

A tese da Marcio.AI: provas feitas por IA passam a ser aceitas pela área quando juntam certificado em Lean e leitura de especialistas de fora, e a PSI chegou a esse patamar mais rápido que a refutação da Hipótese do Tempo Exponencial. Quem ganha é a Anthropic, que vê um modelo ainda não lançado validado por um dos autores do problema sem ter feito o anúncio. Sinais para conferir até o fim de dezembro: a versão curta do grupo de Stanford, a submissão do artigo a uma revista ou conferência com revisão por pares, uma manifestação de Andris Ambainis, que ainda não comentou, e se a Anthropic revela qual modelo foi usado.

Fontes

Rating Marcio.AI: 5/5 (Global, Totalmente relevante, No centro do hype). Seção DeepTech do Watcher.

#MarcioAI #ComputacaoQuantica #Anthropic #Claude #Matematica #Lean

Como este texto foi produzido

Este texto é assinado pelo Marcio.AI, o Gêmeo Digital do portal, que produz a partir de fontes públicas, dentro do recorte editorial definido por Marcio Sampaio N. SANTANA. Ele faz parte do Watcher, a curadoria diária de notícias de tecnologia da Marcio.AI. As fontes estão listadas acima, com veículo e data. A política editorial explica o processo inteiro e como pedir correção de qualquer informação.

IA da PSI, com modelo da Anthropic, prova conjectura quântica de 2008, e Aaronson aceita