AI System at Physical Superintelligence Cracks an 18-Year-Old Quantum Speedup Question
Physical Superintelligence says an AI research system it built produced a full proof of the 2008 Aaronson-Ambainis conjecture, a limit on quantum speedups, with Lean checking every step and Stanford researchers reviewing the result.
- Published
- Updated
- 2 min read

Physical Superintelligence (PSI) says an AI research system it built produced a complete proof of the Aaronson-Ambainis conjecture, according to the company. The question about the limits of quantum speedups had stood open since 2008. The system ran on PSI’s own infrastructure under researcher David Turturean. It used instances of a non-public Anthropic model and reached the full proof on the third day of the run. Lean, a proof assistant that checks every step of a mathematical argument against formal logic, accepted it.
The conjecture is about yes-or-no decision problems built from randomly chosen inputs, according to Physical Superintelligence. Its proof shows a quantum algorithm cannot gain an exponential edge over a classical one on such unstructured inputs. Doing so would require reading far more of the input data. That is a hard limit on how far quantum speedups can reach when a problem has no exploitable structure to lean on.
That limit is narrower than it sounds. Physical Superintelligence says the proof bounds how many times a classical algorithm must read the input to match a quantum algorithm’s answer on most random inputs lacking a rare pattern. A quantum computer cannot save exponentially many of those reads in that setting. It does not cap the total running time of quantum algorithms generally. Nor does it rule out speedups on practical problems with exploitable structure, such as Shor’s algorithm.
According to Physical Superintelligence, the system’s method was iterative rather than a single leap. It searched prior literature, proposed candidate arguments and tested them against each other. A full proof emerged on that third day. The argument was then translated into Lean and checked by its kernel. PSI had the system improve the proof’s bounds twice more, with Lean accepting each improved version.
The proof now faces outside scrutiny. Physical Superintelligence says Stanford computer scientists Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan have read the proof. They sent comments and are writing a shorter exposition of it for experts. PSI has published the manuscript and the Lean 4 formalisation alongside its research page. The proof has not yet been through peer review.
Sources
MethodologyHow this article was made
- Facts confirmed
- 5 / 5
- Sources
- 2
- Last checked
- Nov 7, 2026
- Image
- Photo
This article was written by an AI system from facts in international trade media, publications by companies and research institutes and public sources, with the source for every fact, and checked under our methodology. The byline is an editorial pseudonym. Found an error? Report it through the contact page.
Facts used
- Physical Superintelligence (PSI) says its researcher David Turturean ran an internal AI research system on its own infrastructure, using instances of a non-public Anthropic model, and the system produced a complete proof of the Aaronson-Ambainis conjecture, a question about quantum algorithms open since 2008, on the third day of the run. The Lean proof assistant, which checks every step of a mathematical argument, accepted the proof. Physical Superintelligence · Nov 7, 2026
- PSI's system searched prior literature, proposed candidate arguments and tested them against each other until a full proof emerged on the third day of the run on PSI's own infrastructure. The argument was translated into the Lean proof assistant and checked by Lean's kernel; PSI then had the system improve the proof's bounds twice more, with Lean accepting each improved version. Physical Superintelligence · Nov 7, 2026
- The conjecture concerns yes-or-no decision problems built from randomly chosen inputs. Its proof implies that a quantum algorithm cannot gain an exponential edge over a classical one on such unstructured inputs without reading dramatically more of the input data, a limit on how far quantum speedups can reach in the absence of exploitable structure. Physical Superintelligence · Nov 7, 2026
- The proof bounds how many times a classical algorithm must read the input to match a quantum algorithm's answer on most random inputs lacking a rare pattern; a quantum computer cannot save exponentially many of those reads on such unstructured inputs. It does not cap the total running time of quantum algorithms or rule out quantum speedups on the many practical problems, such as Shor's algorithm, that do have exploitable structure. Physical Superintelligence · Nov 7, 2026
- Stanford computer scientists Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan have read PSI's proof of the full conjecture, sent comments and are writing a shorter exposition of it for experts; PSI has published the manuscript and the Lean 4 formalization alongside its own research page announcing the result. The proof has not yet been through peer review. Physical Superintelligence · Nov 7, 2026


_2bflou.webp)