Quantum Speedups Require Structure or Depth
2026-08-19 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study how well quantum algorithms that run in multiple steps can be copied by classical algorithms using roughly the same number of steps raised to some power. They prove that any quantum algorithm with t queries and d rounds can be approximated by a classical algorithm making about t to the power of d squared queries on most inputs. This means big quantum speedups without special problem structures need complex quantum circuits with many layers. Their results also provide new insight into the relationship between classical and quantum computer power when using random oracles.
quantum algorithmclassical simulationquery complexityparallel quantum algorithmsquantum speedupcircuit depthBPP vs BQPrandom oraclequantum complexity theory
Authors
Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan
Abstract
One of the most basic conjectures in quantum complexity theory states that every $t$-query quantum algorithm can be simulated on most inputs by a $\mathrm{poly}(t)$-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups. We settle this conjecture for parallel quantum algorithms, showing that every $t$-query $d$-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms. Our techniques also carry new implications for the status of $\mathsf{BPP}$ vs. $\mathsf{BQP}$ relative to a random oracle, a similarly longstanding problem.