A research system developed by the startup Physical Superintelligence, using instances of a non-public Anthropic model, has produced a complete proof of the Aaronson-Ambainis conjecture, a mathematical problem that had stood open since 2008 and concerns when quantum computers can achieve exponential advantages over classical machines. The proof was accepted by the Lean proof assistant, according to a paper posted publicly by the company.
The result, first reported by The Quantum Insider and covered by Business Insider, is being described by independent researchers as a landmark for AI-assisted mathematics — and one of the most consequential outputs yet attributed to a frontier model that has never been released to the public. For more context on this story, see our ongoing AI news.
What the Conjecture Says
Scott Aaronson and Andris Ambainis posed the question in work tracing back to a 2008 lecture by Aaronson: can a quantum algorithm still gain an exponential advantage when the input it receives has no structure to exploit? The best-known quantum speedups, like Peter Shor's 1994 factoring algorithm, work because their inputs carry repeating patterns the algorithm can exploit. The Aaronson-Ambainis question addresses the opposite case — uniformly random, unstructured inputs where such patterns are absent.
To study the question, researchers use the query model, which counts how often an algorithm accesses its input rather than every operation it performs. A classical algorithm reads one bit per query, while a quantum query can act on a superposition of many input positions at once. Aaronson and Ambainis conjectured that every bounded low-degree polynomial — the mathematical object that describes a quantum algorithm's output probability after a given number of queries — must have a highly influential variable.
If true, the conjecture implies that a quantum algorithm making T queries can be simulated by a classical algorithm making only polynomially many queries on most inputs, ruling out exponential speedups for unstructured problems. The conjecture was proved assuming a formal statement about polynomials, but the statement itself had resisted proof for 18 years.
How the Proof Was Found
According to PSI's blog post and the accompanying paper, the research system produced a complete proof during the third day of a run on PSI's own infrastructure. The main theorem and its formulation of the original conjecture were formalized in Lean 4, and Lean's kernel — the software component that mechanically verifies every logical step — accepted the proof. PSI then assigned the system related open problems, which led it to strengthen the result twice before the final version was accepted.
The repository's recorded audit states that the formal development contains no proof placeholders and no added axioms. The declarations were replayed through Lean's kernel and through lean4lean, an independent implementation of Lean's type checker, and a comparator using both kernels accepted the four final theorems. In a control test on a second machine, the comparator accepted one correct small solution and rejected four deliberately wrong ones.
The proof follows a strategy laid out by mathematicians Shachar Lovett and Jiapeng Zhang, based on fractional certificates and level sets, but replaces an inequality their plan had left as a conjecture with a new all-pairs inequality built on a determinant-generated pairing of input settings — a construction PSI says goes beyond David Reimer's earlier Butterfly Lemma.
Human Oversight and Verified Limits
David Turturean, a member of PSI's technical staff, developed and ran the research system, scoped the problem, prompted the model to package a first draft, and reviewed that draft; the repository names him as responsible for the paper's correctness. Jim Halverson audited the proof, and Phiala Shanahan commented on the formalization. The repository discloses that AI models produced the mathematical statements, the first draft, and the Lean formalization.
The verification also has explicit limits, which PSI's paper acknowledges. A human reader must still confirm that the formal statement in Lean matches the printed conjecture, and the human-readable paper is not itself machine-checked. Lean's kernel, the Mathlib library's definitions, and the machines used for checking remain part of the trusted base.
Expert Reaction
The announcement follows an August 2026 paper by Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan, which settled the classical-simulation consequence for parallel quantum algorithms — a partial result that stopped short of the full conjecture. According to PSI, all four researchers have been reading the complete proof, have supplied comments, and are preparing a shorter exposition aimed at experts.
In their assessment published by PSI, the researchers wrote: "This is a huge result. It resolves a decades-old conjecture with important implications for the nature of problems that admit quantum speedups. The proof draws on and extends several lines of work in the analysis of boolean functions and probabilistic combinatorics. Everything is brought together in a rather magical way."
What It Means for Quantum Computing
For quantum computing research, the theorem sharpens the boundary between problems where quantum machines can help and problems where they cannot. It directs algorithm designers toward problems whose mathematical or physical structure offers genuine advantages, rather than searching for speedups on generic inputs. The result does not, however, determine which real-world applications will deliver useful speedups, and the query model does not account for all the work needed to process data, so it establishes no general limit on total computing time or on the commercial value of quantum machines.
The manuscript and its Lean 4 formalization are public on GitHub, where the community can now attempt to verify the match between the formal statement and the original conjecture — the remaining step that separates a machine-checked proof from a fully certified one.
For Anthropic, the episode offers a preview of capabilities that have not been released to any API: the model that produced the mathematical statements remains non-public, and the company has not announced when or whether it will ship.
---
Stay Ahead of AIGet the latest AI news, analysis, and breakthroughs — all in one place.
Read more AI news →
