BQP is Contained in PP and PSPACE

The class $\mathsf{BQP}$ — bounded-error quantum polynomial time — is the formal home of "what a quantum computer can do efficiently": decision problems solved by uniform families of polynomial-size quantum circuits that answer correctly with probability bounded away from $1/2$ . The structural question that organizes the field is where this quantum class sits inside the classical universe of complexity. The oldest and most durable answer is a pair of containments, $\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE}$ , established in essence by Bernstein and Vazirani in 1993 and sharpened by Adleman, DeMarrais and Huang in 1997: anything a quantum computer computes quickly, a classical machine can also compute — using only polynomial memory, though generally at the cost of exponential time. The engine of both proofs is a single idea borrowed from physics: the Feynman path sum. The amplitude for a circuit $U=U_T\cdots U_1$ to carry one basis state to another is a sum, over every intermediate sequence of basis strings, of the product of the gates' matrix elements. Each gate touches $O(1)$ qubits, so each factor is a small exact number and a whole path is one string of $T$ snapshots; the paths are exponentially many, but each costs only polynomial time and space. The acceptance probability therefore becomes a signed sum of exponentially many efficiently-computable terms — precisely the shape the counting classes $\mathsf{PP}$ and $\#\mathsf{P}$ were built to handle. This reframing turns a quantum question into a bookkeeping one, and bookkeeping is what a classical machine with a counter and a small work-tape does best.

Key takeaways

Every $\mathsf{BQP}$ language is decided by a polynomial-size quantum circuit whose acceptance probability is a Feynman path sum — an exponential sum over computational paths of products of gate amplitudes.
Over the universal Hadamard+Toffoli gate set every amplitude is a real dyadic rational $\pm 2^{-h/2}$ , so $2^{h}p_{\mathrm{acc}}$ is an exact integer $N_{+}-N_{-}$ ; deciding its sign is exactly the $\mathsf{PP}$ question, giving $\mathsf{BQP}\subseteq\mathsf{PP}$ .
The exponentially many paths can be enumerated one at a time with a polynomial-size counter, so $\mathsf{PP}\subseteq\mathsf{PSPACE}$ , hence $\mathsf{BQP}\subseteq\mathsf{PSPACE}$ .
The simulation needs only polynomial space but generally exponential time — it bounds the memory of quantum computing, not its speed, so conjectured speedups like Shor's are untouched, and no $\mathsf{PSPACE}$ -hard (or $\mathsf{NP}$ -hard) problem is solved efficiently unless the hierarchy collapses.
The result anchors $\mathsf{BQP}$ in the chain $\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE}\subseteq\mathsf{EXP}$ .
Key idea: Write the quantum acceptance probability as a Feynman path sum — an exponential sum of efficiently computable signed amplitudes. Counting such signed contributions is exactly what $\mathsf{PP}$ does, and enumerating them one path at a time costs only polynomial space, giving $\mathsf{BQP}\subseteq\mathsf{PP}\subseteq\mathsf{PSPACE}$ .

Where this lives today

The containment is the working ceiling against which claims of quantum advantage are measured. When Google announced in 2019 that its 53-qubit Sycamore processor sampled random circuits in 200 seconds — a task it projected would take a supercomputer millennia — the counterattack came from the $\mathsf{PSPACE}$ side of this result: classical teams built Schrödinger–Feynman simulators looping over Feynman paths (trading memory for time exactly as $\mathsf{PP}\subseteq\mathsf{PSPACE}$ does), and later tensor-network methods that reproduced the sampling in days, then hours. The dispute over "how supreme" a demonstration is is the dispute over how far up the exponential-time-but-polynomial-space curve a classical machine can be pushed. On the theory side, $\mathsf{BQP}\subseteq\mathsf{PP}$ is the entry point to the modern map: it extends to $\mathsf{QMA}\subseteq\mathsf{PP}$ , underpins the celebrated $\mathsf{QIP}=\mathsf{PSPACE}$ , and frames open questions like whether $\mathsf{BQP}\subseteq\mathsf{PH}$ — which the 2019 Raz–Tal oracle separation suggests may fail — while the $\mathsf{PP}$ containment holds firm.

The physical picture

Picture a quantum computation as light threading a maze of beam splitters. Every route the light could take is a computational path, and the brightness at the detector — the acceptance probability — is the squared magnitude of the sum of complex amplitudes over all routes. A classical machine cannot ride all routes at once, but it can add them one at a time, and that patient summation is the whole content of both containments. The first figure fixes where $\mathsf{BQP}$ lives: pinned between randomised $\mathsf{BPP}$ below and the counting class $\mathsf{PP}$ above, with $\mathsf{PSPACE}$ and $\mathsf{EXP}$ enclosing all.

Figure

The complexity ladder P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE ⊆ EXP — each class a subset of the next, with BQP (quantum, defined by the 2/3 versus 1/3 acceptance gap) pinned between classical randomised BPP and the counting class PP

The hardness a classical simulator faces is not the number of paths — a $\mathsf{PSPACE}$ machine cheerfully loops over $2^{O(T)}$ of them — but the delicate cancellation among them. Interference can collapse a sum of exponentially many large terms to almost nothing, and it is this sign structure that forces a counting class like $\mathsf{PP}$ rather than an existential class like $\mathsf{NP}$ : asking "does an accepting path exist?" is the wrong question, because a single path means nothing — only the signed total does. The second figure makes it concrete on the smallest circuit: two Hadamards in a row, where two equal-magnitude paths meet with opposite signs and annihilate.

Figure

Two Feynman paths reach ∣1⟩ from ∣0⟩ through a Hadamard–Hadamard sandwich: the upper path carries amplitude +1/√2·1/√2 = +1/2 and the lower carries −1/√2·1/√2 = −1/2, so they cancel exactly and ⟨1∣HH∣0⟩ = 0 — tracking the sign, not just counting paths, is why PP and not NP is the right class

Universality lets us assume such well-behaved numbers. Over the Hadamard+Toffoli gate set — universal for $\mathsf{BQP}$ — every gate entry lies in $\{0,\pm 1,\pm 1/\sqrt2\}$ , so a path with $h$ Hadamards contributes $\pm 2^{-h/2}$ times an integer and the squared amplitude is dyadic. The decision "is $p_{\mathrm{acc}}>1/2$ ?" then sharpens into "is a signed integer count positive?" — the canonical $\mathsf{PP}$ question.

The core equations

A $\mathsf{BQP}$ computation is a fixed sequence of local unitaries applied to an input register padded with clean ancillas. Writing it out fixes the objects the argument manipulates — the gates, input, workspace, and circuit size.

|\psi_{\mathrm{out}}\rangle = U_T\,U_{T-1}\cdots U_1\,|x\rangle|0^{m}\rangle \qquad (1)

where: $U_t$ — the $t$ -th gate, acting nontrivially on $O(1)$ qubits, $1\le t\le T$ ; $|x\rangle$ — the $n$ -qubit input basis state; $|0^{m}\rangle$ — $m=\mathrm{poly}(n)$ ancillas initialized to zero; $T$ — the circuit size, $\mathrm{poly}(n)$ . Reading it: the machine is a product of poly-many local unitaries, so all its complexity lives in how those pieces interfere. Inserting a complete set of basis states between every pair of adjacent gates turns the matrix product into a sum over intermediate strings — the Feynman path sum, the single identity on which everything downstream rests.

\langle y | U_T\cdots U_1 | x\rangle = \sum_{z_1,\dots,z_{T-1}} \langle y|U_T|z_{T-1}\rangle\,\langle z_{T-1}|U_{T-1}|z_{T-2}\rangle \cdots \langle z_1|U_1|x\rangle \qquad (2)

where: $z_t$ — the intermediate basis string after gate $t$ , summed over all $2^{n+m}$ values; $\langle z_t|U_t|z_{t-1}\rangle$ — a single-gate amplitude, nonzero only when $z_t,z_{t-1}$ agree off the gate's support; $y$ — the measured output string. Reading it: one amplitude is an exponential sum whose every summand is a product of $T$ tiny, locally-computable factors. The machine accepts when the measured output lands in the accepting set, so the acceptance probability is the total weight on those outputs — a sum of squared amplitudes, each itself a path sum against its conjugate.

p_{\mathrm{acc}}(x) = \sum_{y\in A}\big|\langle y|U|x\rangle|0^m\rangle\big|^2 \qquad (3)

where: $A$ — the accepting output strings (e.g. first qubit $1$ ); $U=U_T\cdots U_1$ — the full unitary; $p_{\mathrm{acc}}(x)$ — the acceptance probability on input $x$ . Reading it: squaring pairs each path $\vec z$ with a second $\vec w$ , so $p_{\mathrm{acc}}$ is a double sum over path-pairs — still exponential, still term-by-term efficient. Membership in a $\mathsf{BQP}$ language is defined by a bounded gap around $1/2$ , not exact probabilities; any constant gap works, since majority-vote amplification drives it to $1-2^{-\mathrm{poly}(n)}$ .

x\in L \Rightarrow p_{\mathrm{acc}}(x)\ge \tfrac23,\qquad x\notin L \Rightarrow p_{\mathrm{acc}}(x)\le \tfrac13 \qquad (4)

where: $L$ — the $\mathsf{BQP}$ language; $\tfrac23$ and $\tfrac13$ — the completeness and soundness thresholds. Reading it: the gap $p_{\mathrm{acc}}-\tfrac12$ is bounded away from zero on both sides, so its sign is a robust bit — the one a $\mathsf{PP}$ machine will extract. Choosing the universal Hadamard+Toffoli gate set makes every amplitude real and dyadic, so squaring and clearing the fixed power of two turns the acceptance probability into a signed integer count — the exact object $\mathsf{PP}$ compares against a threshold.

2^{h}\,p_{\mathrm{acc}}(x)\;=\;\sum_{y\in A}\ \sum_{\vec z,\,\vec w}\ \varepsilon(\vec z)\,\varepsilon(\vec w)\;=\;N_{+}(x)-N_{-}(x)\in\mathbb{Z} \qquad (5)

where: $h$ — the fixed number of Hadamard gates; $\varepsilon(\cdot)\in\{0,\pm 1\}$ — the sign of a path's amplitude product; $\vec z,\vec w$ — the two paths produced by squaring; $N_{\pm}(x)$ — the path-pairs contributing $+1$ resp. $-1$ . Reading it: each path is $\pm 2^{-h/2}$ , the two copies give $2^{-h}$ , and the prefactor $2^{h}$ cancels it, leaving a plain integer. Assembling the two containments places $\mathsf{BQP}$ inside the classical hierarchy, above the randomised classes and below the space-bounded ones.

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

where: $\mathsf{BPP}$ — bounded-error randomised polynomial time; $\mathsf{PP}$ — probabilistic polynomial time (accept iff $p_{\mathrm{acc}}>1/2$ , unbounded gap); $\mathsf{PSPACE}$ — polynomial work-tape, unbounded time; $\mathsf{EXP}$ — deterministic exponential time. Reading it: $\mathsf{BQP}$ is sandwiched — at least as strong as classical randomness, no stronger than polynomial space.

Derivation AFrom the circuit to the Feynman path sum

The goal is to show that a single quantum amplitude — an inner product against a product of poly-many unitaries — is literally an exponential sum whose every term is a product of $T$ locally-computable numbers, so the exponential cost lives entirely in the number of terms, never in any one term. This identity is what lets a classical machine touch a quantum amplitude at all, and is the common root of both arguments below.

Step 1. Between every adjacent pair of gates $U_{t+1}$ and $U_t$ insert the resolution of identity $\mathbb{1}=\sum_{z_t}|z_t\rangle\langle z_t|$ ; there are $T-1$ such insertions in $U_T\cdots U_1$ . Why: the identity is exact — nothing is approximated, the product is only rewritten in a basis a classical machine can name string by string.

Step 2. This turns the operator product into $\langle y|U_T\cdots U_1|x\rangle=\sum_{z_1,\dots,z_{T-1}}\prod_{t=1}^{T}\langle z_t|U_t|z_{t-1}\rangle$ with boundary conditions $z_0=x0^m$ , $z_T=y$ . Why: distributing sums over the product exposes the sum-over-paths structure — each choice of $z_1,\dots,z_{T-1}$ is one "history" of the computation.

Step 3. Each factor $\langle z_t|U_t|z_{t-1}\rangle$ depends only on the $O(1)$ qubits in $U_t$ 's support; off-support the two strings must match or the factor vanishes, so a nonzero factor is one lookup into a constant-size matrix. Why: locality keeps each factor cheap — the gate is a small fixed matrix, not an exponential object.

Step 4. A single path therefore contributes a product of $T=\mathrm{poly}(n)$ such factors in $\mathrm{poly}(n)$ time and space; only the number of paths, $\le (2^{n+m})^{T-1}$ , is exponential. Why: cheap terms, exponentially many of them — exactly the profile a counting class or a space-bounded loop can exploit.

Go deeper · Derivation B · 1 minBQP inside PP by signed integer counting

Derivation BBQP inside PP by signed integer counting

The goal is to convert the bounded-error acceptance probability into an integer difference of two counts $N_{+}-N_{-}$ , then exhibit a probabilistic polynomial-time machine whose own acceptance probability exceeds $1/2$ precisely when that difference is positive — the definition of $\mathsf{PP}$ . The Hadamard+Toffoli gate set makes the arithmetic come out in integers, and the constant $\mathsf{BQP}$ gap makes the sign unambiguous.

Step 1. By the path-sum derivation, $\langle y|U|x0^m\rangle=\sum_{\vec z}\prod_t\langle z_t|U_t|z_{t-1}\rangle$ , and with gate entries in $\{0,\pm1,\pm1/\sqrt2\}$ each path value is $\pm 2^{-h/2}$ , $h$ the fixed Hadamard count shared by all paths. Why: the only irrational a gate introduces is the Hadamard's $1/\sqrt2$ , and every path meets the same $h$ of them — a single global constant, not a per-path nuisance.

Step 2. Square and scale: $2^{h}p_{\mathrm{acc}}=\sum_{y\in A}\sum_{\vec z,\vec w}\varepsilon(\vec z)\varepsilon(\vec w)$ , with $\varepsilon(\cdot)\in\{0,\pm1\}$ the sign of a path product. The two $2^{-h/2}$ factors multiply to $2^{-h}$ , killed by the prefactor $2^{h}$ , so the right side is a sum of $0,\pm1$ terms — an integer. Why: squaring removes the root of two, $(2^{-h/2})^2=2^{-h}$ ; this is why one works with the probability, not the amplitude.

Step 3. Define the gap $G(x):=2^{h}p_{\mathrm{acc}}(x)-2^{h-1}=N_{+}(x)-N_{-}(x)$ , with $N_{+}$ the path-pairs of product $+1$ and $N_{-}$ those of $-1$ . The promise gives $G(x)\ge 2^{h}/6$ for $x\in L$ and $G(x)\le -2^{h}/6$ for $x\notin L$ . Why: the $2/3$ – $1/3$ promise becomes a gap of at least $2^{h}(2/3-1/2)=2^{h}/6$ , so the sign is never a coin toss.

Step 4. A $\mathsf{PP}$ machine guesses a uniform tuple $(\vec z,\vec w,y)$ in polynomial time, computes $c\in\{0,\pm1\}$ from $O(T)$ local lookups, and accepts or rejects with auxiliary coins engineered so its acceptance probability exceeds $1/2$ exactly when $\mathbb{E}[c]>0$ , i.e. $N_{+}>N_{-}$ . Why: this is the standard trick letting an unbounded-error machine read the sign of a signed sum — it needs only the sign, not the magnitude.

Step 5. Hence $x\in L\iff N_{+}(x)>N_{-}(x)$ is decided by a $\mathsf{PP}$ machine, so $L\in\mathsf{PP}$ ; as $L$ was arbitrary, $\mathsf{BQP}\subseteq\mathsf{PP}$ . Why: nothing used $L$ beyond the promise and gate set, both generic to $\mathsf{BQP}$ .

Go deeper · Derivation C · 1 minPP inside PSPACE by one path at a time

Derivation CPP inside PSPACE by one path at a time

The goal is to show that a count over exponentially many branches costs only polynomial space, because the branches can be visited sequentially and each discarded before the next begins — the running total, not the list of branches, is all that must be held. Composed with the previous derivation this delivers $\mathsf{BQP}\subseteq\mathsf{PSPACE}$ , and explains why a quantum simulation can be memory-cheap even when time-expensive.

Step 1. Let $M$ be a $\mathsf{PP}$ machine tossing $r\le p(n)$ random bits per branch; the accept count is $\sum_{b\in\{0,1\}^{r}}[\,M(x,b)\text{ accepts}\,]$ . Loop $b=0,\dots,2^{r}-1$ , simulating each deterministic branch $M(x,b)$ in turn. Why: fixing the coin string $b$ makes the machine deterministic, so each branch is an ordinary poly-time, poly-space computation run in isolation.

Step 2. Keep a single counter $C$ , update $C\mathrel{+}=[\,M(x,b)\text{ accepts}\,]$ after each branch, then erase that branch's work-tape before starting $b+1$ . Why: only the total matters for the threshold, so scratch space is overwritten — reuse of space, not storage, is the whole point.

Step 3. The counter has $\le r+1$ bits, the index $b$ has $r$ bits, and one branch uses $p(n)$ space, so total space is $O(p(n))$ and the machine accepts iff $C>2^{r-1}$ . Why: three poly-size objects — index, counter, one live branch — are all that ever coexist, so the exponential branch count never touches the space bill.

Step 4. Composing $\mathsf{BQP}\subseteq\mathsf{PP}$ with $\mathsf{PP}\subseteq\mathsf{PSPACE}$ gives $\mathsf{BQP}\subseteq\mathsf{PSPACE}$ ; equivalently one loops over Feynman paths directly, accumulating $2^{h}p_{\mathrm{acc}}$ in a poly-size register, never forming the state vector. Why: the exponential resource is traded from space into time — the loop is exponentially long but its footprint polynomial.

Limiting cases

The containment chain, its lower frame, and its known sharpenings:

Case	Result	Meaning
Lower frame	$\mathsf{P}\subseteq\mathsf{BPP}\subseteq\mathsf{BQP}$	Quantum at least matches classical randomised polynomial time; inclusions believed proper but unproven.
Counting frame	$\mathsf{BQP}\subseteq\mathsf{PP}$	The central result: bounded-error quantum power is captured by unbounded-error counting.
Space frame	$\mathsf{PP}\subseteq\mathsf{PSPACE}\subseteq\mathsf{EXP}$	Enumerate paths one at a time in polynomial space; $\mathsf{PSPACE}\subseteq\mathsf{EXP}$ by configuration-graph reachability.
Sharpening	$\mathsf{BQP}\subseteq\mathsf{AWPP}\subseteq\mathsf{PP}$	Fortnow–Rogers: $\mathsf{BQP}$ sits in the low subclass $\mathsf{AWPP}$ , so the plain $\mathsf{PP}$ bound is not tight.
Oracle vs $\mathsf{PH}$	$\mathsf{BQP}\not\subseteq\mathsf{PH}$ relative to an oracle	Raz–Tal (2019): quantumness can escape the polynomial hierarchy yet stays inside $\mathsf{PP}$ .

Common trapQuantum computers are just exponential-time classical machines in disguise

This misreads the containment. The $\mathsf{PSPACE}$ simulation bounds the memory a classical machine needs, not its time: looping over $2^{O(T)}$ Feynman paths generally takes exponential time, so $\mathsf{BQP}\subseteq\mathsf{PSPACE}$ says nothing against a genuine speedup. Nor is the bound believed tight — $\mathsf{BQP}$ is conjectured far smaller than $\mathsf{PSPACE}$ , thought incomparable to $\mathsf{NP}$ , and relative to an oracle even escapes the polynomial hierarchy. A subtler trap: the path sum is over signed amplitudes, and their cancellation is what makes the count nontrivial — drop the signs and you count all paths, a meaningless overcount that erases the interference that is quantum computing's engine.

Worked examples

1 · A path sum you can add by hand (confidence builder)

Take the smallest interfering circuit: one qubit initialized to $|0\rangle$ , hit by two Hadamards, then measured. Use the path sum to compute the amplitude to land in $|1\rangle$ , and read off what the sign structure does.

Step 1. There is one intermediate time, so $z_1\in\{0,1\}$ — exactly two paths from $|0\rangle$ to $|1\rangle$ , and $\langle 1|HH|0\rangle=\sum_{z_1}\langle 1|H|z_1\rangle\langle z_1|H|0\rangle$ .

Step 2. Insert the Hadamard entries $\langle 0|H|0\rangle=\langle 1|H|0\rangle=\langle 0|H|1\rangle=+1/\sqrt2$ and $\langle 1|H|1\rangle=-1/\sqrt2$ . The upper path ( $z_1=0$ ) gives $\langle 1|H|0\rangle\langle 0|H|0\rangle=(+1/\sqrt2)(+1/\sqrt2)=\mathbf{+1/2}$ . The lower path ( $z_1=1$ ) gives $\langle 1|H|1\rangle\langle 1|H|0\rangle=(-1/\sqrt2)(+1/\sqrt2)=\mathbf{-1/2}$ .

Step 3. Sum the paths: $\langle 1|HH|0\rangle=(+1/2)+(-1/2)=\mathbf{0}$ , agreeing with $HH=\mathbb{1}$ , $\langle 1|\mathbb{1}|0\rangle=0$ . Two equal-magnitude paths exist, yet the amplitude vanishes — an $\mathsf{NP}$ -style "does a path exist?" test says yes and is useless; only the signed total $N_{+}-N_{-}=1-1=0$ carries the physics. The amplitude is 0 by exact cancellation of a $+1/2$ and a $-1/2$ path; sign-tracking is mandatory, which is why the right class is PP.

2 · Resource accounting for a real-scale circuit (fully worked)

A $\mathsf{BQP}$ circuit runs on $N=n+m=60$ qubits with $T=1000$ gates, $h=4000$ of them Hadamards. Estimate (a) the number of Feynman paths, (b) the size of the integer $2^{h}p_{\mathrm{acc}}$ , and (c) the space and time a $\mathsf{PSPACE}$ simulation uses, and contrast the two costs.

Step 1. Count the paths. Each of the $T-1=999$ intermediate times carries a full string in $\{0,1\}^{60}$ , so there are $(2^{60})^{999}=2^{59940}$ paths, and squaring pairs them into $\sim 2^{119880}$ path-pairs. The sum has about $2^{6\times10^{4}}$ terms.

Step 2. Size the integer. By equation (5), $2^{h}p_{\mathrm{acc}}$ is a nonnegative integer no larger than $2^{h}=2^{4000}$ , fitting in $h=\mathbf{4000}$ bits. It is compared against $2^{h-1}=2^{3999}$ , and the promise forces the two sides apart by at least $2^{h}/6\approx 2^{3997.4}$ — a gap of thousands of bits, never a photo finish.

Step 3. Bill the space. The $\mathsf{PSPACE}$ loop holds one path index ( $\approx N(T-1)=6\times10^{4}$ bits), one counter ( $\approx 6\times10^{4}$ bits), and one live path: on the order of $10^{5}$ bits $=\mathbf{poly}(n)$ , a few kilobytes.

Step 4. Bill the time, and contrast. The loop must still visit all $\sim 2^{6\times10^{4}}$ path-pairs one by one, so the time is exponential and infeasible. Space is polynomial ( $\sim10^{5}$ bits) while time is exponential ( $\sim2^{6\times10^{4}}$ steps): the containment trades state-vector memory for prohibitive time — exactly why $\mathsf{BQP}\subseteq\mathsf{PSPACE}$ forbids nothing about quantum speed.

Physics of the portrait

The containment sits at the crossroads of physics and computer science: a physicist's sum-over-histories, pressed into service to bound a class of machines that did not exist when the sum was invented. The sharp form $\mathsf{BQP}\subseteq\mathsf{PP}$ belongs to a cryptographer who had already reshaped two other fields.

Origins · 1 minLeonard Adleman and how this was discovered

Leonard Adleman

born 1945, computer scientist, University of Southern California · proved BQP ⊆ PP and founded the theory of quantum computability

Leonard Adleman is best known as the "A" in RSA — with Ron Rivest and Adi Shamir he built, in 1977, the public-key cryptosystem that still secures much of the internet, work honoured with the 2002 Turing Award. He has a habit of founding fields: in 1994 he solved a small Hamiltonian-path instance in a test tube using strands of DNA, launching molecular computing overnight. His entry into quantum complexity came in 1997, with Jonathan DeMarrais and Ming-Deh Huang, in "Quantum Computability" (SIAM J. Comput. 26(5):1524). Where Bernstein and Vazirani had placed $\mathsf{BQP}$ inside $\mathsf{PSPACE}$ and built the field's foundations, Adleman, DeMarrais and Huang pinned down the sharper ceiling $\mathsf{BQP}\subseteq\mathsf{PP}$ and analysed how the amplitudes' number-theoretic character affects what a quantum computer can compute. Their proof is the signed-integer-counting argument of this article — cast the acceptance probability as a difference of two exact counts and hand the sign to a probabilistic machine, a characteristically Adleman move showing an exotic model is, underneath, a counting problem in disguise.

History

1985

— Deutsch defines the universal quantum Turing machine, giving quantum computation a formal model

1993

— Bernstein and Vazirani found quantum complexity theory and show BQP ⊆ PSPACE

1994

— Shor's factoring algorithm supplies a candidate BQP problem outside BPP

1997

— Adleman, DeMarrais and Huang prove the sharp containment BQP ⊆ PP

1999

— Fortnow and Rogers sharpen it further to BQP ⊆ AWPP ⊆ PP

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §4.5 and Ch. 4 · Watrous, Quantum Computational Complexity (survey) and The Theory of Quantum Information · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, AMS (2002) · Preskill, Lecture Notes, Ch. 6 · Arora & Barak, Computational Complexity, Ch. 10 and 17 · Papadimitriou, Computational Complexity. Key facts underlying the arguments: the Feynman path-sum identity follows from inserting complete basis resolutions between gates; the Hadamard+Toffoli gate set is universal for $\mathsf{BQP}$ with amplitude entries in $\{0,\pm1,\pm1/\sqrt2\}$ ; the signed-count reduction establishing $\mathsf{BQP}\subseteq\mathsf{PP}$ is due to Adleman, DeMarrais & Huang (SIAM J. Comput. 26(5):1524, 1997) and Bernstein & Vazirani (SIAM J. Comput. 26(5):1411, 1997); $\mathsf{PP}\subseteq\mathsf{PSPACE}$ follows from one-branch-at-a-time enumeration with a polynomial counter; $\mathsf{BQP}\subseteq\mathsf{AWPP}$ is proved in Fortnow & Rogers (J. Comput. Syst. Sci. 59, 1999); the oracle separation $\mathsf{BQP}\not\subseteq\mathsf{PH}$ appears in Raz & Tal (STOC 2019). The example $\langle 1|HH|0\rangle=+1/2-1/2=0$ and the $2/3$ – $1/3$ promise are standard.

Prerequisites. The Complexity Class BQP · BQP versus P, NP, and PSPACE. Leads to. QIP = PSPACE · Quantum Merlin–Arthur (QMA) · The Local Hamiltonian Problem.

Ask the tutor: Want the signed path-count worked out for a three-gate circuit, or to see how the same trick upgrades to $\mathsf{QMA}\subseteq\mathsf{PP}$ and $\mathsf{QIP}=\mathsf{PSPACE}$ ?

Does BQP ⊆ PP ⊆ PSPACE mean a quantum computer is useless?

Not at all. The containment bounds the space a classical machine needs, not the time: the simulation loops over exponentially many Feynman paths, so it generally runs in exponential time — hopeless for a large circuit. What it rules out is a quantum computer efficiently solving problems that need more than polynomial memory ( $\mathsf{PSPACE}$ -hard ones); any speedup must come from interference, not brute-force search. Conjectured speedups like Shor's factoring live inside $\mathsf{PSPACE}$ while (plausibly) outside $\mathsf{P}$ and $\mathsf{BPP}$ , with no contradiction.

What exactly is the class PP?

$\mathsf{PP}$ , probabilistic polynomial time, is the set of languages decided by a poly-time randomised machine that accepts with probability strictly greater than $1/2$ exactly when the input is in the language. The crucial word is strictly: the gap may be exponentially small, so $\mathsf{PP}$ is "unbounded-error" — unlike $\mathsf{BPP}$ , which demands a constant gap. That razor-thin threshold is its power: it asks whether a signed count of accepting versus rejecting paths is positive, which is why it, not $\mathsf{NP}$ , is the natural home for the quantum path sum.

Why does interference force a counting class rather than NP?

$\mathsf{NP}$ asks an existential question: is there at least one accepting path? For a quantum computation that is meaningless — a lone path carries no observable weight, only the signed sum of amplitudes is a probability. Interference can make exponentially many nonzero paths add to exactly zero (as in $\langle 1|HH|0\rangle$ ), so the existence of accepting paths tells you nothing. What matters is whether positive contributions outweigh negative — a threshold on a signed count, precisely the $\mathsf{PP}$ (and $\#\mathsf{P}$ ) question. So the counting classes, not $\mathsf{NP}$ , capture quantum computation.

Is the PP bound on BQP believed to be tight?

No. Fortnow and Rogers (1999) proved the sharper $\mathsf{BQP}\subseteq\mathsf{AWPP}\subseteq\mathsf{PP}$ , placing $\mathsf{BQP}$ in a "low" subclass of $\mathsf{PP}$ that behaves almost like $\mathsf{P}$ relative to itself. The broad belief is that $\mathsf{BQP}$ is much smaller than $\mathsf{PP}$ and incomparable to $\mathsf{NP}$ . So the containments here are upper bounds, not equalities: they give a ceiling on quantum power, while the true extent of $\mathsf{BQP}$ — even whether $\mathsf{BQP}\ne\mathsf{BPP}$ — remains open, tied to $\mathsf{P}$ versus $\mathsf{PSPACE}$ questions we cannot yet resolve.

Who proved these containments, and when?

The framework and the $\mathsf{PSPACE}$ containment come from Ethan Bernstein and Umesh Vazirani, whose 1993 STOC paper (journal version SIAM J. Comput. 1997) defined $\mathsf{BQP}$ , built the universal quantum Turing machine, and showed $\mathsf{BQP}\subseteq\mathsf{PSPACE}$ . The sharper $\mathsf{BQP}\subseteq\mathsf{PP}$ is due to Adleman, DeMarrais and Huang (1997, "Quantum Computability"); the elementary $\mathsf{PP}\subseteq\mathsf{PSPACE}$ is counting-complexity folklore (Papadimitriou), and Fortnow–Rogers refined the bound to $\mathsf{AWPP}$ in 1999. Together they give the chain that anchors quantum complexity theory.

Can we actually run the PSPACE simulation to validate a real quantum computer?

For small circuits, yes — routinely. Path-sum and Schrödinger–Feynman simulators reproduce the output of tens of qubits by summing amplitudes, and were central to the classical rebuttals of the 2019 Sycamore claim, cutting the projected time from millennia to days. But the cost is exponential in depth and qubit count, so for a large fault-tolerant machine it is a purely theoretical bound — the useful tension: $\mathsf{BQP}\subseteq\mathsf{PSPACE}$ guarantees a simulation exists in modest memory, while its exponential time is exactly what leaves room for a real quantum advantage.

How does this relate to QIP = PSPACE and the rest of the quantum hierarchy?

The signed-amplitude-summation toolkit generalises. Add a quantum witness and you get $\mathsf{QMA}\subseteq\mathsf{PP}$ , the quantum analogue of $\mathsf{NP}\subseteq\mathsf{PP}$ . Add an interactive prover and the same argument, with semidefinite-programming machinery, yields $\mathsf{QIP}=\mathsf{PSPACE}$ — quantum interactive proofs reach exactly polynomial space. So this result is the first node in a web of containments folding quantum models into classical counting and space classes.