An artificial intelligence system has produced a proof of a quantum-computing problem that mathematicians have been unable to settle since 2008 — and a computer proof checker has accepted every step of it. Physical Superintelligence, known as PSI, announced on November 6 that a research system it built, running instances of a non-public Anthropic model, found a complete proof of the Aaronson-Ambainis conjecture during the third day of a run on the company's own infrastructure.
The system then kept working. PSI set it loose on related open problems, and it improved the result twice, tightening the proof's bound exponent from 22 down to 11 and then to 7. The Lean proof assistant accepted the final version, and PSI has published both for outsiders to re-check.
What the conjecture says about quantum speedups
The Aaronson-Ambainis conjecture is a mathematical statement about polynomials, but its importance is what it implies for quantum computing: when quantum computers can be exponentially faster than classical ones, and when they cannot. If PSI's proof holds, an ordinary computer can estimate a quantum algorithm's probability of answering yes on most inputs, within a fixed margin of error, without exponentially more reads of the input. Superpolynomial quantum speedups on yes-or-no query problems would require structured inputs.
PSI says its proof follows a plan laid out by researchers Shachar Lovett and Jiapeng Zhang, who had left one key inequality unproved. The new paper proves a replacement inequality with an explicit bound. It also builds on work from August, when four Stanford researchers proved there is no exponential speedup on random inputs for quantum algorithms that query in a fixed number of parallel rounds. Those four are now reading PSI's proof and writing a shorter version for experts, according to the company.
How the proof was checked — and its limits
What makes this claim harder to dismiss than a typical AI-generated result is the checking. The repository says the formal development contains no proof placeholders and no added axioms, and its declarations were replayed through Lean's kernel and through lean4lean, an independent implementation of Lean's type checker. In a sandboxed run, a comparator using two independent kernels accepted the four final theorems, and on a second machine it accepted one correct small solution while rejecting four deliberately wrong ones.
But the checks have explicit limits, and PSI's own material states them plainly. A reader must still confirm that the formal statement encoded in Lean matches the conjecture as Aaronson and Ambainis meant it, and the human-readable paper is not itself machine-checked. The result has not been peer reviewed, neither Scott Aaronson nor Andris Ambainis has publicly assessed it, and Anthropic has not confirmed which non-public model was used.
Who built the system — and what comes next
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, reviewed that draft and is named as responsible for the paper's correctness. The repository discloses that AI models produced the mathematical statements, the first draft and the Lean formalization. Jim Halverson audited the proof, and Phiala Shanahan commented on the formalization.
PSI, a public benefit corporation that launched in September with $58 million in seed funding, is one of a growing group of labs betting that AI can do original mathematics rather than just assist with it. The claim follows the release of 722 AI-written mathematics manuscripts by OpenAI in October. Whether it survives expert scrutiny is now the test: the paper and the formalization are public, and independent mathematicians can replay the argument.



