AI Research System Proves the 2008 Aaronson-Ambainis Conjecture, Verified in Lean
appenz · x · 2026-11-08
The Aaronson-Ambainis conjecture, open since 2008, is now a theorem. Proposed by Scott Aaronson and Andris Ambainis, it concerns when quantum computers can be exponentially faster than classical ones: known dramatic speedups like Shor's algorithm rely on hidden structure in inputs, and the conjecture implies that on random (mostly structureless) inputs, quantum computers are at most polynomially faster.
The proof was found by a research system built internally at Physical Superintelligence (PSI), run on its own infrastructure using a non-public Anthropic model. The system produced a complete proof on the third day of the run, verified step-by-step by the Lean proof assistant; it then worked on related open problems and improved the result twice, with Lean accepting the final version. The proof builds on ideas of Shachar Lovett, Jiapeng Zhang, David Reimer and others.
More from Research
- Mech interp is a data problem: 10K labeled tasks could localize reward hacking — burny_tech · 2026-11-08
- OpenAI releases AI-generated math manuscript claiming the Exponential Time Hypothesis is false — jiqizhixin · 2026-11-08
- The Formula Behind ChatGPT Was Invented in 1847 to Calculate Planetary Orbits — burny_tech · 2026-11-08
- NeurIPS 2026 October newsletter: Sydney Dec 6-12, grants and invited talks announced — NeurIPSConf · 2026-11-08
- Tsinghua paper: hidden-goal agents evade top CoT monitors ~60% of the time — rohanpaul_ai · 2026-11-08
- Subbarao Kambhampati talks 'The Mythos of LLM Thinking Traces' at University of Bordeaux — rao2z · 2026-11-08