An AI research system has proved a quantum computing conjecture that stood open for 18 years, according to Physical Superintelligence (PSI), the startup behind the work. The Aaronson-Ambainis conjecture, posed in 2008 by computer scientists Scott Aaronson and Andris Ambainis, is now a theorem, PSI said in a research post published on November 6, 2026.
The proof was found by a research system PSI developed internally, running instances of a non-public Anthropic model on the company’s own infrastructure. PSI says the system had a complete proof during the third day of the run, and that Lean, a proof assistant that checks every step by computer, accepted it. The team then pointed the system at related open problems, improved the result twice, and Lean accepted the final version.
What Was Announced?
The conjecture concerns a basic question in quantum computing: when can a quantum computer be exponentially faster than an ordinary one? The dramatic quantum speedups known so far, including Peter Shor’s 1994 algorithm for factoring large numbers, rely on structure, a hidden repeating pattern in the input. Whether quantum computers can be exponentially faster on random inputs, which almost never have such structure, was unknown.
Aaronson and Ambainis found a way to settle the question 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. Researchers have counted the conjecture among the central open problems of quantum complexity theory.
PSI says its proof follows a plan laid out by Shachar Lovett and Jiapeng Zhang, replacing one inequality they had left as a conjecture with a new inequality proved in the manuscript. The final result states that some bit has influence of at least c times v to the power 5/2 divided by d to the power 6, where c is about 0.0025, a bound that is at least (v/d) to the power 7. In practical terms, an ordinary computer can predict a quantum computer’s yes or no answer, up to a small error, for all but a small fraction of inputs, using a number of looks that grows only as a fixed power of the quantum computer’s looks, not exponentially.
IBM Q System One quantum computer installation. Image: IBM Research, via Wikimedia Commons (CC BY 2.0).
Why It Matters
The result sharpens the boundary between quantum and classical computing. On yes or no questions about random strings, a quantum computer cannot save exponentially many looks unless the string has a rare pattern. That conclusion matters for how researchers think about where quantum advantage can realistically appear, and it gives the field a concrete, machine-checked result rather than a claim to take on trust.
The work also lands as a milestone for AI-led science. The system did not merely assist with a calculation, it produced a full proof of a problem that had resisted human mathematicians for nearly two decades, and the proof was verified step by step by Lean. David Turturean, a member of PSI’s technical staff, led the work: he developed the research system, scoped the problem, ran it, and reviewed the draft paper. Jim Halverson, an advisor, audited the proof, and Phiala Shanahan, also an advisor, commented on the Lean formalization.
From conjecture to theorem: 18 years. Source: PSI (psi.inc), November 6, 2026.
What Still Needs Checking
The claim comes with honest limits. The paper has not yet undergone journal peer review, and neither Scott Aaronson nor Andris Ambainis has publicly assessed the proof. Anthropic has not confirmed which non-public model was used. PSI says both the manuscript and the Lean formalization are public, so independent mathematicians can examine them directly.
That scrutiny has already begun in part. In August 2026, Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan of Stanford University settled the conjecture’s prediction in a special case, proving there is no exponential speedup on random inputs for quantum algorithms that look at their input in a fixed number of parallel rounds. PSI says the Stanford researchers have been reading its proof of the full conjecture, have sent comments, and are writing a shorter exposition of it for experts. They wrote to PSI:
“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.”
As PSI put it in its announcement: “Quantum computing still has plenty of mysteries, but now there is one fewer.”
