Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.09773

A proof of the Aaronson-Ambainis conjecture

David Turturean

Published Nov 6, 2026• 2 citations
arXivHTMLPDF

Abstract

Aaronson and Ambainis conjectured that every bounded polynomial of low degree on the discrete cube has an influential variable. They showed that the conjecture implies that the acceptance probability of every quantum algorithm making $T$ queries can be approximated on most inputs by a classical algorithm making $\mathrm{poly}(T)$ queries. We prove their conjecture: every function $f\colon\{-1,1\}^n\to[-1,1]$ of degree at most $d\ge1$ has a variable of influence at least $c\,\operatorname{Var}(f)^{5/2}/d^{6}$, where $c>0$ is an absolute constant. In the original formulation, for polynomials of degree at most $d$ with values in $[0,1]$ on $\{0,1\}^n$ and variance at least $\varepsilon$, this gives a variable of influence at least $(\varepsilon/d)^{7}$. The proof is elementary, with steps inspired by works of others. Thus, as Aaronson and Ambainis anticipated, superpolynomial quantum speedups in the query model require structure, such as a promise on the inputs.

DOI
10.48550/arxiv.2611.09773

Related papers

Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms

N Nikhil Bansal, M. (Makrand) Sinha, Ronald de Wolf

The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every $d$-query quantum algorithm can be well-approximated almost everywhere (i.e., on almost all inputs) by a $\mathrm{poly}(d)$-query classical algorithm. We prove a special case of the conjecture: in every completely bounded degree-$d$ block-multilinear form with constant variance, there always exists a variable with influence at least $1/\mathrm{poly}(d)$. In a certain sense, such polynomials characterize the acceptance probability of quantum query algorithms, as shown by Arunachalam, Briët and Palazuelos (SICOMP '19). As a corollary we obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms that includes for instance $k$-fold Forrelation. Our main technical result relies on connections to free probability theory.

arXiv:2203.00212•Leibniz international proceedings in informatics•Jan 1, 2022•10 citations

Distributional Variants of the Aaronson-Ambainis Conjecture

Uma Girish, Kunal Mittal, Barak Nehoran +1 more

A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution $μ_p$, where the input bits are independent Bernoulli variables with fixed bias $p$. We show that for every fixed $p \in (0, 1)$, quantum query algorithms under the $μ_p$ distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution $ν_p$ that is uniform over the slice of strings with Hamming weight $\lfloor pn \rfloor$ and prove a similar equivalence for the $ν_p$ distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.

quant-pharXiv:2609.35327•Sep 29, 2026•2 citations

Quantum speedups need structure

Nathan Keller, Ohad Klein

We prove the following conjecture, raised by Aaronson and Ambainis in 2008: Let $f:\{-1,1\}^n \rightarrow [-1,1]$ be a multilinear polynomial of degree $d$. Then there exists a variable $x_i$ whose influence on $f$ is at least $\mathrm{poly}(\mathrm{Var}(f)/d)$. As was shown by Aaronson and Ambainis, this result implies the following well-known conjecture on the power of quantum computing, dating back to 1999: Let $Q$ be a quantum algorithm that makes $T$ queries to a Boolean input and let $ε,δ> 0$. Then there exists a deterministic classical algorithm that makes $\mathrm{poly}(T,1/ε,1/δ)$ queries to the input and that approximates $Q$'s acceptance probability to within an additive error $ε$ on a $1-δ$ fraction of inputs. In other words, any quantum algorithm can be simulated on most inputs by a classical algorithm which is only polynomially slower, in terms of query complexity.

arXiv:1911.03748•Nov 9, 2019•5 citations

Proof of the Aaronson-Ambainis Conjecture: An Exposition

Guy Blanc, Jordan Docter, Carmen Strassle +1 more

We give an exposition of a recent proof of the Aaronson-Ambainis conjecture, which states that every degree-$d$ polynomial $p : \{0,1\}^n \to [0,1]$ has a variable of influence at least $\mathrm{poly}(\mathrm{Var}(p)/d)$. This implies that quantum query algorithms for decision problems can be efficiently simulated classically on most inputs. It also yields a near-equivalence between the status of the $\mathsf{BPP}$ vs. $\mathsf{BQP}$ problem in the random oracle and unrelativized worlds. We organize the proof around four main steps and discuss how each connects to the literature on the analysis of boolean functions and probabilistic combinatorics. To bring out the key ideas, we do not optimize parameters, and our presentation yields weaker exponents than the original. $\textbf{Authors' note.}$ The proof was discovered by David Turturean using a research system developed at Physical Superintelligence (PSI), in combination with a non-public Anthropic model. The proof was then shared with the authors, who worked to understand it and prepare this exposition. Anthropic's public models were used in this process. The authors did not receive financial compensation from Anthropic or PSI. This article is not intended for publication at a conference or in a journal.

arXiv:2611.11626•Nov 8, 2026•0 citations

Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms

Francisco Escudero Gutiérrez, Miquel Saucedo, Carlos Palazuelos

We consider the problem of establishing limitations on the power of quantum query algorithms via the completely bounded polynomial method. In particular, we prove several optimal functional inequalities involving different notions of completely bounded polynomials. These inequalities lead to limiting theorems for the power of quantum query algorithms that improve on prior works. 1. An optimal root-influence bound for block-multilinear polynomials. Prior work showed that block-multilinear polynomials $p$ of degree $t$ satisfy a root-influence bound, $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t^2$, which is stronger than the bound appearing in the Aaronson-Ambainis conjecture. We find the optimal constant in that inequality: $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t$. Since the amplitudes of quantum algorithms that query disjoint blocks of inputs-such as $t$-fold forrelation- are block-multilinear polynomials with $\|p\|_{\text{cb}}\leq 1,$ our inequality shows that they satisfy $t\geq \sum_i\sqrt{\mathrm{Inf}_i[p]}$. We prove that this inequality yields both a more efficient classical simulation than prior results based on the Aaronson-Ambainis argument, and a qualitative improvement: all classical queries are nonadaptive. 2. Optimal Fourier growth of the highest level of quantum query algorithms. We show that for every polynomial $p$ defined on $\{-1,1\}^n$ of degree $2t$, the Fourier Growth at the level $2t,$ namely $\|\widehat p_{2t}\|_{\ell_1}$, satisfies $\|\widehat p_{2t}\|_{\ell_1}\leq (en/(2t-1))^{\frac{2t-1}{2}}\|p\|_{\text{cb}}$. This is optimal up to the factor $e$, as witnessed by $2t$-fold forrelation. As quantum query algorithms that make $t$ queries (to the whole input) satisfy $\|p\|_{\text{cb}}\leq 1$, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).

quant-pharXiv:2609.05201•Sep 7, 2026•2 citations

Aaronson-Ambainis Conjecture Is True For Random Restrictions

Sreejata Kishor Bhattacharya

In an attempt to show that the acceptance probability of a quantum query algorithm making $q$ queries can be well-approximated almost everywhere by a classical decision tree of depth $\leq \text{poly}(q)$, Aaronson and Ambainis proposed the following conjecture: let $f: \{ \pm 1\}^n \rightarrow [0,1]$ be a degree $d$ polynomial with variance $\geq ε$. Then, there exists a coordinate of $f$ with influence $\geq \text{poly} (ε, 1/d)$. We show that for any polynomial $f: \{ \pm 1\}^n \rightarrow [0,1]$ of degree $d$ $(d \geq 2)$ and variance $\text{Var}[f] \geq 1/d$, if $ρ$ denotes a random restriction with survival probability $\dfrac{\log(d)}{C_1 d}$, $$ \text{Pr} \left[f_ρ \text{ has a coordinate with influence} \geq \dfrac{\text{Var}[f]^2 }{d^{C_2}} \right] \geq \dfrac{\text{Var}[f] \log(d)}{50C_1 d}$$ where $C_1, C_2>0$ are universal constants. Thus, Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions of the given polynomial assuming its variance is not too low.

arXiv:2402.13952•Leibniz international proceedings in informatics•Feb 21, 2024•4 citations
Aaronson and Ambainis conjectured that every bounded polynomial of low degree on the discrete cube has an influential variable. They showed that the conjecture implies that the acceptance probability of every quantum algorithm making TTT queries can be approximated on most inputs by a classical algorithm making poly(T)\mathrm{poly}(T)poly(T) queries. We prove their conjecture: every function f ⁣:{−1,1}n→[−1,1]f\colon\{-1,1\}^n\to[-1,1]f:{−1,1}n→[−1,1] of degree at most d≥1d\ge1d≥1 has a variable of influence at least c Var⁡(f)5/2/d6c\,\operatorname{Var}(f)^{5/2}/d^{6}cVar(f)5/2/d6, where c>0c>0c>0 is an absolute constant. In the original formulation, for polynomials of degree at most ddd with values in [0,1][0,1][0,1] on {0,1}n\{0,1\}^n{0,1}n and variance at least ε\varepsilonε, this gives a variable of influence at least (ε/d)7(\varepsilon/d)^{7}(ε/d)7. The proof is elementary, with steps inspired by works of others. Thus, as Aaronson and Ambainis anticipated, superpolynomial quantum speedups in the query model require structure, such as a promise on the inputs.
The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every ddd-query quantum algorithm can be well-approximated almost everywhere (i.e., on almost all inputs) by a poly(d)\mathrm{poly}(d)poly(d)-query classical algorithm. We prove a special case of the conjecture: in every completely bounded degree-ddd block-multilinear form with constant variance, there always exists a variable with influence at least 1/poly(d)1/\mathrm{poly}(d)1/poly(d). In a certain sense, such polynomials characterize the acceptance probability of quantum query algorithms, as shown by Arunachalam, Briët and Palazuelos (SICOMP '19). As a corollary we obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms that includes for instance kkk-fold Forrelation. Our main technical result relies on connections to free probability theory.
A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution μpμ_pμp​, where the input bits are independent Bernoulli variables with fixed bias ppp. We show that for every fixed p∈(0,1)p \in (0, 1)p∈(0,1), quantum query algorithms under the μpμ_pμp​ distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution νpν_pνp​ that is uniform over the slice of strings with Hamming weight ⌊pn⌋\lfloor pn \rfloor⌊pn⌋ and prove a similar equivalence for the νpν_pνp​ distribution and the uniform distribution. The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.
We prove the following conjecture, raised by Aaronson and Ambainis in 2008: Let f:{−1,1}n→[−1,1]f:\{-1,1\}^n \rightarrow [-1,1]f:{−1,1}n→[−1,1] be a multilinear polynomial of degree ddd. Then there exists a variable xix_ixi​ whose influence on fff is at least poly(Var(f)/d)\mathrm{poly}(\mathrm{Var}(f)/d)poly(Var(f)/d). As was shown by Aaronson and Ambainis, this result implies the following well-known conjecture on the power of quantum computing, dating back to 1999: Let QQQ be a quantum algorithm that makes TTT queries to a Boolean input and let ε,δ>0ε,δ> 0ε,δ>0. Then there exists a deterministic classical algorithm that makes poly(T,1/ε,1/δ)\mathrm{poly}(T,1/ε,1/δ)poly(T,1/ε,1/δ) queries to the input and that approximates QQQ's acceptance probability to within an additive error εεε on a 1−δ1-δ1−δ fraction of inputs. In other words, any quantum algorithm can be simulated on most inputs by a classical algorithm which is only polynomially slower, in terms of query complexity.
We give an exposition of a recent proof of the Aaronson-Ambainis conjecture, which states that every degree-ddd polynomial p:{0,1}n→[0,1]p : \{0,1\}^n \to [0,1]p:{0,1}n→[0,1] has a variable of influence at least poly(Var(p)/d)\mathrm{poly}(\mathrm{Var}(p)/d)poly(Var(p)/d). This implies that quantum query algorithms for decision problems can be efficiently simulated classically on most inputs. It also yields a near-equivalence between the status of the BPP\mathsf{BPP}BPP vs. BQP\mathsf{BQP}BQP problem in the random oracle and unrelativized worlds. We organize the proof around four main steps and discuss how each connects to the literature on the analysis of boolean functions and probabilistic combinatorics. To bring out the key ideas, we do not optimize parameters, and our presentation yields weaker exponents than the original. Authors’ note.\textbf{Authors' note.}Authors’ note. The proof was discovered by David Turturean using a research system developed at Physical Superintelligence (PSI), in combination with a non-public Anthropic model. The proof was then shared with the authors, who worked to understand it and prepare this exposition. Anthropic's public models were used in this process. The authors did not receive financial compensation from Anthropic or PSI. This article is not intended for publication at a conference or in a journal.
We consider the problem of establishing limitations on the power of quantum query algorithms via the completely bounded polynomial method. In particular, we prove several optimal functional inequalities involving different notions of completely bounded polynomials. These inequalities lead to limiting theorems for the power of quantum query algorithms that improve on prior works. 1. An optimal root-influence bound for block-multilinear polynomials. Prior work showed that block-multilinear polynomials ppp of degree ttt satisfy a root-influence bound, ∥p∥cb≥∑iInfi[p]/t2\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t^2∥p∥cb​≥∑i​Infi​[p]​/t2, which is stronger than the bound appearing in the Aaronson-Ambainis conjecture. We find the optimal constant in that inequality: ∥p∥cb≥∑iInfi[p]/t\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t∥p∥cb​≥∑i​Infi​[p]​/t. Since the amplitudes of quantum algorithms that query disjoint blocks of inputs-such as ttt-fold forrelation- are block-multilinear polynomials with ∥p∥cb≤1,\|p\|_{\text{cb}}\leq 1,∥p∥cb​≤1, our inequality shows that they satisfy t≥∑iInfi[p]t\geq \sum_i\sqrt{\mathrm{Inf}_i[p]}t≥∑i​Infi​[p]​. We prove that this inequality yields both a more efficient classical simulation than prior results based on the Aaronson-Ambainis argument, and a qualitative improvement: all classical queries are nonadaptive. 2. Optimal Fourier growth of the highest level of quantum query algorithms. We show that for every polynomial ppp defined on {−1,1}n\{-1,1\}^n{−1,1}n of degree 2t2t2t, the Fourier Growth at the level 2t,2t,2t, namely ∥p^2t∥ℓ1\|\widehat p_{2t}\|_{\ell_1}∥p​2t​∥ℓ1​​, satisfies ∥p^2t∥ℓ1≤(en/(2t−1))2t−12∥p∥cb\|\widehat p_{2t}\|_{\ell_1}\leq (en/(2t-1))^{\frac{2t-1}{2}}\|p\|_{\text{cb}}∥p​2t​∥ℓ1​​≤(en/(2t−1))22t−1​∥p∥cb​. This is optimal up to the factor eee, as witnessed by 2t2t2t-fold forrelation. As quantum query algorithms that make ttt queries (to the whole input) satisfy ∥p∥cb≤1\|p\|_{\text{cb}}\leq 1∥p∥cb​≤1, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).
In an attempt to show that the acceptance probability of a quantum query algorithm making qqq queries can be well-approximated almost everywhere by a classical decision tree of depth ≤poly(q)\leq \text{poly}(q)≤poly(q), Aaronson and Ambainis proposed the following conjecture: let f:{±1}n→[0,1]f: \{ \pm 1\}^n \rightarrow [0,1]f:{±1}n→[0,1] be a degree ddd polynomial with variance ≥ε\geq ε≥ε. Then, there exists a coordinate of fff with influence ≥poly(ε,1/d)\geq \text{poly} (ε, 1/d)≥poly(ε,1/d). We show that for any polynomial f:{±1}n→[0,1]f: \{ \pm 1\}^n \rightarrow [0,1]f:{±1}n→[0,1] of degree ddd (d≥2)(d \geq 2)(d≥2) and variance Var[f]≥1/d\text{Var}[f] \geq 1/dVar[f]≥1/d, if ρρρ denotes a random restriction with survival probability log⁡(d)C1d\dfrac{\log(d)}{C_1 d}C1​dlog(d)​, Pr[fρ has a coordinate with influence≥Var[f]2dC2]≥Var[f]log⁡(d)50C1d \text{Pr} \left[f_ρ \text{ has a coordinate with influence} \geq \dfrac{\text{Var}[f]^2 }{d^{C_2}} \right] \geq \dfrac{\text{Var}[f] \log(d)}{50C_1 d}Pr[fρ​ has a coordinate with influence≥dC2​Var[f]2​]≥50C1​dVar[f]log(d)​ where C1,C2>0C_1, C_2>0C1​,C2​>0 are universal constants. Thus, Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions of the given polynomial assuming its variance is not too low.