Several restricted quantum-query algorithms can be approximated by deterministic classical algorithms on most inputs, according to an arXiv preprint dated 20 Aug 2026. For an algorithm making T queries in parallel, the simulator uses a number of queries polynomial in T, 1/ε and 1/δ, and matches the quantum algorithm’s acceptance probability within an additive ε on a 1−δ fraction of inputs.
This is an almost-everywhere guarantee: it applies to a 1−δ fraction of inputs rather than promising a match on every input. The study is theoretical, working with Boolean oracle inputs and dense and uniform oracle distributions rather than an empirical participant or dataset sample.
Where the theorem applies
The paper also proves dense-versus-uniform indistinguishability for parallel-query algorithms—in other words, the algorithm’s acceptance probability changes only by a bounded amount when the oracle comes from either distribution. The bound has the form C·T^a·δ^b, with absolute constants.
One extension covers a terminal-parallel design—a final parallel stage after a bounded adaptive quantum-query prefix. With Tq queries in that final stage, classical simulation is proved when the prefix length r obeys r=O(log K/log log K).
Another terminal-parallel theorem allows Tc adaptive classical queries before Tq parallel quantum queries. Its classical simulator uses polynomially many queries and stays within additive error ε on a 1−δ fraction of inputs.
A separate construction handles every fixed number of adaptive parallel-query layers for uniform oracles. It puts the probability that approximation error exceeds ε at no more than δ; the theorem is explicitly limited to a fixed layer count and does not establish the same result for unbounded or generally growing adaptivity.
How the proofs work
The central technical step is a randomized coupling, or a way of pairing outcomes from two distributions. It maps any dense oracle distribution exactly into the uniform distribution while keeping each coordinate’s flip probability small.
For the parallel case, the proof combines that coordinate-wise construction with a BBBV hybrid—a step-by-step comparison of oracle changes—and a trace-distance bound on how distinguishable the resulting quantum states are. It relies on pre-query weights that do not depend on the oracle.
For the fixed-round case, the proof uses strong induction. At each layer it regularizes the distribution of query weights, explicitly queries coordinates carrying unusually large weight, and then applies a variance bound to the rest.
The boundary of the claim
The result is not a general proof of classical simulation for all quantum query algorithms. The broader question of arbitrary fully adaptive algorithms remains unresolved, and the fixed-round theorem gives direct simulation rather than the stronger dense-versus-uniform indistinguishability statement for multiple adaptive layers.
The authors also state an informal certifiable-randomness protocol for restricted quantum provers. The proposed classes use either constant-round parallel queries or a polynomial classical prefix followed by one parallel quantum layer; the implication is not independently implemented or evaluated.
The work analyzes mathematical algorithm classes and oracle distributions, not people, animals, cells or an empirical dataset. It therefore offers no direct evidence about real-world performance or randomness certification in practice.
The document also discloses that ChatGPT 5.5 Pro assisted with proofs of Theorem 1.8.
Paper data and sources
Original title: Parallel Quantum Advantage with Limited Adaptivity Requires Structure
Authors: Qipeng Liu, Saachi Mutreja
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text