Skip to content
Preprint

Quantum Speedups Require Structure or Depth

Aug 2026 · 2 citations · ⚡ 1 influential
Physics Computer Science

TL;DR

This work settles 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, suggesting that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth.

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.

View source

Similar papers

Preprint Aug 2026

Parallel Quantum Advantage with Limited Adaptivity Requires Structure

The simulation theorem is established 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, and a coupling theorem is a coupling theorem that relates the uniform distribution over oracles t...

Qi-Peng Liu, Saachi Mutreja · 2 citations · ⚡1
Preprint Sep 2026

Quantum Query Advantage Requires Space

The separation is obtained through a one-bit filtered-parity construction and a space-sensitive quantum lower bound based on compressed-oracle capacity and a new parity-to-capacity inequality, which may be of independent interest.

Minbo Gao, Zheng-Feng Ji, Zi-Yi Xie · 0 citations
Sep 2026

Improved Quantum Query Bounds for Boolean Matrix Product Verification

We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound o...

Amin Shiraz Gilani, François Le Gall, Xing-Yu Zhou · 0 citations
Preprint Sep 2026

Quantum Query Complexity Beyond the Worst Case

Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results. $(1)$ We show that there is a total fun...

Srinivasan Arunachalam, Yan-Lin Chen, Amin Shiraz Gilani · 0 citations
Preprint Sep 2026

Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE

A deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest, and a full sample--time tradeoff that interpolates between exponential and polynomial runtime is established.

Robin Kothari, Tony Metger, R. O'Donnell et al. · 0 citations
Preprint Oct 2026

Distributional Quantum Query Complexity

This work gives distributional joint computation lower bounds for the composition, direct sum, and direct product problems, and introduces some new tools for handling quantum query lower bounds, including a new ``Shaltiel-free''measure of quantum query complexity, which characterizes the composition behavior of distrib...

S. Ben-David, M. H. Ebtehaj · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.