A proof of the Aaronson–Ambainis conjecture

The paper in detail

A quantum algorithm making \(T\) queries to an \(N\)-bit input accepts with a probability that is a real polynomial of degree at most \(2T\) in the bits, with values in \([0,1]\). A classical algorithm can mimic it on most inputs if it can always find a bit whose value matters: query it, fix it, and repeat until the remaining polynomial is nearly constant. Aaronson and Ambainis showed that this works with polynomially many queries exactly when every bounded degree-\(d\) polynomial with variance \(\varepsilon\) has a variable of influence \((\varepsilon/d)^{O(1)}\). For polynomials taking only the values 0 and 1 this was known; for merely bounded ones, the best bounds lost a factor \(e^{d}\).

The proof first studies a Boolean function \(g\) with a fractional certificate (a "row") at each point: weights \(\lambda^{x}\) on coordinates such that every set of flips that changes \(g(x)\) carries total weight at least 1. A determinant argument, related to Reimer's butterfly lemma, produces a bijection of the 1-inputs that moves each point across its certificate, and from it an inequality bounding a sum over pairs of antipodal points by the influences. Applying it on every subcube gives the all-pairs inequality, and one consequence is the two-sided bound: four times the product of the averages of \(1/\|\lambda^{x}\|_1\) over the 0-inputs and over the 1-inputs is at most the largest influence.

A bounded degree-\(d\) polynomial has, at every point, a real-valued analogue of a certificate with total weight at most \(\pi^{2}d^{2}\) (via Markov's inequality for the derivative of a polynomial and LP duality, following Agarwal and Ben-David). Each level set \(\{f>t\}\) is a Boolean function inheriting rows scaled by \(1/|f(x)-t|\). Integrating the all-pairs inequality over \(t\) turns products \((f(x)-t)(t-f(y))\) into \((f(x)-f(y))^{3}/6\), which yields a third-moment inequality and then a coordinate whose mean absolute change is at least \(\mathrm{Var}(f)^{3/2}/(6K^{2})\). A final averaging over coordinates with small influence converts this into the influence bound.

The open questions are quantitative: whether the variance exponent can be 2 (as for Boolean functions, where the paper's inequality gives \(\mathrm{Var}(g)/K^{2}\)), the best constant in the certificate bound (between 2 and \(\pi^{2}/2\)), and a direct combinatorial construction of the bijection. Appendix A records that the first complete proof gave exponent 22, later improved to 11 and then 7, each checked in Lean.

Transferable methods

1. Integrating a Boolean inequality over level sets

   The combinatorial core of the proof is about Boolean functions, but the conjecture is about bounded real ones. Thresholding \(f\) at every level \(t\) gives a family of Boolean functions; an inequality that holds for each, integrated over \(t\), becomes an inequality for \(f\) with cubic dependence on its differences.

   For \(g_t=1_{\{f>t\}}\), a row \(a^{x}\) of \(f\) divided by \(|f(x)-t|\) is a row of \(g_t\), and the all-pairs inequality for \(g_t\) reads \[\sum_{f(y)<t<f(x)}\frac{(f(x)-t)(t-f(y))}{s_{xy}}\le2^{n-1}\sum_j\frac{b_j(g_t)}{w_j}.\] Over the interval between \(f(y)\) and \(f(x)\), \(\int(f(x)-t)(t-f(y))\,dt=(f(x)-f(y))^{3}/6\), and \(\int b_j(g_t)\,dt=2^{n-1}L_j(f)\), where \(L_j\) is the mean absolute change of \(f\) when coordinate \(j\) flips.

   Editorial remark: the cube comes from the product of two linear factors integrated over the gap. Restricting to pairs on either side of a median \(m\) and removing the weights \(w\) by Cauchy–Schwarz gives \(\mathbb E|f-m|^{3}\le6K^{2}\max_jL_j(f)\), and \(\mathrm{Var}(f)^{3/2}\le\mathbb E|f-m|^{3}\) finishes the step. Numerically the level integral agrees with \((a-b)^{3}/6\) to \(10^{-10}\).

   How to reuse it

   Any inequality proved for Boolean functions with linear dependence on a threshold, such as isoperimetric or certificate-type bounds, can be lifted to real-valued functions by the layer-cake formula; the exponent of the resulting moment is the number of threshold-dependent factors plus one.

2. From influences to a classical simulation

   The quantum consequence is not in the polynomial theorem itself; it comes from the query-and-fix procedure of Aaronson and Ambainis. The theorem guarantees a large-influence variable at each step, and total influence bounds how many steps can happen before the variance is small.

   The acceptance probability has degree at most \(2T\), so its total influence is at most \(2T\). While the restricted polynomial's variance exceeds \(\varepsilon^{2}\delta/2\), the theorem provides a variable of influence above \((\varepsilon^{2}\delta/(4T))^{7}\); querying it removes that much expected total influence. By Markov's inequality the process stops, except with probability \(\delta/2\), within \[\frac{4T}{\delta}\Bigl(\frac{4T}{\varepsilon^{2}\delta}\Bigr)^{7}=(4T)^{8}\varepsilon^{-14}\delta^{-8}\] queries, and then the restricted polynomial's mean approximates the acceptance probability on most remaining inputs.

   Editorial check: the two forms of the query count agree numerically (for example \(4.30\times10^{30}\) at \(T=3\), \(\varepsilon=\delta=0.1\)), and the constants \(\sqrt{15}/(500\pi^{4})=7.95\times10^{-5}\) and \(128\cdot8\sqrt{15}/(125\pi^{4})=0.326>1/4\), the step that turns \(\mathrm{Var}^{5/2}/d^{6}\) into \((\mathrm{Var}/d)^{7}\), are as stated. The two-sided inequality of Theorem 1.5 held, with minimal certificates as rows, on several hundred random Boolean functions of 2–4 variables.

   How to reuse it

   Any lower bound on the maximum influence of bounded low-degree polynomials translates, through the same query-and-fix argument, into a polynomial-query classical simulation of quantum query algorithms on the corresponding input distribution.

Source: Section 1.5 (overview), Sections 5, 7 and 8; Theorem 1.5. Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. If the proof holds, it settles an 18-year-old conjecture and with it the folklore statement that unstructured problems admit at most polynomial quantum speedups on average; Aaronson and Ambainis's random-oracle consequences follow too. The proof is elementary (linear algebra over a polynomial ring, Cauchy–Schwarz, Markov's inequality for polynomials, linear-programming duality), and the main theorem is formalised in Lean. We covered the release and its background in our article of 6 November.

Limitations. The paper is days old and not yet refereed; its Lean formalisation is the main independent check so far, and a shorter exposition by Blanc, Docter, Strassle and Tan is announced. The exponents are not optimal: the variance exponent must be at least 2, and the proof loses a factor of order \(\sqrt n\) for averages of coordinates. The paper states that its mathematical statements were produced by instances of a non-public Anthropic model in a research harness run by Physical Superintelligence, which also drafted the paper; the author reviewed and edited it and takes responsibility for its correctness.

Description based on the full arXiv HTML of v1, read 2026-11-09: Sections 1 and 9, the overview of the six-link proof in Section 1.5, the statements of Sections 3–8 and Appendix A (timeline). The detailed proofs of Sections 3–8 were not checked line by line. The constants, the query-count arithmetic, the level integral and the two-sided inequality (Theorem 1.5, on random Boolean functions of 2–4 variables) were checked numerically.