Aaronson-Ambainis Conjecture proved — by AI, Scott Aaronson announces
fortnow · x · 2026-11-10
Scott Aaronson announces on his blog that the Aaronson-Ambainis Conjecture, posed with Andris Ambainis in 2009, has been proved — with AI's help — in a new exposition by Guy Blanc, Jordan Docter, Carmen Strassle, and Li-Yang Tan.
Key takeaways from his "For Dummies" version:
- An AI did solve a major open problem in quantum computing theory.
- But it doesn't kill quantum supremacy or change how quantum computers are built.
- It rules out a class of quantum speedups most complexity theorists never believed in: superpolynomially faster quantum query algorithms for yes/no properties of exponentially many random bits.
- The conjecture: every degree-d polynomial over n Boolean variables with constant variance has a variable with influence at least 1/poly(d), implying no superpolynomial quantum query advantage for decision problems.
Aaronson notes long-standing open problems are now "dropping like flies," jokes his prediction was right, and recalls a 2019 attempted proof that turned out fallacious.
Related event: AI Proves the 16-Year-Old Aaronson-Ambainis Conjecture(5 posts)→
More from AGI Musings
- "Pure FAKE": X User Rants Against AI Romance and Simulated Consciousness — ryunuck · 2026-11-10
- Under-30 Americans use chatbots most, yet only 14% expect AI to benefit society — PeterDiamandis · 2026-11-10
- Non-verifiable domains aren't safe harbors — agents make effort free — generativist · 2026-11-10
- Rasmus Andersson's 'software should feel like home, not a hotel' take sparks debate — round · 2026-11-10
- Non-verifiable Domains Aren't Human Safe Harbors — Agents Supply Effort for Free — burny_tech · 2026-11-10
- SOTA podcast: CMU professor on why you shouldn't just trust your agents — niloofar_mire · 2026-11-10