Almost-everywhere classical simulation of quantum query algorithms: the quantum analogue of average-case derandomization of query algorithms (Aaronson–Ambainis simulation conjecture)

In the query model, every randomized $q$-query algorithm can be simulated on almost all inputs by a deterministic $O(q/\varepsilon)$-query algorithm (Fact 1.1 of Blanc–Lange–Tan 2019, from the easy direction of Yao's lemma). Whether the analogous statement holds for quantum query algorithms — that every $t$-query quantum algorithm has its acceptance probabilities approximated on almost all inputs by a deterministic classical algorithm making only $\mathrm{poly}(t)$ queries — has been open since 1999 or earlier (Conjecture 4 of Aaronson–Ambainis 2014) and is the explicitly highlighted major open problem of Blanc–Lange–Tan's work on constructive derandomization of query algorithms. The standard sufficient route is the Aaronson–Ambainis conjecture: every polynomial $p:\{\pm1\}^n\to[0,1]$ of degree at most $t$ has a coordinate with influence at least $\mathrm{poly}(\mathrm{Var}(p)/t)$. As of August 2026 the general conjecture is open: the best general bound remains the $\exp(t)$ dependence of Dinur–Friedgut–Kindler–O'Donnell, and confirmed cases cover only restricted classes (symmetric functions; completely bounded block-multilinear forms; homogeneous Fourier completely bounded polynomials; random restrictions; and, very recently, parallel/low-round quantum algorithms with $t^{O(d^2)}$ classical queries). The surviving open core is the general, arbitrarily adaptive case, and it is the subject of this problem.

Background

In the query model (decision-tree model) of computation, an algorithm accesses an input $x\in\{0,1\}^N$ only by querying coordinates $x_i$, and its cost is the number of queries; a randomized query algorithm additionally flips coins. A classical result that Blanc, Lange and Tan (2019) isolate as their Fact 1.1 — an easy consequence of the easy direction of Yao's min-max lemma, the averaging principle that some fixed setting of the algorithm's random bits performs on average (over uniform inputs) as well as the randomized algorithm itself — shows that any randomized $q$-query algorithm $R$ can be derandomized on average: for every $\varepsilon$ there is a deterministic $O(q/\varepsilon)$-query algorithm $D$ with $\mathbb{E}_{x}\big[(D(x)-\mathbb{E}_{r}[R(x,r)])^2\big]\le\varepsilon$, i.e. $D$ approximates $R$'s mean output on almost all inputs at only a constant-factor query overhead. Blanc–Lange–Tan made this and related statements (Nisan's STOC 1989 theorem that bounded-error randomized $q$-query algorithms for total decision problems — Boolean functions $f:\{0,1\}^N\to\{0,1\}$ defined on every input — admit exact deterministic $O(q^3)$-query algorithms, and Beals–Buhrman–Cleve–Mosca–de Wolf's Journal of the ACM 2001 result giving deterministic $O(Q(f)^6)$-query algorithms from quantum ones) constructive: e.g. a deterministic procedure running in time $\mathrm{poly}(N)\cdot 2^{O(q/\varepsilon)}$ that outputs an $O(q/\varepsilon)$-query simulator.

A quantum query algorithm $Q$ making $t$ queries applies interleaved arbitrary unitary transformations and $t$ invocations of a quantum oracle unitary (which maps $|i,b\rangle|x\rangle\mapsto|i,b\oplus x_i\rangle|x\rangle$ on the query register), then measures. Its acceptance probability $p_Q(x)$ is a function of the input. By the polynomial method (Beals–Buhrman–Cleve–Mosca–de Wolf, 2001), $p_Q:\{0,1\}^N\to[0,1]$ is a multilinear polynomial of degree at most $2t$; this is the basis of quantum lower bounds and of the connection to Fourier analysis on the Boolean cube (the expansion of such functions as multilinear polynomials in the orthogonal basis of parity functions).

The quantum analogue of Fact 1.1 — whether a $t$-query quantum algorithm can be simulated on almost all inputs by a deterministic classical query algorithm of polynomially related query complexity — is attributed by Aaronson and Ambainis to folklore dating back to 1999 or earlier, and is Conjecture 4 of their paper “The need for structure in quantum speedups” (Theory of Computing, 2014); it is often called the simulation conjecture. Aaronson–Ambainis reduced a sufficient form of it to a now-famous purely Fourier-analytic statement, the Aaronson–Ambainis conjecture: for a polynomial $p:\{\pm1\}^n\to[0,1]$ of degree at most $t$, define the influence of coordinate $i$ as $\mathrm{Inf}_i(p)=\mathbb{E}_x\,|p(x)-p(x^{\oplus i})|$ (where $x^{\oplus i}$ flips the $i$-th bit) and the variance $\mathrm{Var}(p)$ over uniform $x$; then some coordinate satisfies $\mathrm{Inf}_i(p)\ge\mathrm{poly}(\mathrm{Var}(p)/t)$. Under this conjecture the simulation is even constructive, with an efficient meta-algorithm conditional on $\mathsf{P}=\mathsf{P}^{\#\mathsf{P}}$ (here $\#\mathsf{P}$ is the counting complexity class). Despite almost two decades of work, the best general influence bound remains the $\exp(t)$ dependence implied by the Fourier-tails result of Dinur–Friedgut–Kindler–O'Donnell (STOC 2006), and all known proof techniques (which rely on hypercontractivity — a family of inequalities controlling the noise-sensitivity of low-degree polynomials, for which the exponential dependence on degree is inherent) stall at that barrier. Confirmed special cases include symmetric functions (Aaronson–Ambainis 2014); completely bounded block-multilinear forms — the norm-constrained class of multilinear polynomials that, by Arunachalam–Briët–Palazuelos (SIAM Journal on Computing, 2019), exactly characterizes the acceptance polynomials of quantum query algorithms — proven by Bansal–Sinha–de Wolf (2022) using free probability (asymptotic operator-algebra techniques), yielding almost-everywhere classical simulation for algorithms including $k$-fold Forrelation (a canonical unstructured black-box problem with a maximal quantum-over-classical query separation); homogeneous Fourier completely bounded polynomials (Escudero Gutiérrez, 2023); a non-negligible fraction of random restrictions (each coordinate fixed at random with a small probability; Bhattacharya, 2024); and, very recently, a noncommutative analogue for Hamiltonians built from anti-commuting Pauli strings (tensor products of the elementary Pauli matrices; Slote–Volberg–Zhang, 2026).

The question matters beyond quantum query complexity. A positive answer would give broad justification for the thesis that exponential quantum speedups require structured inputs (the “need for structure” principle); would rule out the query-complexity approach to separating $\mathsf{BPP}$ (bounded-error randomized polynomial time) from $\mathsf{BQP}$ (bounded-error quantum polynomial time) relative to a random oracle (an oracle whose answers are independent random bits; open since Fortnow–Rogers 1999); and would make unconditional the certifiable-randomness protocol (a protocol whose outputs are accompanied by a proof of statistical randomness) of Yamakawa–Zhandry (Journal of the ACM, 2024), whose security is currently proven only under the Aaronson–Ambainis conjecture or against shallow-query adversaries (Khurana–Roberts–Tal, 2026).

Problem Statement

Prove or refute the quantum analogue of average-case derandomization of query algorithms (the simulation conjecture, Conjecture 4 of Aaronson–Ambainis, highlighted as the major open problem in Remark 1 of Blanc–Lange–Tan): for every quantum query algorithm $Q$ making $t$ queries to an input $x\in\{0,1\}^N$, there exists — even just non-constructively — a deterministic classical query algorithm $D$ making $\mathrm{poly}(t)$ queries whose output approximates the acceptance probability $p_Q(x)$ of $Q$ on almost all inputs, e.g. $\Pr_{x\sim\{0,1\}^N}\big[|D(x)-p_Q(x)|\le\tfrac13\big]\ge0.99$ with query complexity $\mathrm{poly}(t)$ (with $\mathrm{poly}(t,1/\varepsilon,1/\delta)$ queries for approximation error $\varepsilon$ and success probability $1-\delta$, as quantified in Conjecture 4 of Aaronson–Ambainis). An admissible and standard sufficient route is a proof of the Aaronson–Ambainis influence conjecture: every polynomial $p:\{\pm1\}^n\to[0,1]$ of degree at most $t$ has some coordinate $i$ with $\mathrm{Inf}_i(p)=\mathbb{E}_x|p(x)-p(x^{\oplus i})|\ge\mathrm{poly}(\mathrm{Var}(p)/t)$. A valid proof must cover all $t$-query quantum algorithms — not merely restricted classes such as nonadaptive or low-round (parallel) algorithms (whose quantum oracle calls are grouped into few synchronized rounds), symmetric functions, or completely bounded block-multilinear/homogeneous special cases — though a proof exploiting the completely bounded structure of quantum acceptance polynomials is admissible if it applies to every quantum query algorithm. Constructive solutions (an efficient deterministic procedure outputting the simulator, as Blanc–Lange–Tan achieved for the classical randomized case) are welcome strengthenings, consistent with the source framing, but non-constructive existence already answers the stated question. A refutation consists of an explicit family of $t$-query quantum algorithms whose acceptance probabilities cannot be approximated within additive error $1/3$ on a $0.99$ fraction of inputs by any deterministic classical algorithm of $\mathrm{poly}(t)$ query complexity, for infinitely many $t$.

References

1. Guy Blanc, Jane Lange, Li-Yang Tan, Constructive derandomization of query algorithms, arXiv:1912.03042 (2019), DOI 10.48550/arXiv.1912.03042, https://arxiv.org/abs/1912.03042
2. Scott Aaronson, Andris Ambainis, The need for structure in quantum speedups, Theory of Computing 10(6):133–166 (2014), arXiv:0911.0996, DOI 10.4086/toc.2014.v010a006, https://doi.org/10.4086/toc.2014.v010a006
3. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf, Quantum lower bounds by polynomials, Journal of the ACM 48(4):778–797 (2001), DOI 10.1145/502090.502097, https://doi.org/10.1145/502090.502097
4. Noam Nisan, CREW PRAMs and decision trees, Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC 1989), pp. 327–335, DOI 10.1145/73007.73038, https://doi.org/10.1145/73007.73038
5. Irit Dinur, Ehud Friedgut, Guy Kindler, Ryan O'Donnell, On the Fourier tails of bounded functions over the discrete cube, Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006), DOI 10.1145/1132516.1132580, https://doi.org/10.1145/1132516.1132580
6. Srinivasan Arunachalam, Jop Briët, Carlos Palazuelos, Quantum query algorithms are completely bounded forms, SIAM Journal on Computing (2019), DOI 10.1137/18m117563x, https://doi.org/10.1137/18m117563x
7. Nikhil Bansal, Makrand Sinha, Ronald de Wolf, Influence in completely bounded block-multilinear forms and classical simulation of quantum algorithms, arXiv:2203.00212 (2022), https://arxiv.org/abs/2203.00212
8. Francisco Escudero Gutiérrez, Influences of Fourier completely bounded polynomials and classical simulation of quantum algorithms, arXiv:2304.06713 (2023), https://arxiv.org/abs/2304.06713
9. Sreejata Kishor Bhattacharya, Aaronson-Ambainis Conjecture Is True For Random Restrictions, arXiv:2402.13952 (2024), https://arxiv.org/abs/2402.13952
10. Joseph Slote, Alexander Volberg, Haonan Zhang, Tightness of and counterexamples to several quantum estimates, arXiv:2608.04411 (2026), https://arxiv.org/abs/2608.04411
11. Takashi Yamakawa, Mark Zhandry, Verifiable Quantum Advantage without Structure, Journal of the ACM 71 (2024), DOI 10.1145/3658665, https://doi.org/10.1145/3658665
12. Dakshita Khurana, Bhaskar Roberts, Avishay Tal, Certified Randomness without Structure Against Shallow-Query Adversaries, arXiv:2608.24832 (2026), https://arxiv.org/abs/2608.24832
13. Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan, Quantum Speedups Require Structure or Depth, arXiv:2608.19158 (2026), https://arxiv.org/abs/2608.19158