AI Proves the Aaronson-Ambainis Conjecture, Another Longstanding Quantum Theory Open Problem Falls
ns123abc · x · 2026-11-09
Theoretical computer scientist Scott Aaronson announced on his blog that AI has proven the Aaronson-Ambainis Conjecture, which he posed with Andris Ambainis in 2009: every bounded degree-d polynomial on n Boolean variables with constant variance has some variable with influence at least 1/poly(d).
What the result means:
- It rules out a class of potential quantum speedups most researchers never believed existed—no superpolynomial quantum-over-classical query advantage for decision problems on most Boolean inputs
- In complexity-class terms, this closes off hope of separating P from BQP relative to a random oracle, answering a 1998 question of Fortnow and Rogers
Aaronson's "for dummies" version stresses this does not kill quantum supremacy or change how quantum computers are built. He also notes that longstanding open problems in math and theoretical CS are now dropping to AI at a pace he can't keep up with in blog posts.
Related event: AI Proves Aaronson-Ambainis Conjecture in Quantum Computing(3 posts)→
More from AGI Musings
- Andreessen: AI-native startups vs incumbents is 'widest gap' he's ever seen — ai · 2026-11-10
- OpenAI's Job Transition Framework adopted by Philadelphia Fed and World Bank to map AI job risk — soumitrashukla9 · 2026-11-10
- Vonnegut's 'buying one envelope' quote goes viral in AI circles: 'we're dancing animals' — msfeldstein · 2026-11-10
- Survey: a monitor-controller-mechanism framework for meta-reasoning in LRMs — kalyan_kpl · 2026-11-10
- Justine Bateman pushes back on tech bros' AI predictions: 'They can't predict our future' — GaryMarcus · 2026-11-10
- Environmental groups are using AI to fight wildfires and protect species — castrotech · 2026-11-09