Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0911.0996 · International Conference on Supercomputing

The Need for Structure in Quantum Speedups

Scott Aaronson, Andris Ambainis

Published Nov 5, 2009• 45 citations
arXivHTMLPDF

Abstract

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate. First, we show that for any problem that is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 7th root of the classical randomized query complexity. (An earlier version of this paper gave the 9th root.) This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O'Donnell et al. (2005) and Dinur et al. (2006), we conjecture that every bounded low-degree polynomial has a "highly influential" variable. Assuming this conjecture, we show that every T-query quantum algorithm can be simulated on most inputs by a poly(T)-query classical algorithm, and that one essentially cannot hope to prove P!=BQP relative to a random oracle.

DOI
10.48550/arxiv.0911.0996

Related papers

Quantum Speedups Require Structure or Depth

Guy Blanc, Jordan Docter, Carmen Strassle +1 more

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.

quant-pharXiv:2608.19158•Aug 20, 2026•0 citations

Parallel Quantum Advantage with Limited Adaptivity Requires Structure

Qipeng Liu, Saachi Mutreja

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 $\mathrm{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.

quant-pharXiv:2608.20297•Aug 21, 2026•0 citations

Quantum speedups need structure

Nathan Keller, Ohad Klein

We prove the following conjecture, raised by Aaronson and Ambainis in 2008: Let $f:\{-1,1\}^n \rightarrow [-1,1]$ be a multilinear polynomial of degree $d$. Then there exists a variable $x_i$ whose influence on $f$ is at least $\mathrm{poly}(\mathrm{Var}(f)/d)$. As was shown by Aaronson and Ambainis, this result implies the following well-known conjecture on the power of quantum computing, dating back to 1999: Let $Q$ be a quantum algorithm that makes $T$ queries to a Boolean input and let $ε,δ> 0$. Then there exists a deterministic classical algorithm that makes $\mathrm{poly}(T,1/ε,1/δ)$ queries to the input and that approximates $Q$'s acceptance probability to within an additive error $ε$ on a $1-δ$ fraction of inputs. In other words, any quantum algorithm can be simulated on most inputs by a classical algorithm which is only polynomially slower, in terms of query complexity.

arXiv:1911.03748•Nov 9, 2019•1 citation

Can graph properties have exponential quantum speedup?

Andrew M. Childs, Daochen Wang

Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity $R$ of any graph property $\mathcal{P}$ has $R(\mathcal{P}) = O(Q(\mathcal{P})^{6})$, where $Q$ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove $R(\mathcal{P}) = O(Q(\mathcal{P})^{3l})$ for any $l$-uniform hypergraph property $\mathcal{P}$ in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.

arXiv:2001.10520•Jan 28, 2020•2 citations

How Much Structure Is Needed for Huge Quantum Speedups?

Scott Aaronson

I survey, for a general scientific audience, three decades of research into which sorts of problems admit exponential speedups via quantum computers -- from the classics (like the algorithms of Simon and Shor), to the breakthrough of Yamakawa and Zhandry from April 2022. I discuss both the quantum circuit model, which is what we ultimately care about in practice but where our knowledge is radically incomplete, and the so-called oracle or black-box or query complexity model, where we've managed to achieve a much more thorough understanding that then informs our conjectures about the circuit model. I discuss the strengths and weaknesses of switching attention to sampling tasks, as was done in the recent quantum supremacy experiments. I make some skeptical remarks about widely-repeated claims of exponential quantum speedups for practical machine learning and optimization problems. Through many examples, I try to convey the "law of conservation of weirdness," according to which every problem admitting an exponential quantum speedup must have some unusual property to allow the amplitude to be concentrated on the unknown right answer(s).

arXiv:2209.06930•Sep 14, 2022•11 citations

The Acrobatics of BQP

Scott Aaronson, DeVon Ingram, William Kretschmer

One can fix the randomness used by a randomized algorithm, but there is no analogous notion of fixing the quantumness used by a quantum algorithm. Underscoring this fundamental difference, we show that, in the black-box setting, the behavior of quantum polynomial-time ($\mathsf{BQP}$) can be remarkably decoupled from that of classical complexity classes like $\mathsf{NP}$. Specifically: -There exists an oracle relative to which $\mathsf{NP^{BQP}}\not\subset\mathsf{BQP^{PH}}$, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which $\mathsf{P}=\mathsf{NP}$ but $\mathsf{BQP}\neq\mathsf{QCMA}$. -Conversely, there exists an oracle relative to which $\mathsf{BQP^{NP}}\not\subset\mathsf{PH^{BQP}}$. -Relative to a random oracle, $\mathsf{PP}=\mathsf{PostBQP}$ is not contained in the "$\mathsf{QMA}$ hierarchy" $\mathsf{QMA}^{\mathsf{QMA}^{\mathsf{QMA}^{\cdots}}}$. -Relative to a random oracle, $\mathsfΣ_{k+1}^\mathsf{P}\not\subset\mathsf{BQP}^{\mathsfΣ_{k}^\mathsf{P}}$ for every $k$. -There exists an oracle relative to which $\mathsf{BQP}=\mathsf{P^{\# P}}$ and yet $\mathsf{PH}$ is infinite. -There exists an oracle relative to which $\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP}=\mathsf{P^{\# P}}$. To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which $\mathsf{BQP}\not \subset \mathsf{PH}$, and associated results about the Forrelation problem. We also introduce new tools that might be of independent interest. These include a "quantum-aware" version of the random restriction method, a concentration theorem for the block sensitivity of $\mathsf{AC^0}$ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.

arXiv:2111.10409•Leibniz international proceedings in informatics•Nov 19, 2021•7 citations
Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate. First, we show that for any problem that is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 7th root of the classical randomized query complexity. (An earlier version of this paper gave the 9th root.) This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O'Donnell et al. (2005) and Dinur et al. (2006), we conjecture that every bounded low-degree polynomial has a "highly influential" variable. Assuming this conjecture, we show that every T-query quantum algorithm can be simulated on most inputs by a poly(T)-query classical algorithm, and that one essentially cannot hope to prove P!=BQP relative to a random oracle.
One of the most basic conjectures in quantum complexity theory states that every ttt-query quantum algorithm can be simulated on most inputs by a poly(t)\mathrm{poly}(t)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 ttt-query ddd-round quantum algorithm can be simulated on most inputs with tO(d2)t^{O(d^2)}tO(d2) 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 BPP\mathsf{BPP}BPP vs. BQP\mathsf{BQP}BQP relative to a random oracle, a similarly longstanding problem.
Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any TTT-query quantum algorithm, its acceptance probability can be approximated on a (1−δ)(1-δ)(1−δ) fraction of inputs, up to εεε additive error, using poly(T,1/ε,1/δ)\mathrm{poly}(T, 1/ε, 1/δ)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.
We prove the following conjecture, raised by Aaronson and Ambainis in 2008: Let f:{−1,1}n→[−1,1]f:\{-1,1\}^n \rightarrow [-1,1]f:{−1,1}n→[−1,1] be a multilinear polynomial of degree ddd. Then there exists a variable xix_ixi​ whose influence on fff is at least poly(Var(f)/d)\mathrm{poly}(\mathrm{Var}(f)/d)poly(Var(f)/d). As was shown by Aaronson and Ambainis, this result implies the following well-known conjecture on the power of quantum computing, dating back to 1999: Let QQQ be a quantum algorithm that makes TTT queries to a Boolean input and let ε,δ>0ε,δ> 0ε,δ>0. Then there exists a deterministic classical algorithm that makes poly(T,1/ε,1/δ)\mathrm{poly}(T,1/ε,1/δ)poly(T,1/ε,1/δ) queries to the input and that approximates QQQ's acceptance probability to within an additive error εεε on a 1−δ1-δ1−δ fraction of inputs. In other words, any quantum algorithm can be simulated on most inputs by a classical algorithm which is only polynomially slower, in terms of query complexity.
Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity RRR of any graph property P\mathcal{P}P has R(P)=O(Q(P)6)R(\mathcal{P}) = O(Q(\mathcal{P})^{6})R(P)=O(Q(P)6), where QQQ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove R(P)=O(Q(P)3l)R(\mathcal{P}) = O(Q(\mathcal{P})^{3l})R(P)=O(Q(P)3l) for any lll-uniform hypergraph property P\mathcal{P}P in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.
I survey, for a general scientific audience, three decades of research into which sorts of problems admit exponential speedups via quantum computers -- from the classics (like the algorithms of Simon and Shor), to the breakthrough of Yamakawa and Zhandry from April 2022. I discuss both the quantum circuit model, which is what we ultimately care about in practice but where our knowledge is radically incomplete, and the so-called oracle or black-box or query complexity model, where we've managed to achieve a much more thorough understanding that then informs our conjectures about the circuit model. I discuss the strengths and weaknesses of switching attention to sampling tasks, as was done in the recent quantum supremacy experiments. I make some skeptical remarks about widely-repeated claims of exponential quantum speedups for practical machine learning and optimization problems. Through many examples, I try to convey the "law of conservation of weirdness," according to which every problem admitting an exponential quantum speedup must have some unusual property to allow the amplitude to be concentrated on the unknown right answer(s).
One can fix the randomness used by a randomized algorithm, but there is no analogous notion of fixing the quantumness used by a quantum algorithm. Underscoring this fundamental difference, we show that, in the black-box setting, the behavior of quantum polynomial-time (BQP\mathsf{BQP}BQP) can be remarkably decoupled from that of classical complexity classes like NP\mathsf{NP}NP. Specifically: -There exists an oracle relative to which NPBQP⊄BQPPH\mathsf{NP^{BQP}}\not\subset\mathsf{BQP^{PH}}NPBQP⊂BQPPH, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which P=NP\mathsf{P}=\mathsf{NP}P=NP but BQP≠QCMA\mathsf{BQP}\neq\mathsf{QCMA}BQP=QCMA. -Conversely, there exists an oracle relative to which BQPNP⊄PHBQP\mathsf{BQP^{NP}}\not\subset\mathsf{PH^{BQP}}BQPNP⊂PHBQP. -Relative to a random oracle, PP=PostBQP\mathsf{PP}=\mathsf{PostBQP}PP=PostBQP is not contained in the "QMA\mathsf{QMA}QMA hierarchy" QMAQMAQMA⋯\mathsf{QMA}^{\mathsf{QMA}^{\mathsf{QMA}^{\cdots}}}QMAQMAQMA⋯. -Relative to a random oracle, Σk+1P⊄BQPΣkP\mathsfΣ_{k+1}^\mathsf{P}\not\subset\mathsf{BQP}^{\mathsfΣ_{k}^\mathsf{P}}Σk+1P​⊂BQPΣkP​ for every kkk. -There exists an oracle relative to which BQP=P#P\mathsf{BQP}=\mathsf{P^{\# P}}BQP=P#P and yet PH\mathsf{PH}PH is infinite. -There exists an oracle relative to which P=NP≠BQP=P#P\mathsf{P}=\mathsf{NP}\neq\mathsf{BQP}=\mathsf{P^{\# P}}P=NP=BQP=P#P. To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which BQP⊄PH\mathsf{BQP}\not \subset \mathsf{PH}BQP⊂PH, and associated results about the Forrelation problem. We also introduce new tools that might be of independent interest. These include a "quantum-aware" version of the random restriction method, a concentration theorem for the block sensitivity of AC0\mathsf{AC^0}AC0 circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.