BQP vs Classical Classes

Where does $\mathsf{BQP}$ sit among the classical classes? The honest answer is: pinned between two of them by theorems, but separated from them only by conjecture. This lesson lays out the proven containments, explains the one genuinely nontrivial upper bound ( $\mathsf{BQP} \subseteq \mathsf{PSPACE}$ ), and is careful about what is believed versus what is known.

The proven sandwich

The containments that are theorems are

\mathsf{P} \subseteq \mathsf{BPP} \subseteq \mathsf{BQP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXP}.

The first inclusions going up are easy. A deterministic computation is a randomized one that ignores its coins, so $\mathsf{P} \subseteq \mathsf{BPP}$ . A quantum computer can simulate a classical reversible computation, and any randomized classical algorithm can be made reversible and have its coin flips supplied by Hadamard-prepared qubits measured at the end; hence $\mathsf{BPP} \subseteq \mathsf{BQP}$ . The genuinely interesting inclusion is the upper one.

Why BQP ⊆ PSPACE

A polynomial-size quantum circuit on $m = \mathrm{poly}(n)$ qubits acts on a state vector with $2^m$ complex amplitudes — exponentially many to store all at once. The key insight is that we do not need to store them. The acceptance probability is

p(x) = \sum_{y \,:\, y \text{ accepts}} \big| \braket{y | C | x} \big|^2 ,

and each amplitude $\braket{y | C_g \cdots C_1 | x}$ is a sum over computational paths:

\braket{y | C | x} = \sum_{i_1, \dots, i_{g-1}} \braket{y|C_g|i_{g-1}} \cdots \braket{i_1|C_1|x}.

Each path's contribution is a product of $g = \mathrm{poly}(n)$ individual gate matrix entries, each computable to high precision in polynomial time and space. There are exponentially many paths, but we can enumerate them one at a time, accumulating the running sum and reusing the same polynomial-size memory cell for each path. Squaring and summing the accepting amplitudes likewise reuses space. The total time is exponential, but the space is polynomial — so $\mathsf{BQP} \subseteq \mathsf{PSPACE}$ . (A sharper analysis places $\mathsf{BQP} \subseteq \mathsf{PP} \subseteq \mathsf{PSPACE}$ , but the path-sum argument already gives the headline result.)

BQP vs NP: incomparable as far as we know

A common misconception is that quantum computers solve $\mathsf{NP}$ -complete problems. There is no evidence for this. $\mathsf{BQP}$ and $\mathsf{NP}$ are believed to be incomparable:

$\mathsf{NP} \subseteq \mathsf{BQP}$ is considered very unlikely. The natural quantum approach, Grover search, gives only a quadratic speedup for unstructured search and the BBBV lower bound (a later lesson) shows that is optimal in the black-box setting — far short of the exponential speedup a containment would require.
$\mathsf{BQP} \subseteq \mathsf{NP}$ is also doubtful: factoring is in $\mathsf{BQP}$ and (as a decision problem) in $\mathsf{NP} \cap \mathsf{coNP}$ , but problems like Forrelation give oracle evidence that $\mathsf{BQP}$ contains things outside the polynomial hierarchy, hence outside $\mathsf{NP}$ relative to an oracle.

The cleanest summary: factoring sits in $\mathsf{BQP}$ but is not believed $\mathsf{NP}$ -complete, so even a working quantum computer would not obviously crack every $\mathsf{NP}$ problem.

Separations are oracular, not absolute

We do not know $\mathsf{BQP} \ne \mathsf{BPP}$ . Proving it would, among other things, require proving $\mathsf{P} \ne \mathsf{PSPACE}$ , a long-standing open problem implied by the chain above (since $\mathsf{BPP} = \mathsf{BQP}$ together with other collapses would propagate). What we do have are oracle separations: relative to a black-box function, problems like Simon's problem and Forrelation are exponentially easier for quantum machines than for classical ones, giving worlds in which $\mathsf{BPP}^{\mathcal O} \ne \mathsf{BQP}^{\mathcal O}$ . Oracle separations are strong heuristic evidence but are not proofs about the unrelativized classes — there exist oracles relativizing the question both ways for many class pairs.

Takeaways

$\mathsf{BQP}$ is sandwiched $\mathsf{BPP} \subseteq \mathsf{BQP} \subseteq \mathsf{PSPACE}$ by theorems, is believed incomparable to $\mathsf{NP}$ , and is not known to be strictly larger than $\mathsf{BPP}$ — that separation would resolve major open problems. Quantum advantage is a claim about time complexity within the decidable; it never escapes $\mathsf{PSPACE}$ .