Scott Aaronson confirms AI proved the Aaronson-Ambainis conjecture, 16 years after it was posed
IgorCarron · x · 2026-11-09
Scott Aaronson confirmed on his blog that the Aaronson-Ambainis conjecture, posed with Andris Ambainis in 2009, has been proved — by AI. He expressed surprise it was absent from OpenAI's "Mathocalypse" dump a few weeks earlier.
The conjecture states that every bounded degree-d polynomial p:{0,1}^n→[0,1] with constant variance has some variable with influence at least 1/poly(d). Its significance: it rules out superpolynomial quantum query advantage over classical on most Boolean inputs, closing the door on separating P from BQP relative to a random oracle and answering a 1998 question of Fortnow and Rogers. The framework builds on Beals et al. (1998), showing quantum algorithm acceptance probabilities are real polynomials of degree at most 2T. Another longstanding open problem in quantum computing theory to fall to AI.
More from AGI Musings
- AI safety talent surge debated: is METR's hiring boom really field-wide growth? — austinc3301 · 2026-11-09
- Gary Marcus: soaring costs of incremental AI gains point to a looming bubble burst — GaryMarcus · 2026-11-09
- Open source is easy to start but hard to polish: the real cost is mental endurance — yangyi · 2026-11-09
- AI era favors broad intermediate skills over maxed-out skill trees, argues dev — zack_overflow · 2026-11-09
- Hot take: speeding up individual AI researchers is a weak metric as big labs fight over compute — ZhongRuiqi · 2026-11-09
- Are faster AI researchers a good progress metric? One researcher argues no — ZhongRuiqi · 2026-11-09