The Aaronson–Ambainis conjecture

The acceptance probability of a quantum algorithm that makes $T$ queries to an $N$-bit input is a polynomial of degree at most $2T$ in the input bits, taking values in $[0,1]$. Aaronson and Ambainis conjectured that every such bounded low-degree polynomial that is not nearly constant has a variable with large influence. If true, every quantum query algorithm could be simulated on most inputs by a classical one with only polynomially more queries, so large quantum speedups would need structure, such as a promise on the input.

Problem

Let $p:\mathbb{R}^N\to\mathbb{R}$ be a real polynomial of degree at most $d$ with

$$0\le p(X)\le 1\qquad\text{for all } X\in\{0,1\}^N .$$

For $X$ uniform on $\{0,1\}^N$, let $\mathrm{Var}[p]=\mathbb{E}\big[(p(X)-\mathbb{E}[p])^2\big]$, and define the influence of the $i$-th variable as

$$\mathrm{Inf}_i[p]=\mathbb{E}\big[(p(X)-p(X^{i}))^2\big],$$

where $X^{i}$ is $X$ with its $i$-th bit flipped.

Conjecture. There is a universal constant $C$ such that whenever $\mathrm{Var}[p]\ge\varepsilon$, some variable has $\mathrm{Inf}_i[p]\ge(\varepsilon/d)^{C}$, independently of $N$.

Background

For total Boolean functions, quantum and classical query complexities are polynomially related, while for problems with a promise on the input the quantum advantage can be enormous [1]. Aaronson and Ambainis posed the conjecture, as "bounded polynomials have influential variables", in a paper first circulated in 2009 and published in 2014 [1]. They showed that it implies a folklore conjecture known since about 1999: for every $T$-query quantum algorithm and every $\varepsilon,\delta>0$, a deterministic classical algorithm making $\mathrm{poly}(T,1/\varepsilon,1/\delta)$ queries approximates its acceptance probability to within $\varepsilon$ on all but a $\delta$ fraction of inputs. It would also mean that one essentially cannot hope to prove $\mathsf{P}\ne\mathsf{BQP}$ relative to a random oracle [1].

What is known

• A theorem of Dinur, Friedgut, Kindler and O'Donnell implies the weaker bound $\mathrm{Inf}_i[p]\ge\varepsilon^3/2^{O(d)}$, so every $T$-query algorithm can be simulated on most inputs with $2^{O(T)}$ classical queries [1]. The conjecture is known when $p$ is Boolean-valued [3].
• In 2019 Keller and Klein posted a proof, then withdrew it after a flaw was found in a key lemma [2].
• Bansal, Sinha and de Wolf proved the conjecture for completely bounded block-multilinear forms with constant variance, giving efficient classical simulation on most inputs for a class of quantum algorithms that includes $k$-fold Forrelation [3].
• Bhattacharya showed that the conclusion holds for a non-negligible fraction of random restrictions of $p$, provided its variance is not too small [4].
• Blanc, Docter, Strassle and Tan proved the simulation statement for parallel algorithms: a $t$-query, $d$-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries (FOCS 2026) [5].
• Girish, Mittal, Nehoran and Raz showed in September 2026 that analogues for biased product distributions and for slices of the cube are equivalent to the original [6].

What would count as progress

• A proof for a class larger than that of [3], for example all polynomials that arise as acceptance probabilities of quantum query algorithms, the case behind the simulation consequence [1, 3].
• A classical simulation with $\mathrm{poly}(t)$ queries for quantum algorithms whose number of rounds grows with the input, improving the $t^{O(d^2)}$ bound of [5].
• A counterexample: explicit degree-$d$ polynomials bounded in $[0,1]$ on the cube, with variance at least $\varepsilon$ and all influences $(\varepsilon/d)^{\omega(1)}$. For small $N$ these properties can be checked exhaustively.

References

1. S. Aaronson and A. Ambainis, "The need for structure in quantum speedups", Theory of Computing 10, 133–166 (2014). doi:10.4086/toc.2014.v010a006
2. N. Keller and O. Klein, "Quantum speedups need structure", preprint (2019), withdrawn. arXiv:1911.03748
3. N. Bansal, M. Sinha and R. 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 (2022). doi:10.4230/LIPIcs.CCC.2022.28
4. S. K. Bhattacharya, "Random restrictions of bounded low degree polynomials are juntas", in 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), LIPIcs 325, 17 (2025). doi:10.4230/LIPIcs.ITCS.2025.17
5. G. Blanc, J. Docter, C. Strassle and L.-Y. Tan, "Quantum speedups require structure or depth", preprint (2026), FOCS 2026. arXiv:2608.19158
6. U. Girish, K. Mittal, B. Nehoran and R. Raz, "Distributional variants of the Aaronson–Ambainis conjecture", preprint (2026). arXiv:2609.35327

Source

Imported from QIQCOP Zoo op_a11fdfadc84e4379, curated by Bikun Li, Qicheng Tang, Changhao Li, Chengkai Zhu, Minbo Gao, Zhong-Xia Shang, Bin Cheng and Naixu Guo. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.