AI System Proves the 18-Year-Old Aaronson-Ambainis Conjecture, Verified by Lean
fortnow · x · 2026-11-07
A major quantum computing milestone: the Aaronson-Ambainis conjecture, open since 2008, has been proven by a research system built at Physical Superintelligence (PSI), using instances of a non-public Anthropic model.
- Why it matters: the conjecture concerns when quantum computers can be exponentially faster than classical ones. Known dramatic speedups like Shor's rely on hidden structure; if the conjecture holds, quantum computers are at most polynomially faster on unstructured random inputs
- Verification: the system produced a complete proof on day three of a run, with the Lean proof assistant checking every step; it then improved the result twice while working on related open problems
- Foundation: builds on prior work by Shachar Lovett & Jiapeng Zhang, David Reimer, and others
- Theorist Lance Fortnow notes he and John Rogers asked a related random-oracle question back in 1998; the new result implies (BQP in Average-P)^R
More from AGI Musings
- Mech interp is a data problem: 10K labeled tasks could localize reward hacking — burny_tech · 2026-11-08
- Gary Marcus calls out Anthropic CEO's AI job-loss claims: 'numbers out of a hat' — GaryMarcus · 2026-11-08
- Australia moves to restrict screens and AI in schools, drawing criticism it will leave kids behind — CtrlAltDwayne · 2026-11-08
- Valuation Guru Damodaran Dismisses 'AI Will Triple GDP' Hype: 40 Years of Data Show No Productivity Gain — GaryMarcus · 2026-11-08
- AI-Generated Resumes Are Flooding the Job Market, Shifting Hiring From Polish to Proof — mdancho84 · 2026-11-08
- Every's Thesis 2027 recap: livestream chat from 15 countries on AI and agency — danshipper · 2026-11-08