We give a short proof of the Aaronson-Ambainis conjecture. If a partial Boolean function f is defined on a δ-fraction of all n-bit strings and have quantum query complexity Q(f), then, for every 0<ε<1, a deterministic algorithm computes f correctly on at least a 1−ε fraction of its domain using 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 f be a partial Boolean function with Dom(f)=∅ and density δ=∣Dom(f)∣/2n. For every 0<ε<1, there is a deterministic algorithm making poly(Q(f),1/ε,1/δ) queries that computes f correctly on at least a 1−ε fraction of Dom(f).
Our approach uses the completion framework of [3]. Given a partial Boolean function f, a total Boolean function F is a completion of f if F(x)=f(x) for all x∈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). Therefore, we allow ourselves to discard at most an ε fraction of Dom(f) before extending the function. Specifically, we seek D⊆Dom(f) with ∣D∣≥(1−ε)∣Dom(f)∣ and a total Boolean function F agreeing with f on D, together with a deterministic algorithm for F using poly(Q(f),1/ε,1/δ) queries that computes f correctly on every input in D, without needing to test membership in D. Conversely, any deterministic algorithm achieving the desired accuracy in computing f naturally defines a total Boolean function F, with D={x∈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, rather than quantum query complexity. Write Λb=f−1(b) and Δ(x,y)={i:xi=yi}. For a nonnegative vector v, write ∥v∥1=∑ivi for its cost. Using the formulation of [2], CAdv(f) is the minimum of maxx∈Dom(f)∥λx∥1 over vectors λx∈R≥0n, x∈Dom(f), satisfying
i∈Δ(x,y)∑min{λix,λiy}≥1if f(x)=f(y).(1)
Theorem 2 (Completion from classical adversary bounds). Let f be a partial Boolean function with Dom(f)=∅ and density δ=∣Dom(f)∣/2n. For every 0<ε<1, there are D⊆Dom(f) and a total function F:{0,1}n→{0,1} such that
∣D∣≥(1−ε)∣Dom(f)∣,F⊇f∣D,D(F)=O((εδ)2CAdv(f)3).
Theorem 2 with the bound CAdv(f)=O(Q(f)2) of [2] immediately implies Conjecture 1 with O(Q(f)6/(εδ)2) queries.
The proof first constructs a completion G⊇f with total influence I(G)=O(CAdv(f)) and fractional certificate complexity FC(G,x)=O(CAdv(f)) for every x∈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) give a deterministic algorithm using O(CAdv(f)3/(εδ)2) queries that agrees with f on at least a 1−ε fraction of its domain.
Proof of the main theorem
Unless otherwise specified, inputs x,y,z are over {0,1}n. Write xS for x with bits of S⊆[n] flipped and xi=x{i}. A subcube C of {0,1}n is obtained by fixing the values of some coordinates in [n], the remaining are called free. For a total Boolean function G and X uniform over {0,1}n, define the influence of G as,
Ii(G)=Pr[G(X)=G(Xi)],I(G)=i∑Ii(G).
A fractional certificate for G at x is a vector cx∈R≥0n satisfying
i∈Δ(x,y)∑cix≥1for every y∈{0,1}n s.t. G(y)=G(x).
Define FC(G,x):=mincx∥cx∥1, where the minimum is over all such fractional certificates. On a subcube C, these definitions use the free coordinates of C and take X uniformly over C.
Lemma 3. Every nonconstant partial Boolean function f has a completion G⊇f such that,
I(G)=O(CAdv(f)),FC(G,x)=O(CAdv(f))(x∈Dom(f)).
Proof. Choose nonnegative vectors λx satisfying Eq. (1) with ∥λx∥1≤CAdv(f) for every x∈Dom(f). For a∈Dom(f), define da(z)=∑i:zi=aiλia. For a∈A1, b∈A0, and any z∈{0,1}n, Eq. (1) gives
da(z)+db(z)≥i∈Δ(a,b)∑min{λia,λib}≥1.(2)
Define g(z)=min{1,mina∈A1da(z)}. Then g=0 on A1 and g=1 on A0. If g(z)<1, choose a∈A1 such that da(z)=g(z). For every coordinate i, this choice gives
max{0,g(zi)−g(z)}≤max{0,da(zi)−da(z)}≤λia.
The left-hand sides sum to at most CAdv(f). When g(z)=1, each maximum is 0. Since (X,Xi) and (Xi,X) have the same distribution,
For every threshold 0<t<1, define Gt(x):=1[g(x)<t]. Notice that Gt extends f and
∫01I(Gt)dt=i∑E[∣g(X)−g(Xi)∣]=L(g).
Hence, by averaging, there is some t∈[1/4,3/4] with I(Gt)≤2L(g)=O(CAdv(f)). Fix the completion G=Gt.
Let us show that 4λx is a fractional certificate for all x∈Dom(f) of G, which implies the statement as ∥4λx∥1≤4CAdv(f). For a∈A1, every y such that G(y)=0 satisfies da(y)≥g(y)≥t≥1/4. Otherwise for b∈A0, every y with G(y)=1 has some a∈A1 with da(y)<t, so Eq. (2) gives db(y)>1−t≥1/4. Thus ∑i∈Δ(x,y)4λix=4dx(y)≥1 whenever G(y)=G(x).
Note that Lemma 3 only controls certificates on the domain 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} and b∈{0,1}, let Ub⊆G−1(b) be nonempty with density δb=∣Ub∣/2n. If FC(G,x)≤γb for every x∈Ub, then some i∈[n] satisfies
Ii(G)≥γ0γ1δ0δ1.
The same holds on a subcube, with densities measured within it.
Proof. For each x∈Ub, fix some fractional certificate cx such that ∥cx∥1≤γb. For i∈[n] and S⊆[n], define cx(S):=∑i∈Scix and the weights
wi:=∣U1∣2γ0x∈U1∑cix,w(S):=i∈S∑wi.
Notice that ∥w∥1≤2γ0γ1. For y∈U0, let Hy={i:ciy>wi}. Since w(Hy)≤cy(Hy)≤γ0,
Ex∈U1[cx(Hy)]=2γ0w(Hy)≤21.
By Markov’s inequality, at least half of the inputs x∈U1 satisfy cx(Hy)<1. Mark each such pair (x,y). If (x,y) is marked, then G(x)=G(xS) for every S⊆Hy since cx(Hy)<1. Furthermore, if G(z)=1 and z agrees with y on Hy, then
1≤cy(Δ(y,z))≤w(Δ(y,z)).(3)
Fix a subcube C with free coordinates J and let Xb={x∈C:G(x)=b} for b∈{0,1}. Let NC count the marked pairs (x,y) in C such that xJ=y. For i∈J, let bi count the pairs {x,xi} with one input in X0 and the other in X1. Our goal is to prove
NC≤i∈J∑wibi.(4)
When X1=∅, this is trivial. Otherwise, for i∈J let ti be variables and define the ∣X1∣×∣X1∣ matrix M by
Mxz=i∈J:xi=zi∏ti(x,z∈X1).(5)
Notice that det(M)=0 because the product of the diagonal entries has degree ∣J∣∣X1∣, while every other product in the determinant expansion has smaller degree since each contains an off-diagonal entry, which omits at least one factor ti.
Fix x,z∈X1 and K⊆J such that xS∈X1 for every S⊆K. To find factors of det(M), we use the following identity,
Each coordinate i∈K contributes ti−ti=0 when xi=zi and 1−ti2 when xi=zi. For a monomial, define its weight as wt(∏i∈Jtiβi)=∑i∈Jwiβi. Fix a monomial m=∏i∈Jtiβi of smallest degree with nonzero coefficient in det(M). We will show NC≤wt(m)=∑i∈Jwiβi≤∑i∈Jwibi, which implies Eq. (4).
Fix i∈J and let ri count the disjoint pairs {x,xi}⊆X1. Notice that ∣X1∣=2ri+bi. For each such pair, choose either input as x and over all z∈X1, set Mxz to Mxz−tiMxi,z. These operations preserve det(M) and by Eq. (6) with K={i} it inserts a factor (1−ti2) in each new row. Therefore there is a polynomial Pi such that det(M)=(1−ti2)riPi whose degree in ti is degti(Pi)=degti(det(M))−2ri≤∣X1∣−2ri=bi. By the expansion of det(M) using Pi, the least-degree terms come from Pi because the first term has the term 1. Therefore, βi=degti(m)≤degti(Pi)≤bi, implying that ∑i∈Jwiβi≤∑i∈Jwibi.
Next we show that NC≤wt(m). Starting with the original matrix M, we transform it into M as follows. For each pair (x,y) counted by NC, let K=Hy∩J and update the row x by setting Mx,z to the left side in Eq. (6) over all z∈X1. Note that the rows xS exist for every S⊆K as (x,y) is marked. The rest of M is as in M. These replacements affect NC distinct rows because y=xJ is determined by x.
By linearity in each row, we expand det(M) in terms of the original rows using the sums over S in Eq. (6). When S=∅ in every replacement, we have det(M). If a row repeats, the contribution is zero. Otherwise, it is ±det(M) multiplied by the factors from the row replacements. Unless every S=∅, these factors have positive degree so the contribution cannot change the coefficient of m.
Consider a pair (x,y) counted by NC and a column z∈X1 with Mx,z=0. By Eq. (6), z differs from x on K, so z agrees with y there. As they also agree outside of J, they agree on all of Hy. Therefore Eqs. (3) and (5) gives Mxz=∏i∈Δ(y,z)ti and w(Δ(y,z))≥1. Expanding the factors in Eq. (6), each monomial in this entry is up to sign Mxz∏i∈Sti2 for some S⊆K and
wt(Mxzi∈S∏ti2)=w(Δ(y,z))+2i∈S∑wi≥1.
Every product in the determinant expansion uses one entry from each of the NC replaced rows, while all other entries have nonnegative weight. Hence every monomial in det(M) has weight at least NC. Since m occurs in det(M), we obtain NC≤wt(m), completing the proof of Eq. (4).
Next we sum over all subcubes. Each marked pair (x,y) is counted by NC for exactly one subcube C whose free coordinates are Δ(x,y), while each {x,xi} with G(x)=G(xi) belongs to 2n−1 subcubes, since every other coordinate can be fixed or free. There are 2n−1Ii(G) such pairs. Summing Eq. (4) and using ∥w∥1≤2γ0γ1 gives
The certificates at inputs in Dom(f)∩C remain valid after restricting to the free coordinates of C. If m(C)>0, Lemma 4 applied with Ub=Ab∩C implies a free coordinate i with
Ii(G∣C)=Ω(CAdv(f)2m(C)2),(7)
as δ0(C)δ1(C)≥m(C)2. The algorithm repeatedly queries such i until m(C)=0. Next, we track the expected remaining total influence. For Cb=C∩{xi=b}, the exact identity
I(G∣C)−2I(G∣C0)+I(G∣C1)=Ii(G∣C)(8)
holds because all other coordinate influences average unchanged. For t≥0, run the procedure until m(C)=0 or t queries have been made. When done, output the more frequent value of f among the inputs in Dom(f)∩C, choosing either in case of a tie. Let X be a uniformly random input from {0,1}n and Ct(X) the subcube consistent with the answers obtained on X. Then et:=E[m(Ct(X))] is the fraction of all inputs in {0,1}n that belong to Dom(f) and the procedure outputs incorrectly. Additional queries cannot increase et. Telescoping Eq. (8), using Eq. (7), and applying Jensen’s inequality gives for s≥1,
Hence es=O(CAdv(f)3/s). Choose s=O(CAdv(f)3/(εδ)2) be sufficiently large so that es≤εδ. The algorithm then computes a total function F using at most s queries. For D={x∈Dom(f):F(x)=f(x)}, we have
∣Dom(f)∖D∣≤εδ2n=ε∣Dom(f)∣.
□
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→R be a polynomial of degree at most d≥1 satisfying 0≤p(x)≤1 for every x∈{0,1}n. If
EX∈{0,1}n[(p(X)−E[p(X)])2]≥ε>0,
then there exists some i∈[n] that satisfies
Ii(p)≥(dε)O(1).
The proof applies Theorem 2 to a partial function defined by p, then uses a covariance inequality described in Lemma 6.
All expectations below are with respect to the uniform measure on {0,1}n. For real-valued functions p and h, write
Thus δ≥3v/4. The polynomial (1+z)/2 has degree at most d, is bounded in [0,1] on the entire cube, and approximates f on Dom(f) with error at most 1/2−v/8<1/2. The error-dependent approximate-degree bound from Theorem 8 of [2] gives
CAdv(f)≤v4π2d2.
Apply Theorem 2 with ε=v/(16δ)∈(0,1). We obtain a total Boolean function F with
Pr[X∈Dom(f),F(X)=f(X)]≤v/16
and a deterministic algorithm computing F using at most D queries, where
D=O(CAdv(f)3/v2)=O(d6/v5).
Set h=2F−1 and E={x∈Dom(f):F(x)=f(x)}. On Dom(f)∖E, we have zh=∣z∣; elsewhere zh≥−∣z∣. Since ∣z∣<v/4 on Dom(f)c,
Replacing each output b by 2b−1 gives an algorithm for h using at most D queries. Finally, applying Lemma 6 gives us the conclusion
imaxIi(p)≥D24Cov(p,h)2≥16D29v2=Ω(d12v12).
References
[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]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]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]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
Alexander H. Riley, Amanda Byström, Gustavo E. Medina, Namitha Kizhuprakkat, Andrew P. Cooper, Sergey E. Koposov, T. M. Callingham, C. S. Frenk, Ting S. Li, G. Thomas et al. ·
Yanrui Zhou, Jiaxin Han, Wenting Wang, Zhaozhou Li, Alexander H. Riley, Monica Valluri, Amanda Byström, Gustavo E. Medina, Sergey E. Koposov, Ting S. Li et al. ·