Quantum computing · Theory (AI-assisted)

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

Thomas Huffstutler; David Miloschewsky; Supartha Podder

arXiv:2611.12795v1 ↗PDF ↗Submitted 9 November 2026

Question
The Aaronson–Ambainis conjecture says that a quantum query algorithm can be simulated classically on most inputs with only polynomially more queries, so exponential query speedups need a promise on the input. Turturean posted a 60-page proof on 6 November 2026. Is there a short route, and which ingredient of that proof is really needed?
Result
For a partial Boolean function \(f\) defined on a fraction \(\delta\) of all \(n\)-bit strings, there is a deterministic algorithm with \(O(Q(f)^6/(\varepsilon\delta)^2)\) queries that is correct on all but an \(\varepsilon\) fraction of the domain. The proof is three pages. It first completes \(f\) to a total function with total influence and fractional certificates on the domain both of order the classical adversary bound, which is \(O(Q(f)^2)\). It then queries influential coordinates, which exist by a special case of Turturean's certificate inequality that the authors reprove from scratch with a determinant argument. An appendix derives the stronger bounded-polynomial influence conjecture, with maximal influence \(\Omega(v^{12}/d^{12})\) for a bounded degree-\(d\) polynomial of variance \(v\).

The paper in detail

A quantum algorithm with \(T\) queries has an acceptance probability that is a bounded polynomial of degree \(2T\) in the input bits. Aaronson and Ambainis conjectured in 2009 that every such polynomial with nonnegligible variance has an influential variable, which would give a classical simulation on most inputs. Their Conjecture 7.1 states it for partial functions: if \(f\) has quantum query complexity \(Q(f)\) and is defined on a fraction \(\delta\) of inputs, then \(\mathrm{poly}(Q(f),1/\varepsilon,1/\delta)\) classical queries compute it on all but an \(\varepsilon\) fraction of its domain.

The authors had earlier phrased this as a completion problem. Discard a small part of the domain, extend \(f\) to a total function \(F\), and ask that \(F\) have small deterministic query complexity. An algorithm need not know which inputs were discarded; it just computes \(F\). The difficulty is that a total extension can be complicated far from the domain, where \(f\) imposes nothing.

Lemma 3 builds a good extension from the classical adversary bound, a weighting \(\lambda^x\) of coordinates for each domain input that separates any two inputs with different values. A weighted Hamming distance to the nearest 1-input, thresholded at a suitable level, gives a total function \(G\) whose influence is \(O(\mathrm{CAdv}(f))\) and whose fractional certificates on the domain cost \(O(\mathrm{CAdv}(f))\). Since \(\mathrm{CAdv}(f)=O(Q(f)^2)\), both are polynomial in the quantum query complexity.

Small certificates on the domain alone do not obviously force an influential coordinate, since the rest of the cube can be wild. Lemma 4, a special case of Turturean's certificate inequality, shows that they do: if sets of density \(\delta_0,\delta_1\) in \(G^{-1}(0)\) and \(G^{-1}(1)\) have certificates of cost \(\gamma_0,\gamma_1\), some coordinate has influence at least \(\delta_0\delta_1/(\gamma_0\gamma_1)\). The algorithm queries such a coordinate, restricts to the resulting subcube, and repeats. Each query uses up influence, and the total influence is bounded.

Open questions concern the exponents and verification. The bound \(O(Q^6/(\varepsilon\delta)^2)\) is far from known lower bounds, and the bounded-polynomial influence exponent of the appendix is weaker than the best known. The determinant proof of Lemma 4 is the step most worth formalising.

Transferable methods

  1. Completion by thresholding a distance to the 1-inputs

    The extension has to agree with \(f\), change slowly, and have cheap certificates on the domain. A minimum of weighted distances does all three: it is 0 on 1-inputs, at least 1 on 0-inputs by the adversary condition, and each coordinate changes it by at most one weight.

    For \(a\in\mathrm{dom}(f)\) put \(d_a(z)=\sum_{i:z_i\neq a_i}\lambda_i^a\) and \(g(z)=\min\{1,\min_{a\in A_1}d_a(z)\}\). The adversary condition \(\sum_{i\in\Delta(a,b)}\min\{\lambda_i^a,\lambda_i^b\}\ge1\) gives \(d_a(z)+d_b(z)\ge1\) for \(f(a)\neq f(b)\), so \(g=0\) on \(A_1\) and \(g=1\) on \(A_0\). Flipping bit \(i\) raises \(g\) by at most \(\lambda_i^a\) for the minimising \(a\), so \[L(g)=\sum_i\mathbb E\lvert g(X)-g(X^i)\rvert=2\,\mathbb E\sum_i\max\{0,g(X^i)-g(X)\}\le2\,\mathrm{CAdv}(f).\]

    The thresholded functions \(G_t=\mathbf 1[g<t]\) satisfy \(\int_0^1I(G_t)\,dt=L(g)\), a coarea identity, so some \(t\in[1/4,3/4]\) has \(I(G_t)\le2L(g)\). For a 1-input \(a\), every \(y\) with \(G_t(y)=0\) has \(d_a(y)\ge1/4\); for a 0-input \(b\), every \(y\) with \(G_t(y)=1\) has \(d_b(y)>3/4\). Hence \(4\lambda^x\) is a fractional certificate at each domain point.

    Editorial check: on 40 random partial functions of 5 bits with random adversary-feasible weights, a threshold in \([1/4,3/4]\) with \(I(G_t)\le2L(g)\) always existed, \(G_t\) extended \(f\), and \(4\lambda^x\) certified every domain input.

    How to reuse it

    To extend a partial function with control of both smoothness and certificates, threshold a Lipschitz potential built from the data and average over thresholds. The coarea step turns an \(L_1\) bound on the potential into a bound on the boundary of some level set.

  2. Querying influential coordinates against a finite influence budget

    Once the completion has bounded total influence, a query strategy that always takes a coordinate of large influence cannot run long: each query removes that coordinate's influence from the expected remaining total. Lemma 4 guarantees a large one while both values remain well represented in the current subcube.

    Restricting to \(x_i=0\) and \(x_i=1\) leaves every other coordinate's influence unchanged on average, so \[I(G|_C)-\tfrac12\bigl[I(G|_{C_0})+I(G|_{C_1})\bigr]=I_i(G|_C).\] With \(m(C)=\min\{\delta_0(C),\delta_1(C)\}\) and certificate costs \(4\,\mathrm{CAdv}(f)\), Lemma 4 gives a coordinate with \(I_i\ge m(C)^2/(16\,\mathrm{CAdv}(f)^2)\).

    Let \(e_t=\mathbb E\,m(C_t)\) after \(t\) queries, the error rate on the domain. It cannot increase, and Jensen gives \(e_t^2\le\mathbb E\,m(C_t)^2\). Telescoping the identity, \[s\,e_s^2\le\sum_{t<s}\mathbb E\,m(C_t)^2\le16\,\mathrm{CAdv}(f)^2\,I(G)=O(\mathrm{CAdv}(f)^3),\] so \(s=O(\mathrm{CAdv}(f)^3/(\varepsilon\delta)^2)\) queries give \(e_s\le\varepsilon\delta\). Lemma 4 itself compares a count of marked pairs with the lowest-degree monomial of a polynomial determinant, using row operations that extract factors \((1-t_i^2)\).

    Editorial checks: the identity above holds exactly for random 4-bit functions and every coordinate; Lemma 4 was tested by computing fractional certificate costs as linear programs for more than a hundred random total functions on 3–5 bits with random subsets \(U_0,U_1\), with no violation and the largest influence at least 5.3 times the bound.

    How to reuse it

    Greedy decision trees that query the most influential variable can be analysed by a potential: total influence decreases by the queried influence in expectation. Any inequality that lower-bounds the maximal influence by a power of the current imbalance then gives a query bound through the same telescoping.

Source: Theorem 2, Lemma 3, Lemma 4 and the proof of Theorem 2 (Eqs. (1)–(8)); Appendix A (Theorem 7). 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. A second, independent and much shorter proof makes the result easier to check and pinpoints the one new ingredient: an influence lower bound from fractional certificates that are small only on part of the cube. It confirms the consequence for quantum computing: on unstructured inputs, quantum query algorithms give at most a polynomial speedup.

Limitations. The paper is a preprint and, unlike Turturean's proof, has not been formally verified; Lemma 4's determinant argument is compact and was checked here only on small instances. Hidden constants are not given. The influence exponent in the appendix is larger than in Turturean's direct bound, and the query bound answers the partial-function formulation, so its exponents are not directly comparable with his. The authors state that they explored this approach for four months with ChatGPT 5.6 and 6, which led to ideas similar to the final proof, but that the missing ingredient came from Turturean's paper.

Description based on the full arXiv HTML of v1, read 2026-11-15: the whole paper, including Appendix A, the AI disclosure and the acknowledgement. Lemma 4 was checked by linear programming on random total functions of 3–5 bits with random subsets \(U_b\); the influence identity (8) exactly; and the completion of Lemma 3 on 40 random partial functions of 5 bits with feasible adversary weights.

Read the accessible explanation

AI-built proof claims to settle the Aaronson–Ambainis conjecture