PSI says its system found a Lean-checked proof of the Aaronson-Ambainis conjecture
Physical Superintelligence PBC posted on X on 6 November 2026: "Today Physical Superintelligence PBC is announcing a proof of the Aaronson-Ambainis conjecture, one of the central open problems in quantum complexity, with major implications for quantum computing speedup." The verified @psipbc account is the company's primary public statement so far.
David Turturean, who the company later credits with leading the work, wrote on X: "A research system I built for @psipbc, using a non-public Anthropic model, has proved the Aaronson-Ambainis conjecture! Open since 2008..." Photon Dispatch treats that wording as his account of the run, consistent with the company page.
Company research page (PSI's claim). On the same day PSI published A proof of the Aaronson-Ambainis conjecture, dated 6 November 2026. According to that page, an internal research system running instances of a non-public Anthropic model on PSI infrastructure produced a complete proof on day three of a run; Lean accepted it; the system later improved the result twice, with Lean accepting the final version. PSI says the proof builds on ideas from Shachar Lovett and Jiapeng Zhang, David Reimer and others. Those steps, the Lean acceptance claim and the mathematical details are PSI's own account. Independent peer review of the full manuscript may still be pending.
What PSI says the result would mean. PSI frames the Aaronson-Ambainis conjecture as addressing whether quantum computers can be exponentially faster than classical ones on random inputs that lack rare structure. The company says that, with the conjecture proved, an ordinary computer can predict a quantum computer's yes/no answer probability (up to small error, for all but a small fraction of strings) with a number of looks that grows at most like a fixed power of the quantum look count T—not exponentially. In PSI's words, on yes-or-no questions a quantum computer cannot save exponentially many looks unless the input has a rare pattern. That implication is stated by PSI; outsiders should wait for independent verification before treating it as settled mathematics.
Stanford group reading the proof. PSI says Guy Blanc, Jordan Docter, Carmen Strassle and Li-Yang Tan of Stanford, who in August 2026 settled a special case of the conjecture's prediction for algorithms with a fixed number of parallel rounds, have been reading the full proof, sent comments and are writing a shorter exposition. PSI quotes them as writing: "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." The quote appears on PSI's page; Photon Dispatch has not independently confirmed the Stanford correspondence beyond that posting.
Contributors named by PSI. The page credits David Turturean with leading the work (research system, problem scoping, run, draft packaging and responsibility for correctness); Jim Halverson with auditing the proof; and Phiala Shanahan with comments on the Lean formalization.
What to watch. A publicly posted Lean formalization, an arXiv or journal manuscript, and independent expert write-ups (including any Stanford exposition) would let outsiders check the claim beyond the company announcement. Until then, the story rests on PSI's X post, Turturean's X post and PSI's research page.
DeepMind and Google Quantum AI later described using Lean 4 to discover formally verified quantum algorithms.
