In 1976 Kenneth Appel and Wolfgang Haken announced a proof of the four-color theorem that depended on a computer checking well over a thousand map configurations. Mathematicians argued for years over whether a proof no person could check by hand settled anything. In 2005 Georges Gonthier's team checked the whole proof in the Coq proof assistant, so a machine verified every logical step along with the case analysis. On 6 November 2026 a quantum-computing question reached a similar point with the roles changed: the AI model wrote the proof, Lean checked it, and the step left to people is reading the theorem's statement.
The announcement came from Physical Superintelligence (PSI), which reports that a research system it developed in-house, running instances of "a non-public Anthropic model," had a complete proof of the Aaronson–Ambainis conjecture during the third day of a run on PSI's own infrastructure.
Practical takeaway. Lean has verified that PSI's proof derives its formal theorem from standard foundations. Whether that formal theorem is the conjecture Aaronson and Ambainis stated is left to human readers, and the Stanford group reading it has not yet published its exposition. Nothing in the result alters attack estimates for RSA or elliptic-curve cryptography.
Which question about quantum speedups Aaronson and Ambainis asked in 2008
Peter Shor's 1994 factoring algorithm is fast because the problem hides a repeating pattern that a quantum computer can detect. Most dramatic quantum speedups share that dependence on structure. Scott Aaronson and Andris Ambainis asked what happens when the input has no such pattern: can a quantum computer answer a yes-or-no question about a random string of bits with exponentially fewer looks at the string than a classical computer needs?
Their paper, "The Need for Structure in Quantum Speedups" (first posted to arXiv on 5 November 2009, journal version in Theory of Computing 10 in 2014), turned that question into a statement about polynomials. A result of Beals, Buhrman, Cleve, Mosca and de Wolf shows that a quantum algorithm's probability of answering yes after T looks is a polynomial of degree at most 2T, bounded between 0 and 1. Aaronson and Ambainis conjectured that every such bounded low-degree polynomial with positive variance has an influential variable: a bit whose flipping changes the output by a squared amount that, averaged over uniformly random inputs, is at least a fixed power of the variance divided by the degree. They proved that if the conjecture holds, every T-query quantum algorithm can be simulated on most inputs by a classical algorithm whose number of queries grows polynomially in T.
The problem had a history of near misses. In November 2019 Nathan Keller and Ohad Klein posted a claimed proof. Aaronson's post of 17 November 2019 on that claim now opens with an update: the authors retracted it after Paata Ivanisvili found what looked like a fatal flaw in Lemma 5.3. In August 2026 Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan of Stanford settled the parallel case in arXiv 2608.19158, accepted at FOCS 2026: a quantum algorithm making t queries in d parallel rounds can be simulated on most inputs with tO(d²) classical queries.
What PSI's theorem states and who stands behind the paper
The public repository states the main result as a bound: some variable has influence at least 8√15/(125π⁴) · ε5/2/d6, which is at least (ε/d)7, where ε bounds the variance from below and d is the degree. The constant is about 0.0025. PSI reports that the system improved its first result twice and that Lean accepted the final version. The proof follows a plan of Shachar Lovett and Jiapeng Zhang and replaces the one inequality they left open with a new inequality built on a pairing of points derived from a determinant, related to David Reimer's Butterfly Lemma.
The human responsibilities are set out precisely. David Turturean of PSI built the research system, scoped the problem, had the model package the results into a first draft, reviewed the paper and "is responsible for its correctness." Jim Halverson, an adviser, audited the proof; Phiala Shanahan, another adviser, commented on the Lean formalization. The Stanford group wrote to PSI that "this is a huge result" and is preparing a shorter exposition for experts. No peer-reviewed publication exists yet, and in the sources Quentir checked on 7 November neither Aaronson nor Ambainis had commented on the announcement.
Which checks Lean 4, lean4lean and nanoda ran, and which the repository leaves to a reader
The repository's "Trust boundary" section is the most useful document in the release, because it separates what a machine verified from what it did not. On the verified side, a static audit found no sorry, no added axiom and no native_decide; the four final theorems rest only on Lean's three standard axioms; Lean's own leanchecker replayed every declaration through the kernel; lean4lean, an independent implementation of the Lean type checker, repeated the replays; and the Comparator tool had the proofs replayed by nanoda, a checker written in Rust. The authors also built a control: a small project in which a false statement, added with the kernel switched off, passes lake build and both checkers reject. That control explains why the replays matter more than a green build badge.
On the other side, the repository lists three things the checks do not cover. That the Lean definition PrintedConjecture says what the conjecture says "is for a reader to confirm." The paper is written for humans and is not machine-checked. Lean's kernel, Mathlib's definitions and the machines are trusted. One further detail deserves care in secondary coverage: the fourth theorem, which improves the constant by a factor of four, assumes a result of Agarwal and Ben-David that is not formalized. The headline theorem carries no such hypothesis.
For anyone who has to rely on a result like this, the statement check is the open item. It is a short, finite task: one definition of about fifteen lines, written only with Mathlib notions, set beside Conjecture 1.7 of the 2014 paper. It still needs a qualified person to do it and say so publicly.
Why RSA and elliptic-curve migration timelines are unaffected
The theorem limits quantum speedups on inputs without structure. Shor's algorithm, and every resource estimate for breaking RSA-2048 or the secp256k1 curve, works on structured problems, which the theorem leaves untouched; PSI's announcement draws no cryptographic conclusion. The planning inputs for post-quantum migration remain attack-cost estimates, and those have been moving the other way. Quentir's reading of arXiv 2610.22367, in which Claude Mythos 5 helped design a secp256k1 point-addition circuit, showed AI tools lowering gate counts on that structured side of the problem.
Where the theorem bites is on claims, within clear limits. It concerns query complexity, the number of times an algorithm reads its input, for yes-or-no questions on uniformly random inputs, and it holds for most inputs up to a small error. It sets no general limit on running time and does not by itself classify any real dataset. For a vendor, a grant proposal or a hospital pilot that promises exponential quantum gains on unstructured data, it sharpens the request: name the computational model, the input distribution and the claimed advantage, and show which structure the speedup exploits. Recent serious work already fits this pattern: Quentir's Defense Monitor covered PsiQuantum researchers mapping where elastic-media simulation keeps a quartic quantum advantage, a polynomial gain on a structured physics problem. For patients, investors and public funders, that request is a practical check on quantum machine-learning claims made for clinical or financial records.
How Quentir Reads It
The Aaronson–Ambainis proof divides verification among three parties: the model that produced the argument, the proof assistant that checked the derivation, and the human readers who must confirm the statement. The published argument and its checker replays can be inspected and rerun from a public repository; the run that produced them used a non-public model. For the third, the release documents only that its machine checks exclude statement correspondence and that the Stanford group is reading the proof; it supplies no separate public attestation that the formal statement matches Conjecture 1.7. The 2019 retraction shows expert scrutiny catching an error in a derivation. For this proof Lean performs that part mechanically, while the statement, the unformalized passages of the paper and the trusted foundations remain matters for human judgment.
AI regulation increasingly relies on evaluations and capability claims, and a lab or startup announcing that its model "proved" something invites the same three questions: which formal statement, which checker, and which qualified expert confirmed the match. PSI's README answers the first two in unusual detail and openly leaves the third to others, which is the honest position for a release this new.
Organizations whose security planning depends on the structured side of the problem, where attack costs keep falling, are covered by Signature Report No. 2, the PQC Migration Roadmap, which maps the transition on the finalized NIST standards, sets out what to sequence, and carries an internal-use license for the whole organization. The next development to watch is the Stanford exposition, and whether Aaronson or Ambainis publicly confirm that PrintedConjecture is their Conjecture 1.7.
Sources: Physical Superintelligence, "A proof of the Aaronson-Ambainis conjecture", 6 November 2026; David Turturean (PSI), "A proof of the Aaronson–Ambainis conjecture," paper and Lean 4 formalization, GitHub repository, README sections "Result," "Status," "Trust boundary" and "License and disclosure"; Scott Aaronson and Andris Ambainis, "The Need for Structure in Quantum Speedups", arXiv:0911.0996 (first version 5 November 2009; Theory of Computing 10 (2014), 133–166); Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan, "Quantum Speedups Require Structure or Depth", arXiv:2608.19158, 19 August 2026 (FOCS 2026); Avantika Agarwal and Shalev Ben-David, arXiv:2410.19062; Scott Aaronson, "The Aaronson-Ambainis Conjecture (2008-2019)", Shtetl-Optimized, 17 November 2019, with retraction update; The Quantum Insider, "AI-Assisted Proof Settles Longstanding Question About Quantum Speedups", 6 November 2026; Georges Gonthier, "Formal Proof—The Four-Color Theorem," Notices of the AMS 55(11), 2008. Links checked 7 November 2026.
Published intelligence, built to inform your own decisions. Published: November 7, 2026.