AI Proves 2008 Aaronson-Ambainis Quantum Conjecture Using Unpublished Anthropic Model

Conjecture and Its Significance

The 2008 Aaronson-Ambainis conjecture distinguishes two classes of Boolean functions. One class contains hidden periodic structure — exemplified by Peter Shor's 1994 factoring algorithm — where quantum computers achieve exponential speedup. The other class consists of essentially random inputs lacking such structure. The conjecture asserts that for random-input decision problems, a quantum computer can query the input at most polynomially fewer times than a classical computer; it cannot achieve an exponential reduction in query complexity.

New Bound and Improvement Over Prior Work

The proof establishes a concrete polynomial bound: the average squared change in acceptance probability when flipping any single input bit is at least (variance / degree)^7 times a constant factor. The constant is approximately 0.0025 , exactly 8√15 / (125π⁴). Previous bounds for general polynomials degraded exponentially with the degree; this result replaces that exponential dependence with a fixed 7th-power polynomial.

AI-Driven Proof Process

Physical Superintelligence (PSI) ran their research system on proprietary hardware. On the third day, the system produced a complete proof, which the Lean proof assistant accepted after two subsequent improvements. David Turturean architected the system, selected the problem, and oversaw the run; he also reviewed the generated paper draft for correctness. Jim Halverson reviewed the mathematical proof, and Phiala Shanahan reviewed the Lean formalization.

Formal Verification in Lean

The Lean formalization contains no sorry placeholders and introduces no extra axioms beyond Lean's standard three axioms. Two independent Lean kernels have verified the proof. The repository (https://github.com/physical-superintelligence/aaronson-ambainis) provides Lean source files, scripts, and documentation under Apache 2.0; the paper itself remains under author copyright. The formalized statement PrintedConjecture is claimed to match the original 2008 conjecture, but the repository notes that readers must confirm this correspondence themselves.

Context and Related Work

In August 2026, Stanford researchers (Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan) proved a special case of the conjecture covering fixed-round parallel queries, showing no exponential quantum speedup under that restricted query model. The Stanford team has since examined the full PSI proof, offered feedback, and is preparing a shorter expository write-up for experts.

Implications for Quantum Speedup Claims

The result cleanly separates the landscape: for decision problems on random strings, classical computers can simulate quantum acceptance probabilities within polynomial query overhead, with both error and exception probability bounded by predetermined constants. Exponential quantum speedups (like Shor's) require inputs that hide rare periodic structure — a property absent from random instances.

References

PSI research page: https://psi.inc/research/aaronson-ambainis/

GitHub repository: https://github.com/physical-superintelligence/aaronson-ambainis