BQP versus P, NP, and PSPACE

The class $\mathsf{BQP}$ — bounded-error quantum polynomial time — is the formal home of "what a quantum computer can efficiently do." Pinning down where it sits inside the classical complexity zoo is the central question of quantum computational power: it asks, in a language complexity theorists can argue about precisely, how much quantum mechanics buys us over classical computation. The honest answer is that we know surprisingly little for certain. What is proven is a short chain of containments; what is interesting — whether quantum computers crack $\mathsf{NP}$ -complete problems, whether they beat classical randomness — remains conjectural, and provably hard to settle. Two engines drive everything here. The first is the Feynman path-sum: a quantum amplitude for a polynomial-size circuit is a sum over exponentially many computational histories, and that single identity, read two ways, delivers the proven upper bounds $\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE}$ — evaluate the sum in reusable memory for the space bound, read it as a signed count of paths for the counting bound. The second is quantum query complexity: the BBBV theorem shows that unstructured search — the abstraction of an $\mathsf{NP}$ -complete problem — costs $\Theta(\sqrt{N})$ quantum queries, only a quadratic saving over brute force. That is why nobody expects $\mathsf{NP}\subseteq\mathsf{BQP}$ , and why Shor's factoring, which exploits hidden periodicity rather than brute search, is the exception rather than the rule. Every known separation between these classes is relativized — true relative to an oracle — so the real question lives beyond the reach of the very techniques that prove the containments.

Key takeaways

$\mathsf{BQP}$ , the problems a quantum computer solves in polynomial time with bounded error, obeys the proven chain $\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE}$ .
The upper bounds come from one identity — the Feynman path-sum — evaluated in polynomial space (giving $\mathsf{PSPACE}$ ) or read as a signed count (giving $\mathsf{PP}$ , the strongest known bound).
No containment between $\mathsf{BQP}$ and $\mathsf{NP}$ is known in either direction; there are oracles making each fail to contain the other, so any real resolution must be non-relativizing.
Grover search is only quadratic: unstructured search costs $\Theta(\sqrt{N})$ quantum queries (BBBV lower bound), so $\mathsf{NP}$ -complete problems get no generic exponential speedup.
Shor's algorithm puts factoring and discrete log in $\mathsf{BQP}$ by exploiting algebraic periodicity, but those problems are not believed $\mathsf{NP}$ -complete, so they are no evidence for $\mathsf{NP}\subseteq\mathsf{BQP}$ .
Key idea: the quantum power that puts $\mathsf{BQP}$ below $\mathsf{PSPACE}$ is amplitude interference summed over exponentially many paths, while the barrier that keeps $\mathsf{NP}$ out is the $\Theta(\sqrt{N})$ query cost of unstructured search — two different axes, which is why quantum beats classical on structure but not on brute force.

The core insight

The amplitude $\langle x\mid U_T\cdots U_1\mid 0\rangle$ of a polynomial-size circuit is a Feynman sum over exponentially many paths; summing it in polynomial space gives $\mathsf{BQP}\subseteq\mathsf{PSPACE}$ and reading it as a signed count gives $\mathsf{BQP}\subseteq\mathsf{PP}$ , whereas the $\mathsf{BQP}$ -versus- $\mathsf{NP}$ frontier is governed not by amplitude-summing but by query lower bounds that forbid generic exponential speedups for unstructured search.

Where this lives today

The $\mathsf{BQP}$ -versus-classical map is the load-bearing assumption under three live enterprises. Post-quantum cryptography is the largest: because Shor puts factoring and discrete log in $\mathsf{BQP}$ , RSA, Diffie–Hellman and elliptic-curve schemes fall to a large fault-tolerant quantum computer, so standards bodies have moved to lattice- and code-based schemes tied to $\mathsf{NP}$ -hardness, precisely where no speedup beyond Grover's quadratic factor is known. Quantum-advantage experiments are the second: random-circuit sampling and BosonSampling are chosen because they live in $\mathsf{BQP}$ -like sampling classes while being classically hard for reasons argued through $\mathsf{PP}$ and $\#\mathsf{P}$ — the fine structure of $\mathsf{BQP}\subseteq\mathsf{PP}$ is exactly what lets researchers claim a classical simulation would collapse the polynomial hierarchy. The third is the open problem itself: the 2018 Raz–Tal oracle separating $\mathsf{BQP}$ from the polynomial hierarchy, and work on proofs of quantumness and $\mathsf{QMA}$ -complete problems like Local Hamiltonian, are all attempts to prove unconditionally where quantum efficient computation really sits.

The physical picture

Picture a quantum computation as a branching tree of histories. A classical probabilistic machine follows one branch with some probability and you average; a quantum machine sends amplitude down every branch at once, and the branches interfere — amplitudes can add or cancel. All the power of quantum computing lives in that interference. To reproduce the answer classically you must, in the worst case, add up exponentially many branches — and a polynomial-space machine can do exactly that by walking them one at a time and reusing its memory, which is why $\mathsf{BQP}$ sits inside $\mathsf{PSPACE}$ . The first figure is the map this article is about: the proven nest of classes, with $\mathsf{NP}$ straddling $\mathsf{BQP}$ because neither is known to contain the other.

Figure

The proven landscape: P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE as nested classes, with NP straddling BQP — neither class is known to contain the other, and every known separation needs an oracle

Why doesn't quantum interference simply crack $\mathsf{NP}$ ? Because solving an $\mathsf{NP}$ -complete problem "from the outside" is finding a needle in an unstructured haystack of $N$ candidates, and interference only helps when the haystack has hidden structure the amplitudes can resonate with. For a featureless search the best a quantum computer can do is rotate amplitude toward the marked item a little at a time — Grover's geometric rotation — gaining a factor $\sqrt{N}$ , never an exponential one. BBBV makes this a hard theorem, not a failure of imagination: no quantum algorithm beats $\Theta(\sqrt{N})$ queries. The second figure shows what that quadratic ceiling costs, with a concrete number.

Figure

Grover search is only quadratically faster: on a log-log axis the quantum cost (π/4)√N is a line of half the classical slope, so at N = 10⁶ items a quantum computer needs about 785 oracle queries versus 10⁶ classically — a √N gain, never exponential

Shor's algorithm looks like magic only because factoring secretly hides a period, and the quantum Fourier transform is exquisitely tuned to detect periodicity — that is structure, not brute force. The lesson the two figures teach together: $\mathsf{BQP}$ beats classical computation exactly where algebraic structure is available, a different axis from the exhaustive-search axis along which $\mathsf{NP}$ -completeness lives.

The core equations

The proven skeleton is a chain of five classes. Each inclusion is a theorem; none of the strict separations is known — even $\mathsf{P}\ne\mathsf{PSPACE}$ is open, though widely believed. This is the map onto which every claim below must be placed.

\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE} \qquad (1)

where: $\mathsf{P}$ — deterministic polynomial time; $\mathsf{BPP}$ — bounded-error probabilistic polynomial time; $\mathsf{BQP}$ — bounded-error quantum polynomial time; $\mathsf{PP}$ — probabilistic polynomial time with unbounded error (majority vote); $\mathsf{PSPACE}$ — polynomial space. Reading: a quantum machine can run any randomized machine, so it sits above $\mathsf{BPP}$ ; the path-sum puts it below $\mathsf{PP}$ , and $\mathsf{PP}\subseteq\mathsf{PSPACE}$ is classical. Membership in $\mathsf{BQP}$ is defined by a completeness/soundness gap, not by exact acceptance. The thresholds $2/3$ and $1/3$ look arbitrary, and they are — any inverse-polynomial gap defines the same class after amplification.

x\in L_{\mathrm{yes}}\Rightarrow\Pr[\text{accept}]\ge\tfrac{2}{3},\qquad x\in L_{\mathrm{no}}\Rightarrow\Pr[\text{accept}]\le\tfrac{1}{3} \qquad (2)

where: $L_{\mathrm{yes}},L_{\mathrm{no}}$ — the yes/no instances of a promise language $L$ ; $\tfrac{2}{3},\tfrac{1}{3}$ — completeness and soundness thresholds. Reading: the gap of $1/3$ between the two cases is what makes repeated runs informative; Derivation two of the worked examples shows how any $1/\mathrm{poly}$ gap is boosted to $1-2^{-\mathrm{poly}}$ . The single most important identity is the Feynman path-sum. The amplitude to end in basis state $x$ is a sum over all intermediate basis-state sequences, each contributing a product of one-gate transition amplitudes.

\langle x\mid U_T U_{T-1}\cdots U_1\mid 0^n\rangle=\sum_{p_1,\dots,p_{T-1}}\;\prod_{t=1}^{T}\langle p_t\mid U_t\mid p_{t-1}\rangle \qquad (3)

where: $U_t$ — the $t$ -th gate, a unitary on a poly-size register; $p_t\in\{0,1\}^n$ — a computational-basis (path) state at time $t$ , with $p_0=0^n$ and $p_T=x$ ; $T$ — circuit size, polynomial in $n$ ; each $\langle p_t\mid U_t\mid p_{t-1}\rangle$ — a one-gate amplitude computable to the needed precision. Reading: there are up to $2^{n(T-1)}$ paths, so this sum is exponentially long but each term is a tiny product — the tension that makes it $\mathsf{PSPACE}$ but not obviously $\mathsf{P}$ . Squaring and summing the amplitudes over accepting outcomes gives the acceptance probability the class definition refers to.

\Pr[\text{accept}]=\sum_{x\in\text{acc}}\Big|\sum_{\text{paths}\to x}\prod_{t}\langle p_t\mid U_t\mid p_{t-1}\rangle\Big|^2 \qquad (4)

where: $x\in\text{acc}$ — the basis states on which the final measurement accepts; $\text{paths}\to x$ — all length- $T$ histories ending at $x$ . Reading: the inner sum can have massive cancellation — the interference a classical simulator must reproduce. On the $\mathsf{NP}$ side the governing quantity is query complexity, and the BBBV theorem fixes it for unstructured search: the $N$ -bit OR needs $\Theta(\sqrt{N})$ quantum queries, matched above by Grover and below by an adversary argument.

Q(\mathrm{OR}_N)=\Theta(\sqrt{N}),\qquad \text{Grover uses }\tfrac{\pi}{4}\sqrt{N}\text{ queries} \qquad (5)

where: $Q(\cdot)$ — bounded-error quantum query complexity; $\mathrm{OR}_N$ — decide whether any of $N$ bits is set, the black-box form of an $\mathsf{NP}$ search; $\tfrac{\pi}{4}\sqrt{N}$ — the Grover iteration count, optimal up to the leading constant. Reading: quadratic, not exponential — this one bound is why $\mathsf{NP}\subseteq\mathsf{BQP}$ is disbelieved. Every known separation is relativized: there are oracles making each of $\mathsf{BQP}$ and $\mathsf{NP}$ fail to contain the other. Because the containment proofs relativize too, an unrelativized resolution must use non-relativizing techniques.

\exists A:\ \mathsf{BQP}^A\not\subseteq\mathsf{NP}^A \qquad\text{and}\qquad \exists B:\ \mathsf{NP}^B\not\subseteq\mathsf{BQP}^B \qquad (6)

where: $A,B$ — suitably chosen oracles (hidden strings or relations); $\not\subseteq$ — some language in the relativized left class lies outside the relativized right class. Reading: the two oracles point opposite ways, so no relativizing argument can decide the unrelativized question. Finally, both classes embed in a common quantum proof system, $\mathsf{QMA}$ , which is the natural arena for comparing quantum and classical verification.

\mathsf{NP}\subseteq\mathsf{QMA},\qquad \mathsf{BQP}\subseteq\mathsf{QMA} \qquad (7)

where: $\mathsf{QMA}$ — Quantum Merlin-Arthur, a quantum polynomial-time verifier given a quantum witness. Reading: $\mathsf{NP}$ embeds because a classical witness is a special quantum one; $\mathsf{BQP}$ embeds because the verifier can ignore the witness and just compute.

Derivation ABQP inside PSPACE via the Feynman path-sum

The goal is to prove the workhorse upper bound $\mathsf{BQP}\subseteq\mathsf{PSPACE}$ directly from the path-sum, by exhibiting a polynomial-space machine that computes a circuit's acceptance probability without ever storing the exponentially large state vector. The trick: although the sum over paths is exponentially long, a machine can walk the paths one at a time, reuse a fixed-size accumulator, and never hold more than polynomially many bits alive at once — trading the quantum machine's exponential space for exponential time while keeping space polynomial.

Step 1. Fix a universal gate set with algebraic entries, for instance Hadamard plus Toffoli, so that every one-gate amplitude $\langle p_t\mid U_t\mid p_{t-1}\rangle$ is a fixed dyadic number computable to $b$ bits in time $\mathrm{poly}(b)$ . Why: exact algebraic entries mean the machine can compute each factor on demand rather than storing a table, and finite precision suffices because the class has a constant gap to resolve.

Step 2. Write the acceptance amplitude for a target $x$ as the path-sum $\alpha_x=\sum_{p_1,\dots,p_{T-1}}\prod_{t=1}^{T}\langle p_t\mid U_t\mid p_{t-1}\rangle$ , where each $p_t$ ranges over $\{0,1\}^n$ . Why: this converts a linear-algebra object — a product of exponential matrices — into a scalar sum whose terms are cheap and independent, the form a space-bounded machine can stream.

Step 3. Enumerate the path tuples with an $O(nT)$ -bit counter. For each tuple, multiply the $T$ one-gate amplitudes into a single running accumulator and add the product to a running total for $\alpha_x$ , then move to the next tuple and overwrite the working registers. Why: only the counter, one product accumulator, and one total are ever alive, so the space stays $O(nT\cdot b)=\mathrm{poly}(n)$ even though the loop runs $2^{n(T-1)}$ times.

Step 4. Recompute each $\alpha_x$ on demand for every accepting outcome and accumulate $\Pr[\text{accept}]=\sum_{x\in\text{acc}}|\alpha_x|^2$ , then compare it to the threshold $1/2$ . Why: the bounded-error gap of at least $1/3$ dwarfs the accumulated rounding error at $b=\mathrm{poly}(n)$ precision, so a correct decision comes out; space used stays polynomial, which is the definition of $\mathsf{PSPACE}$ .

Go deeper · Derivation B · 1 minBQP inside PP via signed path counting

Derivation BBQP inside PP via signed path counting

The aim is to sharpen the space bound to the strongest containment known, $\mathsf{BQP}\subseteq\mathsf{PP}$ , by recasting the same path-sum as a difference between two counting problems. With a real-amplitude gate set every path contributes a fixed-magnitude term carrying only a sign, so the acceptance amplitude becomes the number of positive paths minus the number of negative paths — a gap whose sign a probabilistic polynomial-time machine, accepting by majority of its branches, can test directly. Because $\mathsf{PP}\subseteq\mathsf{PSPACE}$ , this result contains the previous one and is strictly more informative.

Step 1. Choose a real universal gate set (Hadamard and Toffoli), so every one-gate amplitude is $\pm 2^{-k/2}$ for a fixed $k$ , and each path's product is a signed dyadic rational of fixed magnitude $2^{-kT/2}$ . Why: stripping the amplitudes down to a common magnitude times a sign turns amplitude-summing into sign-counting, the natural currency of counting classes.

Step 2. Write $\alpha_x=2^{-kT/2}\sum_{\text{paths}\to x}s(\text{path})$ with $s\in\{+1,-1\}$ , where the sign is the parity of minus signs along the path and is computable in polynomial time from the path description. Why: the amplitude is now literally $N_+^x-N_-^x$ up to a fixed scale, exposing a $\mathsf{GapP}$ counting function — the difference of two $\#\mathsf{P}$ counts.

Step 3. Express acceptance as $\Pr[\text{accept}]\propto\sum_x(N_+^x-N_-^x)^2$ , handling the square by running a doubled path register $(p,p')$ so the squared count is itself a single counting object over polynomially many bits. Why: probabilities are amplitude magnitudes squared, and the doubled register keeps the whole thing inside one counting problem rather than a product of two.

Step 4. Have a $\mathsf{PP}$ machine encode this signed count so that a majority of its computation branches accept exactly when $\Pr[\text{accept}]>1/2$ ; the bounded-error gap guarantees the count lands strictly on one side. Why: $\mathsf{PP}$ is defined by majority acceptance, so a problem reducible to the sign of a $\mathsf{GapP}$ function is in $\mathsf{PP}$ by definition — this is the Adleman–DeMarrais–Huang theorem.

Go deeper · Derivation C · 1 minThe BBBV bound and mutual oracle separation

Derivation CThe BBBV bound and mutual oracle separation

The purpose here is to show why $\mathsf{NP}$ -complete problems resist quantum attack and why the $\mathsf{BQP}$ -versus- $\mathsf{NP}$ question is oracle-ambiguous. The core is a hybrid argument bounding how much a quantum state can move when a single oracle bit is flipped: because the total "query weight" any algorithm can place grows only linearly in the number of queries, distinguishing $N$ single-marked inputs forces $\Omega(\sqrt{N})$ queries. That same $\Theta(\sqrt{N})$ fact, planted in an oracle, gives a language in $\mathsf{NP}^B$ outside $\mathsf{BQP}^B$ , while a hidden-structure oracle gives the reverse.

Step 1. Run any $t$ -query algorithm and track the query magnitude $\||\psi_i^\tau\rangle\|^2$ it places on each index $i$ at each step; summing over steps gives $\sum_i\sum_{\tau<t}\||\psi_i^\tau\rangle\|^2\le t$ . Why: each query is a unit-norm operation, so the total attention an algorithm can pay across all oracle positions is bounded by the number of queries — the key BBBV inventory.

Step 2. Flip the single marked bit at a low-weight index; the resulting change in the final state satisfies $\||\psi^t_x\rangle-|\psi^t_0\rangle\|\le 2\sum_{\tau<t}\||\psi_i^\tau\rangle\|$ , so the state barely moves at indices the algorithm rarely queried. Why: if the algorithm did not "look hard" at position $i$ , it cannot tell whether the needle is there, which is what turns the weight budget into an indistinguishability statement.

Step 3. Average over the $N$ possible marked positions: since the total weight is only $t$ , most positions get weight $O(t/N)$ , and detecting all of them with constant probability forces $t=\Omega(\sqrt{N})$ . Why: this is the matching lower bound to Grover's $\tfrac{\pi}{4}\sqrt{N}$ upper bound, closing the search problem at $\Theta(\sqrt{N})$ and ruling out an exponential quantum speedup for unstructured search.

Step 4. Deploy the bound as an oracle: a language asking whether an oracle string contains a marked item sits in $\mathsf{NP}^B$ (guess the position) but needs $\Omega(\sqrt{N})$ quantum queries, so it escapes $\mathsf{BQP}^B$ ; conversely a recursive Fourier-sampling oracle $A$ yields a language in $\mathsf{BQP}^A\setminus\mathsf{NP}^A$ . Why: the two oracles point opposite ways, so both non-containments relativize and any unrelativized answer must avoid oracle-respecting arguments.

Limiting cases

The proven relationships, and the conjectured ones, arranged from the strongest facts to the deepest open questions.

Case	Result	Meaning
Proven lower chain	$\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}$	a quantum computer simulates deterministic and randomized computation; both inclusions are unconditional
Proven upper chain	$\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE}\subseteq\mathsf{EXP}$	from the path-sum; ADH 1997 gives $\mathsf{PP}$ , and $\mathsf{PP}\subseteq\mathsf{PSPACE}$ is classical
$\mathsf{NP}$ relationship	$\mathsf{BQP}\;?\;\mathsf{NP}$	no containment proven in either direction; both fail relative to suitable oracles
Unstructured search	$Q(\mathrm{OR}_N)=\Theta(\sqrt{N})$	quadratic, not exponential — no generic quantum speedup for the $\mathsf{NP}$ core
Structured search	factoring, discrete log $\in\mathsf{BQP}$	hidden periodicity is detectable by the quantum Fourier transform (Shor), unlike unstructured $\mathsf{NP}$
Common upper class	$\mathsf{NP},\mathsf{BQP}\subseteq\mathsf{QMA}$	quantum proofs generalize both classical witnesses and quantum computation

Common trapQuantum computers efficiently solve NP-complete problems

This is the single most common misconception about quantum computing, and it is almost certainly false. There is no proof that $\mathsf{NP}\subseteq\mathsf{BQP}$ , and every piece of structural evidence points the other way. For the unstructured search at the heart of $\mathsf{NP}$ -completeness, Grover's algorithm gives only a quadratic speedup, and the BBBV theorem proves that quadratic is optimal in the query model — a $\Theta(\sqrt{N})$ wall no quantum algorithm can climb. Shor's spectacular success on factoring is not a counterexample: factoring is in $\mathsf{NP}\cap\mathsf{coNP}$ , is not believed $\mathsf{NP}$ -complete, and is cracked only because it hides an algebraic period that the quantum Fourier transform can extract — structure that generic $\mathsf{NP}$ -complete problems are not believed to possess. The mirror-image error, asserting $\mathsf{BQP}\subseteq\mathsf{NP}$ , is no safer: there is an oracle relative to which it fails.

Worked examples

1 · Sizing Grover: why quadratic is not enough (fully worked)

A quantum computer searches an unstructured space of $N=2^{40}\approx1.1\times10^{12}$ items for one marked entry. How many oracle queries does Grover use, and what does the same speedup do to a SAT instance on $100$ variables?

Step 1. Grover's iteration count is $\tfrac{\pi}{4}\sqrt{N}$ . With $N=2^{40}$ , $\sqrt{N}=2^{20}=1{,}048{,}576$ , so the query count is $\tfrac{\pi}{4}\cdot 2^{20}=0.7854\times1{,}048{,}576\approx\mathbf{8.2\times10^{5}}$ queries, versus about $N/2=5.5\times10^{11}$ on average classically. The quantum saving is real and large — a factor of roughly $\sqrt{N}\approx10^{6}$ .

Step 2. Now take an $\mathsf{NP}$ -complete problem: Boolean satisfiability on $n=100$ variables, whose brute-force space is $2^{100}\approx1.3\times10^{30}$ assignments. Grover treats "is there a satisfying assignment" as unstructured search, so it uses $\tfrac{\pi}{4}\sqrt{2^{100}}=\tfrac{\pi}{4}\cdot 2^{50}\approx\mathbf{8.8\times10^{14}}$ queries.

Step 3. Read the two numbers together. The quadratic speedup turns $2^{100}$ into about $2^{50}$ — from utterly impossible to merely astronomically impossible. At a billion oracle queries per second, $8.8\times10^{14}$ queries is still over $10$ days per instance, and any real $\mathsf{NP}$ -hardness margin (larger $n$ ) blows past it immediately. A √N speedup halves the exponent; it never removes it, which is exactly why $\mathsf{NP}\subseteq\mathsf{BQP}$ is disbelieved.

2 · Amplifying a weak BQP gap (fully worked)

A quantum circuit decides a language but with only an inverse-polynomial gap: it accepts yes-instances with probability $\tfrac12+\delta$ and no-instances with $\tfrac12-\delta$ , where $\delta=1/n$ and $n=100$ . How many independent repetitions, with a majority vote, drive the error below $2^{-n}$ ?

Step 1. Running the circuit $k$ times and taking the majority fails only when the fraction of correct runs falls below $1/2$ ; a Chernoff/Hoeffding bound gives $\Pr[\text{majority wrong}]\le e^{-2k\delta^2}$ . Set this below the target $2^{-n}=2^{-100}$ .

Step 2. Solve $e^{-2k\delta^2}\le 2^{-n}$ , i.e. $2k\delta^2\ge n\ln 2$ , giving $k\ge\dfrac{n\ln 2}{2\delta^2}$ . With $\delta=1/n$ this is $k\ge\dfrac{n\ln2}{2}\,n^2=\tfrac{\ln 2}{2}\,n^3\approx0.347\,n^3$ .

Step 3. Plug in $n=100$ , $\delta=0.01$ : $k\ge\dfrac{100\times0.6931}{2\times(0.01)^2}=\dfrac{69.31}{2\times10^{-4}}\approx\mathbf{3.5\times10^{5}}$ repetitions. That is still polynomial in $n$ — order $n^3$ — so a machine with any $1/\mathrm{poly}$ gap defines the same class as one with the $2/3$ – $1/3$ gap, which is why the thresholds in the definition of $\mathsf{BQP}$ are arbitrary.

3 · The path-sum, counted

A quantum circuit uses $n=50$ qubits and $T=100$ gates. How many computational paths does its amplitude sum over, and how much memory does the $\mathsf{PSPACE}$ simulation need?

Step 1. The number of paths is at most $2^{n(T-1)}=2^{50\times99}=2^{4950}$ — about $1490$ decimal digits, vastly more than the atoms in the observable universe. This is the sum the quantum machine performs "for free" by interference.

Step 2. The simulator never stores that sum. It holds a path counter of $O(nT)=5000$ bits plus a few fixed-precision accumulators — working memory on the order of $\mathbf{10^{4}}$ bits. The exponential lives in the running time (it walks all $2^{4950}$ paths) while the space stays polynomial — the trade-off that places $\mathsf{BQP}$ in $\mathsf{PSPACE}$ rather than $\mathsf{P}$ .

Physics of the portrait

The theory of quantum computational power is young, and one figure sits at the origin of almost every result above: the person who, with a student, first defined $\mathsf{BQP}$ , bounded it inside $\mathsf{PSPACE}$ , and helped prove the search lower bound that keeps $\mathsf{NP}$ out.

Origins · 1 minUmesh Vazirani and how this was discovered

Umesh Vazirani

b. 1961 · founder of quantum computational complexity

Umesh Vazirani, a theoretical computer scientist at UC Berkeley and a student of Manuel Blum, built much of the scaffolding on which quantum complexity theory stands. In a 1993 paper with his student Ethan Bernstein — expanded in the 1997 SIAM Journal on Computing article the field still cites — he defined the quantum Turing machine rigorously, constructed a universal one, introduced the class $\mathsf{BQP}$ , and proved the foundational upper bound $\mathsf{BQP}\subseteq\mathsf{P}^{\#\mathsf{P}}\subseteq\mathsf{PSPACE}$ by the path-integral simulation used in this article. The same paper introduced recursive Fourier sampling, the ancestor of the oracle that separates $\mathsf{BQP}$ from $\mathsf{NP}$ . Vazirani then joined Charles Bennett, Ethan Bernstein and Gilles Brassard to prove the "BBBV" theorem — that unstructured search needs $\Omega(\sqrt{N})$ quantum queries — the result that makes Grover's algorithm optimal and forecloses a generic quantum attack on $\mathsf{NP}$ -complete problems. The Bernstein–Vazirani problem bears his name, and his framing of what quantum computers can and cannot do still sets the terms of the quantum-advantage debate.

History

1985

— Deutsch defines the universal quantum Turing machine and the notion of quantum-computable functions

1993

— Bernstein and Vazirani define BQP and prove BQP inside PSPACE by the path-sum simulation

1994

— Shor places factoring and discrete log in BQP, dramatizing the BQP-versus-NP gap

1996

— Grover gives the √N-query search algorithm, matched below by the BBBV lower bound

1997

— Adleman, DeMarrais and Huang prove the sharper containment BQP inside PP

2018

— Raz and Tal exhibit an oracle separating BQP from the polynomial hierarchy

Going further

Texts. Nielsen and Chuang, Quantum Computation and Quantum Information, Ch. 4 and 6 · Preskill, Lecture Notes on Quantum Computation, Ch. 6 · Watrous, Quantum Computational Complexity (survey) and The Theory of Quantum Information · Kitaev, Shen and Vyalyi, Classical and Quantum Computation · Wilde, Quantum Information Theory, complexity chapters · Arora and Barak, Computational Complexity, for the classical $\mathsf{PP}$ / $\mathsf{PSPACE}$ background.

Provenance. The chain $\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE}$ is from Bernstein and Vazirani (SIAM J. Comput. 26, 1997, 1411, for $\mathsf{BQP}\subseteq\mathsf{PSPACE}$ ) and Adleman, DeMarrais and Huang (SIAM J. Comput. 26, 1997, 1524, for $\mathsf{BQP}\subseteq\mathsf{PP}$ ). The optimality $Q(\mathrm{OR}_N)=\Theta(\sqrt{N})$ and the mutual oracle non-containments are from Bennett, Bernstein, Brassard and Vazirani (SIAM J. Comput. 26, 1997, 1510); Grover's $\tfrac{\pi}{4}\sqrt{N}$ upper bound is from Grover (STOC 1996), shown exactly optimal by Zalka (1999). The oracle separating $\mathsf{BQP}$ from the polynomial hierarchy is Raz and Tal (STOC 2019). A verifier should confirm: (1) the path-sum identity and its poly-space enumeration; (2) the Chernoff amplification $e^{-2k\delta^2}$ giving threshold independence, and the $k\approx0.347\,n^3$ figure; (3) the Grover counts $\tfrac{\pi}{4}\cdot2^{20}\approx8.2\times10^5$ and $\tfrac{\pi}{4}\cdot2^{50}\approx8.8\times10^{14}$ ; (4) that factoring is in $\mathsf{NP}\cap\mathsf{coNP}$ and not known $\mathsf{NP}$ -complete.

Prerequisites. The Complexity Class BQP · BQP is Contained in PP and PSPACE · Quantum Query Complexity. Leads to. Quantum Merlin-Arthur (QMA) · QIP = PSPACE · The Polynomial Method for Quantum Lower Bounds.

Ask the tutor: ask me to walk through the path-sum simulation line by line, or to show exactly which oracle makes $\mathsf{NP}$ escape $\mathsf{BQP}$ .

Is NP ⊆ BQP known, and what is the best evidence either way?

No — no containment is known between $\mathsf{BQP}$ and $\mathsf{NP}$ in either direction, and the balance of evidence says neither contains the other. On one side, quantum computers solve structured problems like factoring that are not believed $\mathsf{NP}$ -complete, so they give no route to $\mathsf{NP}$ -hardness. On the other, the BBBV theorem shows the unstructured search at the core of $\mathsf{NP}$ -completeness costs $\Theta(\sqrt{N})$ quantum queries — only a quadratic speedup, provably optimal. There are oracles making $\mathsf{BQP}$ fail to contain $\mathsf{NP}$ and others making $\mathsf{NP}$ fail to contain $\mathsf{BQP}$ , so the question is wide open and any resolution must use non-relativizing techniques.

Why does the path-sum give BQP ⊆ PSPACE but not BQP ⊆ P?

Because the sum has exponentially many terms. Polynomial space is enough because the machine enumerates paths one at a time, reusing a fixed-size accumulator, so at any instant only polynomially many bits are alive — but walking every path takes exponential time. There is no known way to collapse the same sum into polynomial time, and doing so would require somehow shortcutting the interference among exponentially many amplitudes, which is precisely the resource that gives quantum computers their power. So the space bound is cheap and the time bound is the whole open question.

If Grover only gives a quadratic speedup, why is it a big deal?

It is useful but not transformative: halving the effective key length of a symmetric cipher means AES-128 offers only about $64$ bits of security against a quantum adversary, which is why standards recommend AES-256. But Grover turns a $2^{n}$ search into only $2^{n/2}$ , still exponential. Its real weight for complexity theory is the matching BBBV lower bound: because Grover is provably optimal, the quadratic ceiling is a theorem about the limits of quantum search, and the strongest single piece of evidence that quantum computers do not efficiently solve $\mathsf{NP}$ -complete problems.

Does Shor's algorithm mean factoring is NP-complete, or that BQP is huge?

Neither. Factoring lies in $\mathsf{NP}\cap\mathsf{coNP}$ — you can certify both a factorization and its absence — and problems in that intersection are not believed to be $\mathsf{NP}$ -complete, because if one were, $\mathsf{NP}$ would equal $\mathsf{coNP}$ , which almost nobody expects. Shor's algorithm works by reducing factoring to finding the period of a modular-exponentiation function and detecting that period with the quantum Fourier transform, a maneuver available only because the problem has hidden algebraic structure. It shows that $\mathsf{BQP}$ very likely strictly contains $\mathsf{BPP}$ , not that it swallows $\mathsf{NP}$ ; the structured-versus-unstructured distinction is the whole point.

What does it mean that every separation here is relativized?

An argument "relativizes" if it stays valid when every machine is given the same oracle — a free subroutine — to consult. Most of the basic simulation and diagonalization arguments in complexity theory relativize, and so do the containment proofs in this article. The trouble is that there are oracles $A$ and $B$ pointing in opposite directions: $\mathsf{BQP}^A\not\subseteq\mathsf{NP}^A$ and $\mathsf{NP}^B\not\subseteq\mathsf{BQP}^B$ . Because a relativizing proof would have to hold for every oracle, no such proof can settle the unrelativized question either way. Any real answer must therefore use a non-relativizing technique, of which complexity theory has only a handful.

Where do QMA and the Local Hamiltonian problem fit into this picture?

$\mathsf{QMA}$ — Quantum Merlin-Arthur — is the quantum analogue of $\mathsf{NP}$ : a polynomial-time quantum verifier receives a quantum state as a witness and must accept valid claims and reject invalid ones with a gap. Both $\mathsf{NP}$ and $\mathsf{BQP}$ sit inside it, so it is the smallest natural class containing the two we compare, the right arena for asking how quantum and classical proofs relate. Its complete problem — deciding the ground-state energy of a Local Hamiltonian — is the quantum echo of Boolean satisfiability, and understanding it is central to whether quantum computations can be efficiently verified.