I will discuss the now-ancient question of where BQP, Bounded-Error Quantum Polynomial-Time, fits in among classical complexity classes. After reviewing some basics from the 90s, I will discuss the Forrelation problem that I introduced in 2009 to yield an oracle separation between BQP and PH, and the dramatic completion of that program by Ran Raz and Avishay Tal in 2018. I will then discuss very recent work, with William Kretschmer and DeVon Ingram, which leverages the Raz-Tal theorem, along with a new "quantum-aware" random restriction method, to obtain results that illustrate just how differently BQP can behave from BPP. These include oracles relative to which NP^{BQP} ̸ ⊂ BQP^{PH} - solving a 2005 open problem of Lance Fortnow - and conversely, relative to which BQP^{NP} ̸ ⊂ PH^{BQP}; an oracle relative to which 𝖯 = NP and yet BQP ≠ QCMA; an oracle relative to which NP ⊆ BQP yet PH is infinite; an oracle relative to which 𝖯 = NP≠ BQP = PP; and an oracle relative to which PP = PostBQP ̸ ⊂ QMA^{QMA^{…}}. By popular demand, I will also speculate about the status of BQP in the unrelativized world.
The
2-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating
BQP and
PH relative to an oracle. A natural question is therefore to ask what are the minimal quantum resources needed to solve this problem. We show that
2-Forrelation can be solved using Instantaneous Quantum Polynomial-time (
IQP) circuits, a restricted model of quantum computation in which all gates commute. Concretely, signed
2-Forrelation can be solved by a classical random choice between two one-query
IQP circuits, while the absolute-value variant uses two independent executions of this randomized procedure. This answers a recent open question of Girish (STOC 2026) on the power of commuting quantum computations. For the Raz-Tal distribution, this randomization is unnecessary. We use this to show that there is an oracle
O such that
IQPO⊆PHO, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between
IQP and
DQC1. We prove Fourier growth bounds for multi-query
IQP circuits, including bounds in terms of the size of their accepting set. Our results suggest a possible route toward decision-based quantum advantage within the restricted
IQP model. The key ingredient is an algebraic identity of the quadratic function
Q(x)=∑i<jxixj that allows extracting inner-product phases within an
IQP circuit.
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) can be remarkably decoupled from that of classical complexity classes like
NP. Specifically: -There exists an oracle relative to which
NPBQP⊂BQPPH, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which
P=NP but
BQP=QCMA. -Conversely, there exists an oracle relative to which
BQPNP⊂PHBQP. -Relative to a random oracle,
PP=PostBQP is not contained in the "
QMA hierarchy"
QMAQMAQMA⋯. -Relative to a random oracle,
Σk+1P⊂BQPΣkP for every
k. -There exists an oracle relative to which
BQP=P#P and yet
PH is infinite. -There exists an oracle relative to which
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, 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 circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.
Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.
Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is, whether QMA = QCMA or QCMA != QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07). This longstanding question was recently answered by works of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC '26) and Bostanci, Huang, and Vaikuntanathan (FOCS '26), which showed that quantum proofs are more powerful than classical ones in the classical-oracle setting.
However, it remains unclear what exactly makes quantum proofs more powerful than classical ones. In the information-theoretic setting, a family of quantum states is not classicalizable if and only if it is unclonable. Indeed, these recent works also explicitly highlight the unclonability of their quantum proofs as a key mechanism behind their separations, and their arguments crucially rely on this property. This raises the question of whether unclonability is necessary for quantum proofs to be more powerful than classical ones.
In this work, we show that even clonable quantum proofs can be more powerful than classical ones relative to a classical oracle by constructing a classical oracle O such that QCMA^O != ClonableQMA^O. This resolves the open question of Nehoran and Zhandry (ITCS '24), who established the analogous separation relative to a quantum oracle. We also show a classical-oracle separation between BQP/clonableqpoly and BQP/poly, and give applications of our results to quantum cryptography.