The Aaronson-Ambainis conjecture asserts that a bounded low-degree polynomial on the Boolean cube with appreciable variance has an influential coordinate (Aaronson and Ambainis 2014). In the convention, take and let have degree at most . The degree is the total degree of the unique multilinear polynomial representing . If has the discrete uniform distribution on the cube and reverses coordinate , the coordinate influence is

where denotes the expectation value. The sum of the coordinate influences is the total influence. The conjecture asks for a lower bound on that is a fixed positive power of , up to an absolute constant. Here is the variance of under the discrete uniform distribution on the cube.

Turturean (2026) reports the bound

A nonpublic Anthropic model in a research system developed at Physical Superintelligence generated the proof and its Lean formalization. The project reports Lean and Nanoda checks of the influence statements (Physical Superintelligence 2026). Blanc et al. (2026) present a weaker quantitative bound in an exposition of Turturean's proof.

The influence bound has an application to query complexity. For a decision procedure with quantum access to its input bits, a deterministic classical algorithm can approximate its acceptance probability on at least a fraction of inputs under the discrete uniform distribution, for fixed error tolerance and fixed . The number of queries is polynomial in the quantum query complexity (Aaronson and Ambainis 2014).

See also

Boolean Fourier Expansion, Query Complexity, Total Influence

Explore with Wolfram|Alpha

References

Aaronson, S. and Ambainis, A. "The Need for Structure in Quantum Speedups." Theory Comput. 10, 133-166, 2014. https://doi.org/10.4086/toc.2014.v010a006.Blanc, G.; Docter, J.; Strassle, C.; and Tan, L.-Y. "Proof of the Aaronson-Ambainis Conjecture: An Exposition." Nov. 7, 2026. https://guyblanc.github.io/AA_Exposition.pdf.Physical Superintelligence. "A Proof of the Aaronson-Ambainis Conjecture." Lean source and reproducibility materials. Nov. 6, 2026. https://github.com/physical-superintelligence/aaronson-ambainis/tree/2a6ceaef872ae993708950f951989134084b851a.Turturean, D. "A Proof of the Aaronson-Ambainis Conjecture." 6 Nov 2026. https://arxiv.org/abs/2611.09773v1.

Cite this as:

Weisstein, Eric W. "Aaronson-Ambainis Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Aaronson-AmbainisConjecture.html

Subject classifications