Aaronson-Ambainis Proof: AI System Proves 2008 Conjecture

AI for Science · ax-trend issue #3863 · Announced November 6, 2026

Aaronson-Ambainis proved title card

Physical Superintelligence (PSI) announced on November 6, 2026 that it has a proof of the Aaronson-Ambainis conjecture, a quantum complexity problem posed by Scott Aaronson and Andris Ambainis that had been open since 2008. PSI says the proof was found by a research system it developed internally, running an instance of an undisclosed Anthropic model. The system produced a complete proof on the third day of the run, and the proof assistant Lean accepted the formal version.

That combination is what makes the claim checkable in a way most AI research announcements are not. The paper manuscript and the Lean 4 formalization are public, according to Unite.ai reporting, so anyone can rerun the machine check. The limits are just as clear. Peer review is not finished, and the model behind the run has not been named, so the result cannot be reproduced end to end even though its central artifact can be verified.

Conjecture open since, posed by Aaronson and Ambainis2008
Complete proof produced on run dayDay 3
Core constant c = 815/(125π^4), approximate value0.0025
Formal verification statusLean accepted

The Conjecture and Quantum Advantage Limits

The Aaronson-Ambainis conjecture draws a boundary around quantum speedup. It asks whether a quantum computer can be exponentially faster than a classical computer on random inputs. If the conjecture holds, it cannot: on inputs with no structure, a quantum advantage stays at polynomial level at most. The dramatic speedups people know, such as the factoring method Peter Shor published in 1994, appear when the input hides a repeating structure that a quantum algorithm can exploit.

Read that way, the proof does not weaken quantum computing. It sharpens the map of where large quantum advantages can and cannot live. Problems with exploitable structure remain open territory, while unstructured search gets a firmer ceiling. For researchers choosing where to look for the next algorithmic breakthrough, that boundary is practical information, not just theory.

The result also did not arrive in one jump. In August 2026, a Stanford team of Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan solved a special case of the conjecture first. PSI says the Stanford team has since read the full proof, sent comments, and is writing a short explainer for experts. That sequence matters because the special case gave the field a partial foothold months before the general claim appeared.

Proof Strategy and the All-Pairs Inequality

Diagram from the 2008 conjecture through the Lovett and Zhang plan and the PSI system run to Lean acceptance
The path from the 2008 conjecture to a Lean-checked proof, as reported by Physical Superintelligence.

The proof strategy follows a plan by Shachar Lovett and Jiapeng Zhang. Their plan left one inequality as a conjecture of its own, and PSI says its proof replaces that step with a new all-pairs inequality. The central bound is Infi(f) ≥ c v5/2 / d6 ≥ (v/d)7, where the constant c is 815/(125π4), about 0.0025. In plain terms, the new inequality is the load-bearing step: swap it in, and a plan that had been stuck at an unproven step becomes a complete argument.

PSI says it then applied the system to related open problems and that the results improved twice, with the final version also passing Lean verification. The announcement does not turn that follow-up work into a benchmark, and no run logs, prompts or model details have been published. The honest reading is narrow: one well documented proof claim, plus a company statement that the same system kept producing improved results afterwards.

Research System, Contributors and Public Artifacts

David Turturean developed the research system and led the run. Jim Halverson audited the proof, and Phiala Shanahan gave input on the Lean formalization. Naming those roles helps a reader judge the claim, because the human work here is specific: system building, proof auditing and formalization advice are three different checks, and each one is attached to a person.

The artifacts are the other half of the credibility case. A manuscript and a Lean 4 formalization that outsiders can run are stronger evidence than a press release alone, and they set a useful standard for AI generated mathematics. A claim of this kind can now ship with a machine checkable object, and readers can reasonably start expecting one.

Verification Limits and Peer Review Status

The caveats are concrete. Peer review is not finished, so the current status is a company announcement backed by verifiable artifacts, not a settled journal result. Lean accepting a formalization proves that the formal statement follows from its premises. It does not by itself prove that the formal statement is the same statement Aaronson and Ambainis posed, and checking that match is still human work for the reader. The paper text itself has not been machine verified.

Reproducibility has a second gap. The Anthropic model used in the run is undisclosed, and Anthropic did not respond to a request for comment, according to Business Insider reporting cited in coverage of the announcement. Nobody outside PSI can rerun the discovery process, only the verification step. My read is that this split will become normal for AI research systems: discovery stays private and hard to audit, while verification goes public. That makes the quality of the public artifacts the whole ballgame, and it is why the Lean files matter more than the announcement itself.

Related Reading

For another approach to machine checked claims from AI systems, see the report on FlashProve and provable inference for LLMs.

FAQ

What is the Aaronson-Ambainis conjecture?

It is a quantum complexity problem posed by Scott Aaronson and Andris Ambainis that had been open since 2008. If it holds, a quantum computer cannot gain an exponential advantage over a classical computer on inputs with no structure, and any advantage stays at polynomial level.

Who produced the proof?

Physical Superintelligence says its internal research system produced the proof, running an instance of an undisclosed Anthropic model. The system produced a complete proof on the third day of the run, and David Turturean developed the system and led the run.

Does Lean verification settle the claim?

Not on its own. Lean accepted the formalization, but the paper text itself was not machine checked, and readers still need to confirm that the formal statement Lean checked matches the original conjecture. Peer review is also still pending.

Which Anthropic model was used?

That is undisclosed. Physical Superintelligence has not named the model, and Anthropic did not respond to a request for comment reported by Business Insider.

Sources

AI for ScienceFormal VerificationQuantum CircuitsAnthropicAX Trend