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

The Aaronson–Ambainis conjecture predicts that every low-degree polynomial with non-negligible variance has a variable of appreciable influence. If true, it would imply classical simulation of quantum query algorithms on almost all inputs using only polynomially more queries.

Known results

Dinur, Friedgut et al. (2006): proved a weaker bound with exponential rather than polynomial 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, covering a special class of quantum algorithms.

2020 and August 2026 developments

Keller and Klein’s claimed proof was retracted after Ivanishvili identified a fatal flaw in Lemma $5.3$ . In August $2026$ , bounded-round and parallel-query coupling theorems established polynomial-type classical simulations in those regimes, showing that exponential separations require substantial adaptivity; neither result proves the full conjecture.

Current status (as of August 2026): Partial simulation theorems are known for important restricted regimes, while the full Aaronson–Ambainis conjecture remains open.

Aaronson–Ambainis conjecture

Progress summary

Primary source

Additional references

Solutions 0