Aaronson Ambainis Conjecture: How One Bit Revealed the Limits of Quantum Speedups

Suppose a quantum algorithm can query a vast string of bits in superposition, while a classical algorithm has to inspect one bit at a time. How can the classical algorithm know where to look? The November 2026 proof of the Aaronson Ambainis Conjecture gives an answer. Every nonconstant bounded polynomial of low degree on the Boolean cube has a variable whose influence is bounded below by a polynomial in its variance and inverse degree. Since a quantum algorithm’s acceptance probability is such a polynomial, a classical decision tree can query influential bits and approximate that probability on most uniformly random inputs. The guarantee counts input queries. The work done between queries can still be expensive.

1. What Is the Aaronson Ambainis Conjecture?

Scott Aaronson raised the problem in a 2008 lecture. In their 2014 paper on structure in quantum speedups, Aaronson and Andris Ambainis asked whether a polynomial that stays between zero and one on all bit strings, and has variance at least $\varepsilon>0$ under the uniform distribution, must have a variable with influence at least $(\varepsilon/d)^{O(1)}$, where $d$ is the degree. Here the exponent denotes a universal power, independent of how many input bits there are.

The dimension-free requirement matters. If an output depends a little on each of a million bits, a bound that shrinks with the input length gives the classical algorithm little guidance. Boundedness and degree together prevent that influence from spreading arbitrarily thin at fixed variance. The influential coordinate can change after an answer fixes one bit. That is what makes the resulting decision tree adaptive.

2. Why Quantum Query Complexity Leads to Low-Degree Polynomials

The polynomial comes from how an oracle call changes a quantum state. In the bit-query model, a query to an input position routes an amplitude according to whether that bit is zero or one. The new amplitudes are therefore linear combinations of the old ones with coefficients affine in input bits. Input-independent operations mix amplitudes without increasing their degree. After $T$ queries, every amplitude has degree at most $T$.

The algorithm’s acceptance probability adds squared magnitudes of the accepting amplitudes. This doubles the degree bound to $2T$. On the bit cube, positive powers of a bit can be replaced by that bit, so the probability has a real multilinear representation. It is between zero and one even if it takes many intermediate values. That range is why a result only about Boolean-valued functions would leave the simulation question open. Our coverage of quantum query complexity provides another example of how much depends on the precise oracle task.

3. Variance, Influence, and a Worked Example on the Boolean Cube

Write $Q_n=\{-1,1\}^n$ for the sign cube and take $x$ uniformly from it. The manuscript uses $x^j$ for the point obtained by flipping coordinate $j$, and $x^S$ for flipping all coordinates in a set $S$. Variance is the mean squared deviation from the mean. The degree is the largest number of distinct coordinates multiplied together in any term of the unique multilinear expansion with a nonzero coefficient. The influence of a variable uses the squared half-change under a flip.

For a worked example, take $f(x)=(2x_1+x_2)/3$. Its four values lie in the required range, its degree is one, and its mean is zero. Since the two signs are independent, the cross term averages to zero. Flipping the first sign gives a half-change of $2x_1/3$. Flipping the second gives $x_2/3$. Therefore $\operatorname{Var}(f)=5/9$, while $\operatorname{Inf}_1(f)=4/9$ and $\operatorname{Inf}_2(f)=1/9$. Any unused coordinates have zero influence. The example shows how the mean squared flip distinguishes the two relevant bits even though both flips always change the output. For related uses of the Boolean cube, see our coverage of the Courtade–Kumar conjecture and the quadratic sensitivity conjecture.

4. Why Earlier Approaches Could Not Prove the Conjecture

Earlier general results could guarantee a coordinate of influence at least $\varepsilon^3/2^{O(d)}$ in the original bit convention. At fixed variance, that guarantee decays exponentially with degree. Polynomial dependence was known for Boolean-valued functions and for special real-valued cases, including certain multilinear forms with equal-magnitude coefficients. A 2019 proof attempt by Nathan Keller and Ohad Klein was later withdrawn.

Lovett and Zhang’s work on fractional certificates came closer. Their strategy would succeed given a conjectured inequality about the distance from one set of cube vertices to the convex hull of another. Turturean’s manuscript gives a counterexample to that inequality as stated for arbitrary sets, using tribes, a Boolean function that takes the OR of many disjoint AND blocks. The new proof keeps the idea of examining where a real-valued polynomial crosses a threshold. It replaces the convex-hull step with an inequality that uses certificates from both sides of the threshold. This lets the proof combine information across all thresholds, including those at which relatively few vertices change sides.

5. The New Theorem on Variable Influence

Theorem 1.1 applies to $f:Q_n\to[-1,1]$ with integers $n\ge 1$ and $d\ge 1$ and degree at most $d$. Some coordinate satisfies the following bound.

At fixed variance, the degree appears to the sixth power in the denominator. At fixed degree, the variance appears to the five-halves power. The leading constant is about $7.95\times 10^{-5}$. Constant functions have zero variance, so the lower bound is informative when the output varies.

Corollary 1.2 returns to the original bit cube. For a real polynomial $p$ of degree at most $d$ with values in $[0,1]$ on $\{0,1\}^n$ and variance at least $\varepsilon>0$, the original influence $\operatorname{Inf}_i[p]$ is the mean squared full change when bit $i$ flips. For some bit it satisfies the following chain.

Changing variables via $X_i=(1-x_i)/2$ and setting $f(x)=2p(X)-1$ multiplies variance by four and makes the sign-cube half-change equal to the original full change. The last inequality absorbs the constant into a convenient exponent, using the fact that the variance of a probability is at most one quarter.

6. How the Determinant Argument Produces a Controlled Bijection

Start with a Boolean function $g$ and let $O$ contain its one-valued vertices. A wing at $x\in O$ is a set $A_x$ of coordinates such that every subset of them can be flipped from $x$ while staying in $O$. Choose one wing per vertex. Theorem 3.1 produces a permutation $\tau$ of $O$ that changes every wing coordinate at each vertex. For any coordinate $j$, it also bounds how many times $x$ and $\tau(x)$ agree there, by $b_j(g)$, the number of edges in direction $j$ crossing from one to zero, counted once per edge. This simultaneous control strengthens the existence statement equivalent to Reimer’s Butterfly Lemma.

The agreement matrix has one row and column per vertex in $O$. Its entry $M[x,z]$ is the product of formal variables $s_i$ over coordinates where $x$ and $z$ agree. A permutation in the determinant expansion contributes a monomial whose exponent of $s_j$ counts its agreements in coordinate $j$. Factoring out contributions from edges that stay inside $O$ bounds those exponents in the lowest-total-degree monomials by the crossing-edge counts. Signed combinations of rows along each wing then cancel entries that agree on any wing coordinate. The transformations preserve the lowest-degree part of the determinant, so a surviving monomial supplies a permutation satisfying both constraints. For a different use of determinants in complexity theory, see the permanent versus determinant problem.

7. From Antipodal Pairs to the All-Pairs Inequality

A fractional certificate for a Boolean output at a vertex assigns nonnegative weights to coordinates. Any set of flips that changes the output must collect at least one unit of weight. At opposite vertices with different outputs, the two certificates identify a wing whose coordinates can be flipped safely from the one-valued endpoint. The determinant bound then controls the cost of getting back to the one-set from the zero-valued endpoint using coordinates outside that wing.

To compare any two vertices $x$ and $y$ with different outputs, fix the coordinates on which they agree and leave the others free. The pair is antipodal in exactly this subcube. For a chosen set of free coordinates, each crossing edge in one of those directions appears in exactly one restriction. Each direction is free in $2^{n-1}$ choices of coordinate sets, so adding over all restrictions gives Proposition 5.2. With $N$ the zero-set, $\lambda_j^x$ the certificate weight at $x$, and $w_j>0$ auxiliary weights, it reads as follows.

8. Fractional Certificates, Chebyshev Bounds, and Linear Programming

For a real-valued $f$, the manuscript calls a certificate a row. A row $a^x$ at $x$ assigns enough weight to each flipped set $S$ to cover the absolute output change $|f(x)-f(x^S)|$. The sum of its coordinate weights is its cost. Theorem 6.8 gives a row at every point with cost at most $\pi^2 d^2$. We use $K$ to denote a common upper bound on the chosen row costs.

The dual problem assigns nonnegative weights to blocks of flips, with at most one unit of weight passing through any coordinate. Maximizing the weighted sum of absolute changes gives twice the fractional block sensitivity in the normalization cited by the paper. The proof uses Chebyshev polynomials to encode overlapping blocks as single flips in new variables. Markov’s endpoint derivative inequality then controls the sum of these flips through the degree. Linear programming duality turns the packing bound into a row at each point. Agarwal and Ben-David had already established a sharper row bound with half that coefficient. The proof in the manuscript derives the looser constant directly. It also bounds the sum of single-bit absolute changes at any point by $4d^2$, so the sum of their means has the same bound. This polynomial use of boundedness has a different objective from the extremal construction in our Littlewood polynomials coverage.

9. Integrating Level Sets and Averaging Coordinates to Finish the Proof

At each threshold $t$, set $g_t(x)=\mathbf{1}_{\{f(x)>t\}}$. Away from equality, dividing the row at $x$ by $|f(x)-t|$ gives a fractional certificate for this Boolean function. Crossing the threshold takes at least that much change. For a pair with $a=f(y)<f(x)=b$, the all-pairs inequality then carries the product of distances from the threshold. Its integral is cubic.

On the edge-count side, an edge crosses the threshold over an interval whose length is its absolute increment. Write $L_j(f)=\mathbb{E}_x|f(x)-f(x^j)|$ and $L(f)=\sum_{j=1}^n L_j(f)$. Keeping pairs across a cut at $r$ and removing the auxiliary weights using Cauchy–Schwarz gives Theorem 7.6. In its upper-tail form, it bounds the third moment above the cut, multiplied by the mass on the other side, by $(3/2)K^2\max_j L_j(f)$. The lower-tail form follows by replacing the function with its negative. Applying it at a median $m$ to both $f$ and $-f$ bounds $\mathbb{E}|f-m|^3$ by $6K^2\max_j L_j(f)$. The third moment is at least $\operatorname{Var}(f)^{3/2}$.

To get squared influence, average out coordinates whose squared influence is too small relative to their mean absolute increment. Their summed influence is at most two fifths of the variance, so at least three fifths of the variance survives, and the row bound survives by averaging. The coordinate with a large mean increment in the averaged function was kept, so its squared influence in the original function also has a lower bound. The denominator in that bound is proportional to $L(f)K^2$. Substituting the two degree bounds yields $d^6$. The extra variance factor in the averaging step turns the exponent $3/2$ into $5/2$.

10. What the Proof Establishes About Quantum Speedups

To approximate a $T$-query quantum algorithm’s acceptance probability, the deterministic classical tree queries an influential bit and restricts the polynomial to the observed value. Once the conditional variance is at most $\varepsilon^2\delta/2$, it returns the conditional mean. Chebyshev’s probability inequality controls the error at such leaves. Under a uniform restriction, the expected total influence of the remaining polynomial drops by the influence of the queried bit. Before stopping, each such drop is at least $(\varepsilon^2\delta/(4T))^7$ by Corollary 1.2. This budget bounds the expected number of queries, and a fixed cutoff adds at most another $\delta/2$ to the exceptional fraction. Section 1.3 gives the following bound on the query count.

The approximation is within additive error $\varepsilon$ on at least a $1-\delta$ fraction of the uniform inputs. A dense promise retains a useful guarantee when the exceptional fraction is chosen small relative to the promise density. A rare promise can lie inside the exceptional set. In Shor’s period-finding setting, the oracle has periodic structure, so the uniform-input guarantee leaves that source of speedup intact. See our coverage of exact quantum factoring for a separate result about factoring. The decision tree’s bound also leaves open the computational cost of finding its next bit and evaluating a conditional mean. Gate counts and circuit lower bounds measure other resources, as our coverage of quantum circuit lower bounds illustrates.

11. Lean Verification, Proof Limitations, and Remaining Open Problems

Physical Superintelligence’s November 6 announcement credits an internal research system running instances of a nonpublic Anthropic model. David Turturean developed the harness, reviewed the manuscript and takes responsibility for it. The public Lean 4 repository documents kernel checks for the main theorem and original-normalization corollary. Its scope notes list the quantum consequences in Section 1.3 and the open questions in Section 9 among the passages without a formal counterpart. For another example of formalization, see our coverage of Fermat’s Last Theorem in Lean.

The paper asks if the variance exponent can drop from $5/2$ to $2$. The average of $n$ independent signs has degree one, variance $1/n$, and every influence equal to $1/n^2$, so an exponent below two cannot work uniformly. The optimal degree exponent is also open. The best universal coefficient in the quadratic row-cost bound lies between $2$ and $\pi^2/2$, and a direct combinatorial construction of the controlled bijection remains open.

The Aaronson Ambainis Conjecture proof makes a concrete link between variance and the next bit a classical decision tree can read. Follow Binary Verse AI for more research explainers on what different models of computation can prove about their limits.