For every T-query quantum algorithm A, there is a polynomial p such that, for every epsilon,delta>0, there exists a classical randomized query algorithm C making at most p(T,1/epsilon,1/delta) queries whose acceptance probability satisfies |Pr[A^x accepts]-Pr[C^x accepts]|≤epsilon for at least a (1-delta) fraction of inputs x.

Aaronson–Ambainis conjecture

Aaronson and Ambainis introduced the conjecture in 2008: every bounded-query quantum algorithm should be approximable on almost all inputs by a classical randomized algorithm using only polynomially more queries. It is equivalent to a conjecture about influential variables in bounded low-degree Boolean polynomials.

Known results

Dinur, Friedgut et al. (2006): proved a weaker influence bound with exponential dependence on the degree.
Montanaro (2012): proved the conjecture for equal-magnitude block-multilinear forms.
O’Donnell and Zhao (2016): reduced the problem to one-block-decoupled polynomials.
Bansal, Sinha, and de Wolf (2022): proved it for completely bounded block-multilinear forms.

August 2026 bounded-adaptivity progress

A new preprint reports the conjectured simulation for parallel and bounded-round algorithms, with query cost $2^{O(d^{2})}\left(t\log(1/\delta)/\varepsilon\right)^{O(d)}$ for $d$ rounds. The unrestricted adaptive case remains open. Keller and Klein’s earlier claimed proof was withdrawn after Ivanishvili found a fatal flaw in Lemma $5.3$ .

Current status (as of August 2026): The full conjecture for unrestricted adaptive quantum algorithms remains open; reported progress establishes it only for parallel and bounded-adaptivity classes.

Aaronson–Ambainis conjecture

Primary source

Additional references

Progress summary

Solutions 0