Parallel Quantum Advantage with Limited Adaptivity Requires Structure
Abstract
Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any T-query quantum algorithm, its acceptance probability can be approximated on a (1−δ) fraction of inputs, up to ε additive error, using poly(T, 1/ε, 1/δ) classical queries. At a high level, the conjecture suggests that exponential quantum speedups are possible only on sufficiently structured inputs. In this work, we make progress on this conjecture by proving it for quantum algorithms that make massively parallel quantum queries. In contrast, Yamakawa and Zhandry (Journal of the ACM, 2024) showed that quantum algorithms restricted to parallel queries can still achieve exponential speedups over classical algorithms for sampling problems. We establish our simulation theorem by proving the stronger statement that parallel-query quantum algorithms cannot distinguish the uniform distribution over oracles from oracles drawn from so-called "dense distributions". Our main technical contribution is a coupling theorem that relates the uniform distribution over oracles to oracles drawn from dense distributions. We further extend this approach beyond the purely parallel setting. We prove simulation theorems for quantum algorithms with constant rounds of adaptivity, and for quantum algorithms with a bounded quantum-query prefix followed by a massively parallel quantum-query stage.
Related
- Quantum Query Advantage Requires Space
- Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries
- Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D
- Quantum Statistical Memory Advantage Reveals Predictive Structure in Chaotic Invariant Measures
- On the Power of Adaptivity in Testing Quantum States in Fidelity
BibTeX
@misc{liu2026parallel,
title = {{Parallel Quantum Advantage with Limited Adaptivity Requires Structure}},
author = {Qipeng Liu and Saachi Mutreja},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.20297},
eprint = {2608.20297},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.20297},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Parallel Quantum Advantage with Limited Adaptivity Requires Structure
AU - Qipeng Liu
AU - Saachi Mutreja
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2608.20297
UR - https://arxiv.org/abs/2608.20297
AB - Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any T-query quantum algorithm, its acceptance probability can be approximated on a (1−δ) fraction of inputs, up to ε additive error, using poly(T, 1/ε, 1/δ) classical queries. At a high level, the conjecture suggests that exponential quantum speedups are possible only on sufficiently structured inputs. In this work, we make progress on this conjecture by proving it for quantum algorithms that make massively parallel quantum queries. In contrast, Yamakawa and Zhandry (Journal of the ACM, 2024) showed that quantum algorithms restricted to parallel queries can still achieve exponential speedups over classical algorithms for sampling problems. We establish our simulation theorem by proving the stronger statement that parallel-query quantum algorithms cannot distinguish the uniform distribution over oracles from oracles drawn from so-called "dense distributions". Our main technical contribution is a coupling theorem that relates the uniform distribution over oracles to oracles drawn from dense distributions. We further extend this approach beyond the purely parallel setting. We prove simulation theorems for quantum algorithms with constant rounds of adaptivity, and for quantum algorithms with a bounded quantum-query prefix followed by a massively parallel quantum-query stage.
ER -