Aaronson–Ambainis conjecture

Problem

Must every bounded low-degree real polynomial on the Boolean cube with non-negligible variance have a variable of inverse-polynomial influence?

Let \(p:\mathbb R^N\to\mathbb R\) be a real multilinear polynomial of degree at most \(d\) satisfying

\begin{equation} 0\leq p(X)\leq 1 \qquad \text{for every }X\in\{0,1\}^N . \tag{1} \end{equation}

For \(i\in[N]\), let \(X^{(i)}\) denote \(X\) with its \(i\)-th bit flipped, and define the influence of the \(i\)-th variable by

\begin{equation} \operatorname{Inf}_i[p] = \mathbb E_{X\in\{0,1\}^N} \left[ \left( p(X)-p(X^{(i)}) \right)^2 \right]. \tag{2} \end{equation}

Define the variance of \(p\) on the uniform Boolean cube by

\begin{equation} \operatorname{Var}[p] = \mathbb E_{X\in\{0,1\}^N} \left[ \left( p(X)-\mathbb E[p] \right)^2 \right]. \tag{3} \end{equation}

Suppose that for some \(\varepsilon>0\),

\begin{equation} \operatorname{Var}[p]\geq\varepsilon . \tag{4} \end{equation}

The Aaronson–Ambainis conjecture asks whether there is a universal constant \(C>0\) such that every polynomial satisfying (1) and (4) has some coordinate \(i\in[N]\) whose influence, as defined in (2), satisfies

\begin{equation} \operatorname{Inf}_i[p] \geq \left(\frac{\varepsilon}{d}\right)^C . \tag{5} \end{equation}

Equivalently, the conjecture asks whether the maximum influence can always be bounded below by a fixed polynomial in \(1/d\) and the variance (3), independently of the ambient dimension \(N\).

Source

Explicitly proposed by Scott Aaronson and Andris Ambainis in Aaronson and Ambainis (2014), Conjecture 1.7, under the name “Bounded Polynomials Have Influential Variables” [AA14]. The related statement asserting polynomial-query classical simulation of a quantum query algorithm on most inputs appears separately as Conjecture 1.5 in the same paper and is explicitly described there as folklore; it should therefore not be attributed as an original Aaronson–Ambainis conjecture. The formulation in the statement above is a self-contained restatement of Conjecture 1.7 rather than a verbatim quotation.

Progress

Beals, Buhrman, Cleve, Mosca, and de Wolf showed that the acceptance probability of a quantum algorithm making \(T\) oracle queries is represented by a real multilinear polynomial of degree at most \(2T\); bounded low-degree polynomials such as those in the statement therefore capture a fundamental aspect of quantum query algorithms [BBCMW01].
Aaronson and Ambainis proposed the influence conjecture under the name “Bounded Polynomials Have Influential Variables” and showed it would imply a strong classical-simulation principle: for every \(T\)-query quantum algorithm and every positive approximation and failure parameters, a deterministic classical algorithm using a polynomial number of queries can approximate the quantum algorithm’s acceptance probability on all but a small fraction of Boolean inputs. The conjecture would thereby formalize that superpolynomial quantum query speedups require substantial promise structure rather than occurring generically on the Boolean cube [AA14].
The influential-variable conjecture should be distinguished from the simulation statement: in the same paper the almost-everywhere classical-simulation statement appears separately as a folklore conjecture, while the influence conjecture is the route Aaronson and Ambainis introduced toward it [AA14].
Bansal, Sinha, and de Wolf proved the desired inverse-polynomial influence bound for completely bounded degree-\(d\) block-multilinear forms with constant variance, giving almost-everywhere classical simulation for a corresponding class of quantum query algorithms including iterated Forrelation; this does not establish the conjecture for arbitrary bounded low-degree polynomials [BSW22].
Bhattacharya proved a partial result via random restrictions: a bounded degree-\(d\) polynomial becomes well approximated by a polynomial-size junta after an appropriate random restriction with high probability, and the Aaronson–Ambainis conclusion holds for a non-negligible fraction of such restrictions under an appropriate variance condition. This establishes additional structure in bounded low-degree polynomials but does not prove the conjecture without restriction [Bhat25].
Blanc, Docter, Strassle, and Tan proved the associated almost-everywhere classical-simulation conjecture for bounded-round quantum query algorithms: a \(t\)-query, \(d\)-round quantum algorithm can be simulated on most inputs using \(t^{O(d^2)}\) classical queries, giving polynomial overhead for constant \(d\). Their result does not prove the influence conjecture for arbitrary bounded polynomials and does not settle the unrestricted adaptive quantum-query simulation problem [BDST26].

Comment

The central unresolved question is whether the dimension-independent influence lower bound in the statement holds for every bounded low-degree polynomial, without additional multilinearity structure, random restriction, or bounded-adaptivity assumptions on the associated quantum query algorithms.

References

[AA14]: Scott Aaronson and Andris Ambainis, “The Need for Structure in Quantum Speedups,” Theory of Computing 10, 133–166 (2014).DOI arXiv
[BBCMW01]: Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf, “Quantum Lower Bounds by Polynomials,” Journal of the ACM 48, 778–797 (2001).DOI arXiv
[BSW22]: Nikhil Bansal, Makrand Sinha, and Ronald de Wolf, “Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms,” in 37th Computational Complexity Conference (CCC 2022), LIPIcs 234, 28:1–28:21 (2022).DOI arXiv
[Bhat25]: Sreejata Kishor Bhattacharya, “Random Restrictions of Bounded Low Degree Polynomials Are Juntas,” in 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), LIPIcs 325, 17:1–17:21 (2025).DOI arXiv
[BDST26]: Guy Blanc, Jordan Docter, Carmen Strassle, and Li-Yang Tan, “Quantum Speedups Require Structure or Depth,” to appear in 67th IEEE Symposium on Foundations of Computer Science (FOCS 2026) (2026).arXiv

Aaronson–Ambainis conjecture

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems