An AI System Has Proved a Quantum Puzzle Open Since 2008 — and a Computer Checked Every Step
Some maths problems stay open for decades. The Aaronson–Ambainis conjecture, posed in 2008 by Scott Aaronson and Andris Ambainis, is one of the central open problems of quantum computing — and on 6 November 2026, Physical Superintelligence (PSI) announced that a research system it built, running a non-public Anthropic model, had found a complete proof.
The system had the proof during the third day of its run. Then came the part that makes this story different from an ordinary announcement: the proof was checked by Lean, a proof assistant in which a computer verifies every single step. Lean accepted it. The team then set the system on related open problems, improved the result twice, and Lean accepted the final version too.
The question: when can quantum computers be dramatically faster?
In 1994, Peter Shor found a quantum algorithm that factors large numbers far faster than any known method for ordinary computers. It works because the problem hides a repeating pattern, and the quantum computer finds how often it repeats. Like most dramatic quantum speedups known, Shor's algorithm relies on structure: a promise that the input has a rare pattern.
The open question was whether quantum computers can be exponentially faster on random inputs — inputs that almost never have such a pattern. Aaronson and Ambainis found a way to settle this with pure mathematics. They stated a conjecture about polynomials, and showed that if it is true, quantum computers are at most polynomially faster on random inputs — faster, but not dramatically so.
Now that the conjecture is proven, we know that on yes-or-no questions about random strings, a quantum computer cannot save exponentially many steps unless the string has a rare pattern. Quantum computers still have plenty of mysteries, but now there is one fewer.
Why the checking matters
A proof written by an AI system raises an obvious question: how do we know it is right? That is where Lean comes in. Lean does not take anyone's word for it — it checks every logical step mechanically. The manuscript and the Lean 4 formalisation are public on GitHub, so other mathematicians can inspect them.
There are still caveats, and PSI states them openly. The result is not yet peer-reviewed, and human experts still need to confirm that the formal statement proved in Lean matches the conjecture exactly as Aaronson and Ambainis meant it. A team at Stanford University — Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan — had settled the conjecture's prediction in a special case in August 2026. They have been reading the new proof, have sent comments, and are writing a shorter exposition of it for experts. They called it "a huge result" that "resolves a decades-old conjecture with important implications for the nature of problems that admit quantum speedups."
What this means for students
For students, two lessons stand out. First, the maths itself: a question about futuristic computers turned out to be a question about polynomials — the same kind of expressions students meet at GCSE and A-level. Second, the method: the proof was found by a machine, but it was trusted because a second machine checked every step. In mathematics, the argument is only as good as its verification.
If your child enjoys maths puzzles, or wonders what quantum computers can and cannot do, a first lesson in maths can start with this 18-year-old puzzle and end with why a proof is only finished when someone — or something — has checked every step. Book your first lesson
Sources:
- Physical Superintelligence, "A proof of the Aaronson-Ambainis conjecture", 6 November 2026: https://psi.inc/research/aaronson-ambainis/
- Simple AI Explain, "An AI Solved an 18-Year Math Problem in 3 Days", 6 November 2026: https://simpleaiexplain.com/2026/11/06/an-ai-solved-an-18-year-math-problem-in-3-days/
London Tutors — post your tutoring request and we will match you with a verified tutor.