betaFeedback

WorksPhysics and Astronomy

A short proof of the Aaronson-Ambainis Conjecture via the completion framework

Abstract

We give a short proof of the Aaronson-Ambainis conjecture. If a partial Boolean function ff is defined on a δδ-fraction of all nn-bit strings and have quantum query complexity Q(f)Q(f), then, for every 0<ε<10<ε<1, a deterministic algorithm computes ff correctly on at least a 1−ε1-ε fraction of its domain using O(Q(f)6/(εδ)2)O( Q(f)^6 / (εδ)^2) queries. Our proof uses the completion framework and establishes a more general bound in terms of the classical adversary measure. The only result we use from Turturean's recent proof is a special case of his certificate inequality, for which we provide a self-contained proof. We also derive the stronger variant of the Aaronson-Ambainis Conjecture, the bounded-polynomial influence conjecture, from our main result in the appendix.

The conjecture and our completion theorem

On November 6th, 2026, Turturean posted a 60-page preprint containing a proof of the Aaronson-Ambainis conjecture [Tur26]. We give a short proof of the following equivalent version of the Aaronson-Ambainis conjecture.

Conjecture 1 (Conjecture 7.1 of [1]). Let ff be a partial Boolean function with Dom⁡(f)≠∅\operatorname{Dom}(f) \ne\varnothing and density δ=∣Dom⁡(f)∣/2n\delta= |\operatorname{Dom}(f)|/2^n. For every 0<ε<10 < \varepsilon< 1, there is a deterministic algorithm making poly⁡(Q(f),1/ε,1/δ)\operatorname{poly}(Q(f),1/\varepsilon,1/\delta) queries that computes ff correctly on at least a 1−ε1-\varepsilon fraction of Dom⁡(f)\operatorname{Dom}(f).

Our approach uses the completion framework of [3]. Given a partial Boolean function ff, a total Boolean function FF is a completion of ff if F(x)=f(x)F(x)=f(x) for all x∈Dom⁡(f)x \in\operatorname{Dom}(f), while values on inputs outside the domain are assigned arbitrarily. For the Aaronson-Ambainis conjecture, we only need correctness on most of the inputs in Dom⁡(f)\operatorname{Dom}(f). Therefore, we allow ourselves to discard at most an ε\varepsilon fraction of Dom⁡(f)\operatorname{Dom}(f) before extending the function. Specifically, we seek D⊆Dom⁡(f)D \subseteq\operatorname{Dom}(f) with ∣D∣≥(1−ε)∣Dom⁡(f)∣|D| \ge(1-\varepsilon)|\operatorname{Dom}(f)| and a total Boolean function FF agreeing with ff on DD, together with a deterministic algorithm for FF using poly⁡(Q(f),1/ε,1/δ)\operatorname{poly}(Q(f),1/\varepsilon,1/\delta) queries that computes ff correctly on every input in DD, without needing to test membership in DD. Conversely, any deterministic algorithm achieving the desired accuracy in computing ff naturally defines a total Boolean function FF, with D={x∈Dom⁡(f):F(x)=f(x)}D=\{x \in\operatorname{Dom}(f): F(x)=f(x)\}. Thus, constructing a low-complexity completion after discarding a small fraction of the domain is precisely the desired simulation.

We prove a statement in terms of the classical adversary measure CAdv⁡\operatorname{CAdv}, rather than quantum query complexity. Write Λb=f−1(b)\Lambda_b=f^{-1}(b) and Δ(x,y)={i:xi≠yi}\Delta(x,y)=\{i:x_i\ne y_i\}. For a nonnegative vector vv, write ∥v∥1=∑ivi\lVert v\rVert_1=\sum_i v_i for its cost. Using the formulation of [2], CAdv⁡(f)\operatorname{CAdv}(f) is the minimum of max⁡x∈Dom⁡(f)∥λx∥1\max_{x\in\operatorname{Dom}(f)}\lVert\lambda^x\rVert_1 over vectors λx∈R≥0n\lambda^x\in\mathbb{R}_{\ge0}^n, x∈Dom⁡(f)x\in\operatorname{Dom}(f), satisfying

∑i∈Δ(x,y)min⁡{λix,λiy}≥1if f(x)≠f(y).(1)\sum_{i\in\Delta(x,y)}\min\{\lambda_i^x,\lambda_i^y\}\ge1\quad\text{if }f(x)\ne f(y). \tag*{(1)}

Theorem 2 (Completion from classical adversary bounds). Let ff be a partial Boolean function with Dom⁡(f)≠∅\operatorname{Dom}(f)\ne\varnothing and density δ=∣Dom⁡(f)∣/2n\delta=\lvert\operatorname{Dom}(f)\rvert/2^n. For every 0<ε<10<\varepsilon<1, there are D⊆Dom⁡(f)D\subseteq\operatorname{Dom}(f) and a total function F:{0,1}n→{0,1}F:\{0,1\}^n\to\{0,1\} such that

∣D∣≥(1−ε)∣Dom⁡(f)∣,F⊇f∣D,D(F)=O(CAdv⁡(f)3(εδ)2).\lvert D\rvert\ge(1-\varepsilon)\lvert\operatorname{Dom}(f)\rvert,\qquad F\supseteq f|_D,\qquad\mathrm{D}(F)=O\left(\frac{\operatorname{CAdv}(f)^3}{(\varepsilon\delta)^2}\right).

Theorem 2 with the bound CAdv⁡(f)=O(Q(f)2)\operatorname{CAdv}(f)=O(Q(f)^2) of [2] immediately implies Conjecture 1 with O(Q(f)6/(εδ)2)O(Q(f)^6/(\varepsilon\delta)^2) queries.

The proof first constructs a completion G⊇fG\supseteq f with total influence I(G)=O(CAdv⁡(f))I(G)=O(\operatorname{CAdv}(f)) and fractional certificate complexity FC⁡(G,x)=O(CAdv⁡(f))\operatorname{FC}(G,x)=O(\operatorname{CAdv}(f)) for every x∈Dom⁡(f)x\in\operatorname{Dom}(f). At each step of our deterministic algorithm, the inputs consistent with the answers so far form a subcube. We apply Lemma 4 to this subcube to choose an influential coordinate to query next. Each query decreases the expected remaining total influence by the queried coordinate’s influence on the current subcube, so Lemma 4 and the bound on I(G)I(G) give a deterministic algorithm using O(CAdv⁡(f)3/(εδ)2)O(\operatorname{CAdv}(f)^3/(\varepsilon\delta)^2) queries that agrees with ff on at least a 1−ε1-\varepsilon fraction of its domain.

Proof of the main theorem

Unless otherwise specified, inputs x,y,zx,y,z are over {0,1}n\{0,1\}^n. Write xSx^S for xx with bits of S⊆[n]S\subseteq[n] flipped and xi=x{i}x^i=x^{\{i\}}. A subcube CC of {0,1}n\{0,1\}^n is obtained by fixing the values of some coordinates in [n][n], the remaining are called free. For a total Boolean function GG and XX uniform over {0,1}n\{0,1\}^n, define the influence of GG as,

Ii(G)=Pr⁡[G(X)≠G(Xi)],I(G)=∑iIi(G).I_i(G)=\Pr[G(X)\ne G(X^i)],\qquad I(G)=\sum_i I_i(G).

A fractional certificate for GG at xx is a vector cx∈R≥0nc^x\in\mathbb{R}_{\ge0}^n satisfying

∑i∈Δ(x,y)cix≥1for every y∈{0,1}n s.t. G(y)≠G(x).\sum_{i\in\Delta(x,y)}c_i^x\ge1\quad\text{for every }y\in\{0,1\}^n\text{ s.t. }G(y)\ne G(x).

Define FC⁡(G,x):=min⁡cx∥cx∥1\operatorname{FC}(G,x):=\min_{c^x}\lVert c^x\rVert_1, where the minimum is over all such fractional certificates. On a subcube CC, these definitions use the free coordinates of CC and take XX uniformly over CC.

Lemma 3. Every nonconstant partial Boolean function ff has a completion G⊇fG\supseteq f such that,

I(G)=O(CAdv⁡(f)),FC⁡(G,x)=O(CAdv⁡(f))(x∈Dom⁡(f)).I(G)=O(\operatorname{CAdv}(f)),\qquad\operatorname{FC}(G,x)=O(\operatorname{CAdv}(f))\quad(x\in\operatorname{Dom}(f)).

Proof. Choose nonnegative vectors λx\lambda^x satisfying Eq. (1) with ∥λx∥1≤CAdv⁡(f)\lVert\lambda^x\rVert_1\le\operatorname{CAdv}(f) for every x∈Dom⁡(f)x\in\operatorname{Dom}(f). For a∈Dom⁡(f)a\in\operatorname{Dom}(f), define da(z)=∑i:zi≠aiλiad_a(z)=\sum_{i:z_i\ne a_i}\lambda_i^a. For a∈A1a\in A_1, b∈A0b\in A_0, and any z∈{0,1}nz\in\{0,1\}^n, Eq. (1) gives

da(z)+db(z)≥∑i∈Δ(a,b)min⁡{λia,λib}≥1.(2)d_a(z)+d_b(z)\ge\sum_{i\in\Delta(a,b)}\min\{\lambda_i^a,\lambda_i^b\}\ge1. \tag*{(2)}

Define g(z)=min⁡{1,min⁡a∈A1da(z)}g(z)=\min\{1,\min_{a\in A_1}d_a(z)\}. Then g=0g=0 on A1A_1 and g=1g=1 on A0A_0. If g(z)<1g(z)<1, choose a∈A1a\in A_1 such that da(z)=g(z)d_a(z)=g(z). For every coordinate ii, this choice gives

max⁡{0,g(zi)−g(z)}≤max⁡{0,da(zi)−da(z)}≤λia.\max\{0,g(z^i)-g(z)\}\leq\max\{0,d_a(z^i)-d_a(z)\}\leq\lambda_i^a.

The left-hand sides sum to at most CAdv⁡(f)\operatorname{CAdv}(f). When g(z)=1g(z)=1, each maximum is 0. Since (X,Xi)(X,X^i) and (Xi,X)(X^i,X) have the same distribution,

L(g):=∑iE[∣g(X)−g(Xi)∣]=2E[∑imax⁡{0,g(Xi)−g(X)}]=O(CAdv⁡(f)).L(g):=\sum_i\mathbb{E}[|g(X)-g(X^i)|]=2\mathbb{E}\left[\sum_i\max\{0,g(X^i)-g(X)\}\right]=O(\operatorname{CAdv}(f)).

For every threshold 0<t<10<t<1, define Gt(x):=1[g(x)<t]G_t(x):=\mathbf{1}[g(x)<t]. Notice that GtG_t extends ff and

∫01I(Gt) dt=∑iE[∣g(X)−g(Xi)∣]=L(g).\int_0^1 I(G_t)\,dt=\sum_i\mathbb{E}[|g(X)-g(X^i)|]=L(g).

Hence, by averaging, there is some t∈[1/4,3/4]t\in[1/4,3/4] with I(Gt)≤2L(g)=O(CAdv⁡(f))I(G_t)\leq2L(g)=O(\operatorname{CAdv}(f)). Fix the completion G=GtG=G_t.

Let us show that 4λx4\lambda^x is a fractional certificate for all x∈Dom⁡(f)x\in\operatorname{Dom}(f) of GG, which implies the statement as ∥4λx∥1≤4CAdv⁡(f)\|4\lambda^x\|_1\leq4\operatorname{CAdv}(f). For a∈A1a\in A_1, every yy such that G(y)=0G(y)=0 satisfies da(y)≥g(y)≥t≥1/4d_a(y)\geq g(y)\geq t\geq1/4. Otherwise for b∈A0b\in A_0, every yy with G(y)=1G(y)=1 has some a∈A1a\in A_1 with da(y)<td_a(y)<t, so Eq. (2) gives db(y)>1−t≥1/4d_b(y)>1-t\geq1/4. Thus ∑i∈Δ(x,y)4λix=4dx(y)≥1\sum_{i\in\Delta(x,y)}4\lambda_i^x=4d_x(y)\geq1 whenever G(y)≠G(x)G(y)\neq G(x).

Note that Lemma 3 only controls certificates on the domain Dom⁡(f)\operatorname{Dom}(f). Next we give a self-contained proof of a consequence of Theorem 5.4 in [Tur26].

Lemma 4. For G:{0,1}n→{0,1}G:\{0,1\}^n\to\{0,1\} and b∈{0,1}b\in\{0,1\}, let Ub⊆G−1(b)U_b\subseteq G^{-1}(b) be nonempty with density δb=∣Ub∣/2n\delta_b=|U_b|/2^n. If FC⁡(G,x)≤γb\operatorname{FC}(G,x)\leq\gamma_b for every x∈Ubx\in U_b, then some i∈[n]i\in[n] satisfies

Ii(G)≥δ0δ1γ0γ1.I_i(G)\geq\frac{\delta_0\delta_1}{\gamma_0\gamma_1}.

The same holds on a subcube, with densities measured within it.

Proof. For each x∈Ubx\in U_b, fix some fractional certificate cxc^x such that ∥cx∥1≤γb\|c^x\|_1\leq\gamma_b. For i∈[n]i\in[n] and S⊆[n]S\subseteq[n], define cx(S):=∑i∈Scixc^x(S):=\sum_{i\in S}c_i^x and the weights

wi:=2γ0∣U1∣∑x∈U1cix,w(S):=∑i∈Swi.w_i:=\frac{2\gamma_0}{|U_1|}\sum_{x\in U_1}c_i^x,\qquad w(S):=\sum_{i\in S}w_i.

Notice that ∥w∥1≤2γ0γ1\|w\|_1\leq2\gamma_0\gamma_1. For y∈U0y\in U_0, let Hy={i:ciy>wi}H_y=\{i:c_i^y>w_i\}. Since w(Hy)≤cy(Hy)≤γ0w(H_y)\leq c^y(H_y)\leq\gamma_0,

Ex∈U1[cx(Hy)]=w(Hy)2γ0≤12.\mathbb{E}_{x\in U_1}[c^x(H_y)]=\frac{w(H_y)}{2\gamma_0}\leq\frac12.

By Markov’s inequality, at least half of the inputs x∈U1x\in U_1 satisfy cx(Hy)<1c^x(H_y)<1. Mark each such pair (x,y)(x,y). If (x,y)(x,y) is marked, then G(x)=G(xS)G(x)=G(x^S) for every S⊆HyS\subseteq H_y since cx(Hy)<1c^x(H_y)<1. Furthermore, if G(z)=1G(z)=1 and zz agrees with yy on HyH_y, then

1≤cy(Δ(y,z))≤w(Δ(y,z)).(3)1\leq c^y(\Delta(y,z))\leq w(\Delta(y,z)). \tag*{(3)}

Fix a subcube CC with free coordinates JJ and let Xb={x∈C:G(x)=b}X_b=\{x\in C:G(x)=b\} for b∈{0,1}b\in\{0,1\}. Let NCN_C count the marked pairs (x,y)(x,y) in CC such that xJ=yx^J=y. For i∈Ji\in J, let bib_i count the pairs {x,xi}\{x,x^i\} with one input in X0X_0 and the other in X1X_1. Our goal is to prove

NC≤∑i∈Jwibi.(4)N_C\leq\sum_{i\in J}w_i b_i. \tag*{(4)}

When X1=∅X_1=\varnothing, this is trivial. Otherwise, for i∈Ji\in J let tit_i be variables and define the ∣X1∣×∣X1∣|X_1|\times|X_1| matrix MM by

Mxz=∏i∈J:xi=ziti(x,z∈X1).(5)M_{xz}=\prod_{i\in J:x_i=z_i}t_i\qquad(x,z\in X_1). \tag*{(5)}

Notice that det⁡(M)≠0\det(M) \ne0 because the product of the diagonal entries has degree ∣J∣∣X1∣|J||X_1|, while every other product in the determinant expansion has smaller degree since each contains an off-diagonal entry, which omits at least one factor tit_i.

Fix x,z∈X1x,z \in X_1 and K⊆JK \subseteq J such that xS∈X1x^S \in X_1 for every S⊆KS \subseteq K. To find factors of det⁡(M)\det(M), we use the following identity,

∑S⊆K(−1)∣S∣(∏i∈Sti)MxS,z=1[K⊆Δ(x,z)]Mxz∏i∈K(1−ti2).(6)\sum_{S \subseteq K}(-1)^{|S|}\left(\prod_{i \in S}t_i\right)M_{x^S,z}=\mathbf{1}[K \subseteq\Delta(x,z)]M_{xz}\prod_{i \in K}(1-t_i^2). \tag*{(6)}

Each coordinate i∈Ki \in K contributes ti−ti=0t_i-t_i=0 when xi=zix_i=z_i and 1−ti21-t_i^2 when xi≠zix_i \ne z_i. For a monomial, define its weight as wt⁡(∏i∈Jtiβi)=∑i∈Jwiβi\operatorname{wt}\left(\prod_{i \in J}t_i^{\beta_i}\right)=\sum_{i \in J}w_i\beta_i. Fix a monomial m=∏i∈Jtiβim=\prod_{i \in J}t_i^{\beta_i} of smallest degree with nonzero coefficient in det⁡(M)\det(M). We will show NC≤wt⁡(m)=∑i∈Jwiβi≤∑i∈JwibiN_C \le\operatorname{wt}(m)=\sum_{i \in J}w_i\beta_i \le\sum_{i \in J}w_ib_i, which implies Eq. (4).

Fix i∈Ji \in J and let rir_i count the disjoint pairs {x,xi}⊆X1\{x,x^i\} \subseteq X_1. Notice that ∣X1∣=2ri+bi|X_1|=2r_i+b_i. For each such pair, choose either input as xx and over all z∈X1z \in X_1, set MxzM_{xz} to Mxz−tiMxi,zM_{xz}-t_iM_{x^i,z}. These operations preserve det⁡(M)\det(M) and by Eq. (6) with K={i}K=\{i\} it inserts a factor (1−ti2)(1-t_i^2) in each new row. Therefore there is a polynomial PiP_i such that det⁡(M)=(1−ti2)riPi\det(M)=(1-t_i^2)^{r_i}P_i whose degree in tit_i is deg⁡ti(Pi)=deg⁡ti(det⁡(M))−2ri≤∣X1∣−2ri=bi\deg_{t_i}(P_i)=\deg_{t_i}(\det(M))-2r_i\le|X_1|-2r_i=b_i. By the expansion of det⁡(M)\det(M) using PiP_i, the least-degree terms come from PiP_i because the first term has the term 1. Therefore, βi=deg⁡ti(m)≤deg⁡ti(Pi)≤bi\beta_i=\deg_{t_i}(m)\le\deg_{t_i}(P_i)\le b_i, implying that ∑i∈Jwiβi≤∑i∈Jwibi\sum_{i \in J}w_i\beta_i\le\sum_{i \in J}w_ib_i.

Next we show that NC≤wt⁡(m)N_C \le\operatorname{wt}(m). Starting with the original matrix MM, we transform it into M~\widetilde{M} as follows. For each pair (x,y)(x,y) counted by NCN_C, let K=Hy∩JK=H_y\cap J and update the row xx by setting M~x,z\widetilde{M}_{x,z} to the left side in Eq. (6) over all z∈X1z \in X_1. Note that the rows xSx^S exist for every S⊆KS \subseteq K as (x,y)(x,y) is marked. The rest of M~\widetilde{M} is as in MM. These replacements affect NCN_C distinct rows because y=xJy=x^J is determined by xx.

By linearity in each row, we expand det⁡(M~)\det(\widetilde{M}) in terms of the original rows using the sums over SS in Eq. (6). When S=∅S=\varnothing in every replacement, we have det⁡(M)\det(M). If a row repeats, the contribution is zero. Otherwise, it is ±det⁡(M)\pm\det(M) multiplied by the factors from the row replacements. Unless every S=∅S=\varnothing, these factors have positive degree so the contribution cannot change the coefficient of mm.

Consider a pair (x,y)(x,y) counted by NCN_C and a column z∈X1z \in X_1 with M~x,z≠0\widetilde{M}_{x,z}\ne0. By Eq. (6), zz differs from xx on KK, so zz agrees with yy there. As they also agree outside of JJ, they agree on all of HyH_y. Therefore Eqs. (3) and (5) gives Mxz=∏i∈Δ(y,z)tiM_{xz}=\prod_{i \in\Delta(y,z)}t_i and w(Δ(y,z))≥1w(\Delta(y,z))\ge1. Expanding the factors in Eq. (6), each monomial in this entry is up to sign Mxz∏i∈Sti2M_{xz}\prod_{i \in S}t_i^2 for some S⊆KS \subseteq K and

wt⁡(Mxz∏i∈Sti2)=w(Δ(y,z))+2∑i∈Swi≥1.\operatorname{wt}\left(M_{xz}\prod_{i \in S}t_i^2\right)=w(\Delta(y,z))+2\sum_{i \in S}w_i\ge1.

Every product in the determinant expansion uses one entry from each of the NCN_C replaced rows, while all other entries have nonnegative weight. Hence every monomial in det⁡(M~)\det(\widetilde{M}) has weight at least NCN_C. Since mm occurs in det⁡(M~)\det(\widetilde{M}), we obtain NC≤wt⁡(m)N_C\le\operatorname{wt}(m), completing the proof of Eq. (4).

Next we sum over all subcubes. Each marked pair (x,y)(x,y) is counted by NCN_C for exactly one subcube CC whose free coordinates are Δ(x,y)\Delta(x,y), while each {x,xi}\{x,x^i\} with G(x)≠G(xi)G(x)\ne G(x^i) belongs to 2n−12^{n-1} subcubes, since every other coordinate can be fixed or free. There are 2n−1Ii(G)2^{n-1}I_i(G) such pairs. Summing Eq. (4) and using ∥w∥1≤2γ0γ1\lVert w\rVert_1\le2\gamma_0\gamma_1 gives

∣U0∣∣U1∣2≤4n−1∑iwiIi(G)≤2⋅4n−1γ0γ1max⁡iIi(G).\frac{|U_0||U_1|}{2}\le4^{n-1}\sum_iw_iI_i(G)\le2\cdot4^{n-1}\gamma_0\gamma_1\max_i I_i(G).

Substituting ∣Ub∣=2nδb|U_b|=2^n\delta_b proves the bound. □

The lemmas allow us to prove the main result.

Proof of Theorem 2. If ff is constant, let its completion FF also be constant. Otherwise choose GG as in Lemma 3. For a subcube CC, define

δb(C)=Pr⁡[X∈Ab∣X∈C]=∣Ab∩C∣∣C∣,m(C)=min⁡{δ0(C),δ1(C)}.\delta_b(C) = \Pr[X \in A_b \mid X \in C] = \frac{\lvert A_b \cap C\rvert}{\lvert C\rvert}, \qquad m(C) = \min\{\delta_0(C),\delta_1(C)\}.

The certificates at inputs in Dom⁡(f)∩C\operatorname{Dom}(f) \cap C remain valid after restricting to the free coordinates of CC. If m(C)>0m(C)>0, Lemma 4 applied with Ub=Ab∩CU_b=A_b\cap C implies a free coordinate ii with

Ii(G∣C)=Ω(m(C)2CAdv⁡(f)2),(7)I_i(G|C) = \Omega\left(\frac{m(C)^2}{\operatorname{CAdv}(f)^2}\right), \tag*{(7)}

as δ0(C)δ1(C)≥m(C)2\delta_0(C)\delta_1(C)\ge m(C)^2. The algorithm repeatedly queries such ii until m(C)=0m(C)=0. Next, we track the expected remaining total influence. For Cb=C∩{xi=b}C_b=C\cap\{x_i=b\}, the exact identity

I(G∣C)−I(G∣C0)+I(G∣C1)2=Ii(G∣C)(8)I(G|C)-\frac{I(G|C_0)+I(G|C_1)}{2}=I_i(G|C) \tag*{(8)}

holds because all other coordinate influences average unchanged. For t≥0t\ge0, run the procedure until m(C)=0m(C)=0 or tt queries have been made. When done, output the more frequent value of ff among the inputs in Dom⁡(f)∩C\operatorname{Dom}(f)\cap C, choosing either in case of a tie. Let XX be a uniformly random input from {0,1}n\{0,1\}^n and Ct(X)C_t(X) the subcube consistent with the answers obtained on XX. Then et:=E[m(Ct(X))]e_t:=\mathbb{E}[m(C_t(X))] is the fraction of all inputs in {0,1}n\{0,1\}^n that belong to Dom⁡(f)\operatorname{Dom}(f) and the procedure outputs incorrectly. Additional queries cannot increase ete_t. Telescoping Eq. (8), using Eq. (7), and applying Jensen’s inequality gives for s≥1s\ge1,

ses2≤∑t=0s−1et2≤∑t=0s−1E[m(Ct(X))2]=O(CAdv⁡(f)2I(G))=O(CAdv⁡(f)3).s e_s^2 \le\sum_{t=0}^{s-1}e_t^2 \le\sum_{t=0}^{s-1}\mathbb{E}[m(C_t(X))^2] = O(\operatorname{CAdv}(f)^2 I(G)) = O(\operatorname{CAdv}(f)^3).

Hence es=O(CAdv⁡(f)3/s)e_s=O\left(\sqrt{\operatorname{CAdv}(f)^3/s}\right). Choose s=O(CAdv⁡(f)3/(εδ)2)s=O(\operatorname{CAdv}(f)^3/(\varepsilon\delta)^2) be sufficiently large so that es≤εδe_s\le\varepsilon\delta. The algorithm then computes a total function FF using at most ss queries. For D={x∈Dom⁡(f):F(x)=f(x)}D=\{x\in\operatorname{Dom}(f):F(x)=f(x)\}, we have

∣Dom⁡(f)∖D∣≤εδ 2n=ε∣Dom⁡(f)∣.\lvert\operatorname{Dom}(f)\setminus D\rvert\le\varepsilon\delta\,2^n=\varepsilon\lvert\operatorname{Dom}(f)\rvert.

□\square

AI Disclosure. We have long believed that the most promising route to the Aaronson-Ambainis conjecture was through its equivalent formulation in Conjecture 7.1 of [1], with our completion framework providing a natural approach. Indeed, we formulated the conjecture as a completion question in [3].

Over the four months preceding Turturean’s result, we explored this route extensively with the assistance of ChatGPT 5.6 and 6. These efforts led to ideas similar to those used in the present proof, but we were unable to obtain an ingredient playing the role of Turturean’s certificate inequality [Tur26]. His result supplied the missing ingredient that allowed this approach to succeed. We use a special case of his certificate inequality, which we reprove here in a self-contained form for completeness.

Acknowledgment. We thank Ashley Montanaro for asking whether our argument also proves the bounded-polynomial influence conjecture (Conjecture 1.7 of [1]), which led to the extension presented in the appendix.

The bounded-polynomial influence conjecture

We show that Theorem 2 also implies the stronger version of the Aaronson-Ambainis conjecture, the bounded-polynomial influence conjecture.

Conjecture 5 (Conjecture 1.7 of [1]). Let p:Rn→Rp : \mathbb{R}^{n} \to\mathbb{R} be a polynomial of degree at most d≥1d \ge1 satisfying 0≤p(x)≤10 \le p(x) \le1 for every x∈{0,1}nx \in\{0,1\}^{n}. If

EX∈{0,1}n[(p(X)−E[p(X)])2]≥ε>0,\mathbb{E}_{X \in\{0,1\}^{n}}\left[(p(X)-\mathbb{E}[p(X)])^{2}\right] \ge\varepsilon> 0,

then there exists some i∈[n]i \in[n] that satisfies

Ii(p)≥(εd)O(1).I_i(p) \ge\left(\frac{\varepsilon}{d}\right)^{O(1)}.

The proof applies Theorem 2 to a partial function defined by pp, then uses a covariance inequality described in Lemma 6.

All expectations below are with respect to the uniform measure on {0,1}n\{0,1\}^{n}. For real-valued functions pp and hh, write

Ii(p)=E[(p(X)−p(Xi))2],Var⁡(p)=E[(p−E[p])2],Cov⁡(p,h)=E[(p−E[p])h].I_i(p)=\mathbb{E}[(p(X)-p(X^i))^2], \qquad\operatorname{Var}(p)=\mathbb{E}[(p-\mathbb{E}[p])^2], \qquad\operatorname{Cov}(p,h)=\mathbb{E}[(p-\mathbb{E}[p])h].

Lemma 6 (Corollary of [4]). Let p:{0,1}n→Rp : \{0,1\}^{n} \to\mathbb{R} and h:{0,1}n→[−1,1]h : \{0,1\}^{n} \to[-1,1]. If a deterministic algorithm computes hh using at most DD queries, then

∣Cov⁡(p,h)∣≤D2max⁡iIi(p).|\operatorname{Cov}(p,h)| \le\frac{D}{2}\sqrt{\max_i I_i(p)}.

Proof. Let qiq_i be the probability that the algorithm queries coordinate ii on a uniformly random input. In our notation, Eq. (6) of [4] gives

∣Cov⁡(p,h)∣≤12∑iqiE[∣p(X)−p(Xi)∣].|\operatorname{Cov}(p,h)| \le\frac{1}{2}\sum_i q_i\mathbb{E}[|p(X)-p(X^i)|].

The factor 1/21/2 arises because resampling a uniform bit flips it with probability 1/21/2. By Cauchy–Schwarz and ∑iqi≤D\sum_i q_i \le D,

∣Cov⁡(p,h)∣≤12∑iqiIi(p)≤D2max⁡iIi(p).|\operatorname{Cov}(p,h)| \le\frac{1}{2}\sum_i q_i\sqrt{I_i(p)} \le\frac{D}{2}\sqrt{\max_i I_i(p)}.

Theorem 7. Let n,d≥1n,d \ge1, and let p:{0,1}n→[0,1]p:\{0,1\}^n \to[0,1] be a real polynomial of degree dd. If v=Var⁡(p)>0v=\operatorname{Var}(p)>0, then

max⁡i∈[n]Ii(p)=Ω(v12d12).\max_{i\in[n]} I_i(p)=\Omega\left(\frac{v^{12}}{d^{12}}\right).

Proof. Let z=p−E[p]z=p-\mathbb{E}[p] and define

Dom⁡(f)={x:∣z(x)∣≥v/4},f(x)=1[z(x)>0](x∈Dom⁡(f)),δ=∣Dom⁡(f)∣2n.\operatorname{Dom}(f)=\{x:|z(x)|\ge v/4\},\qquad f(x)=\mathbf{1}[z(x)>0]\quad(x\in\operatorname{Dom}(f)),\qquad\delta=\frac{|\operatorname{Dom}(f)|}{2^n}.

Since ∣z∣≤1|z|\le1 and ∣z∣<v/4|z|<v/4 outside Dom⁡(f)\operatorname{Dom}(f),

v=E[z2]≤E[∣z∣]≤δ+v/4.v=\mathbb{E}[z^2]\le\mathbb{E}[|z|]\le\delta+v/4.

Thus δ≥3v/4\delta\ge3v/4. The polynomial (1+z)/2(1+z)/2 has degree at most dd, is bounded in [0,1][0,1] on the entire cube, and approximates ff on Dom⁡(f)\operatorname{Dom}(f) with error at most 1/2−v/8<1/21/2-v/8<1/2. The error-dependent approximate-degree bound from Theorem 8 of [2] gives

CAdv⁡(f)≤4π2d2v.\operatorname{CAdv}(f)\le\frac{4\pi^2d^2}{v}.

Apply Theorem 2 with ε=v/(16δ)∈(0,1)\varepsilon=v/(16\delta)\in(0,1). We obtain a total Boolean function FF with

Pr⁡[X∈Dom⁡(f),F(X)≠f(X)]≤v/16\Pr[X\in\operatorname{Dom}(f),F(X)\ne f(X)]\le v/16

and a deterministic algorithm computing FF using at most DD queries, where

D=O(CAdv⁡(f)3/v2)=O(d6/v5).D=O(\operatorname{CAdv}(f)^3/v^2)=O(d^6/v^5).

Set h=2F−1h=2F-1 and E={x∈Dom⁡(f):F(x)≠f(x)}E=\{x\in\operatorname{Dom}(f):F(x)\ne f(x)\}. On Dom⁡(f)∖E\operatorname{Dom}(f)\setminus E, we have zh=∣z∣zh=|z|; elsewhere zh≥−∣z∣zh\ge-|z|. Since ∣z∣<v/4|z|<v/4 on Dom⁡(f)c\operatorname{Dom}(f)^c,

Cov⁡(p,h)=E[zh]≥E[∣z∣]−2E[∣z∣1Dom⁡(f)c]−2E[∣z∣1E]≥v−v/2−2Pr⁡[X∈E]≥3v8.\begin{aligned} \operatorname{Cov}(p,h)=\mathbb{E}[zh]\ge\mathbb{E}[|z|]-2\mathbb{E}[|z|\mathbf{1}_{\operatorname{Dom}(f)^c}]-2\mathbb{E}[|z|\mathbf{1}_E] \\ &\ge v-v/2-2\Pr[X\in E]\ge\frac{3v}{8}. \end{aligned}

Replacing each output bb by 2b−12b-1 gives an algorithm for hh using at most DD queries. Finally, applying Lemma 6 gives us the conclusion

max⁡iIi(p)≥4Cov⁡(p,h)2D2≥9v216D2=Ω(v12d12).\max_i I_i(p)\ge\frac{4\operatorname{Cov}(p,h)^2}{D^2}\ge\frac{9v^2}{16D^2}=\Omega\left(\frac{v^{12}}{d^{12}}\right).

References

  1. [1]Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. Theory of Computing, 10(6):133–166, 2014. DOI: 10.4086/toc.2014.v010a006.DOI
  2. [2]Anurag Anshu, Shalev Ben-David, and Srijita Kundu. On query-to-communication lifting for adversary bounds. In CCC 2021, volume 200 of LIPIcs, pages 30:1–30:39, 2021. DOI: 10.4230/LIPIcs.CCC.2021.30.DOI
  3. [3]Thomas Huffstutler, Upendra Kapshikar, David Miloschewsky, and Supartha Podder. A Framework for Ruling out Quantum Speedups. In MFCS 2026, volume 386 of LIPIcs, pages 10:1–10:17, 2026. DOI: 10.4230/LIPIcs.MFCS.2026.10. Full version: arXiv:2603.29256.DOI
  4. [4]Ryan O’Donnell, Michael Saks, Oded Schramm, and Rocco A Servedio. Every decision tree has an influential variable. In FOCS 2005, pages 31–39, 2005. DOI: 10.1109/SFCS.2005.34.DOI

Paper details

vlnc:W_3kbxwwqp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents