Simple Algorithm
Quantum Computing · Rydberg State · 30 min

BQP: Definition & Containments

BPP ⊆ BQP ⊆ PP ⊆ PSPACE, and what we do not know.

BQP sits between BPP and PP, but where exactly? This lesson proves the containments carefully, explains why the definition is so robust, and maps the oracle worlds in which BQP escapes NP and even the entire polynomial hierarchy.

What you’ll learn

  • Define BQP and PromiseBQP via P-uniform circuit families, and prove robustness: amplification, gate-set independence and BQPBQP=BQP\mathsf{BQP}^{\mathsf{BQP}} = \mathsf{BQP}.
  • Prove BQP⊆PP\mathsf{BQP}\subseteq\mathsf{PP} with GapP functions and the Hadamard–Toffoli gate set.
  • Derive the Forrelation amplitude and state the Raz–Tal separation BQPO⊈PHO\mathsf{BQP}^O\not\subseteq\mathsf{PH}^O, including the role of AC0\mathsf{AC}^0 lower bounds.
  • Distinguish proven containments, oracle separations and open problems, including the need for structure in exponential speedups.

A robust definition

BQP itself is a semantic class with no known complete languages, but PromiseBQP has natural complete problems: deciding whether a given circuit accepts with probability ≥2/3\ge2/3 or ≤1/3\le1/3; estimating local-Hamiltonian dynamics ∣⟨0n∣e−iHt∣0n⟩∣\abs{\bra{0^n}e^{-iHt}\ket{0^n}} to inverse-polynomial accuracy (by the Feynman–Kitaev construction); and additively approximating the Jones polynomial at certain roots of unity (Freedman, Larsen & Wang 2002; Aharonov, Jones & Landau 2006).

Path sums: BQP ⊆ PP ⊆ PSPACE

Work with the gate set {H,Toffoli}\{H, \mathrm{Toffoli}\}. It is universal for BQP despite having real entries (Shi 2003; Aharonov 2003): a complex amplitude a+iba + ib is carried by an extra qubit as a∣0⟩+b∣1⟩a\ket{0} + b\ket{1}.

DerivationBQP ⊆ PP (Adleman, DeMarrais & Huang 1997)
  1. ⟨y∣C∣x⟩=2−h/2∑b∈{0,1}h(−1)ϕ(x,b) [end(x,b)=y]\bra{y}C\ket{x} = 2^{-h/2}\sum_{b\in\{0,1\}^h}(-1)^{\phi(x,b)}\,\big[\mathrm{end}(x,b) = y\big]

    A Hadamard maps input bit uu to output bit bb with amplitude (−1)ub/2(-1)^{ub}/\sqrt2; Toffolis permute basis states. A path is the string bb of Hadamard outputs, and both its sign ϕ(x,b)\phi(x,b) and its endpoint end(x,b)\mathrm{end}(x,b) are polynomial-time computable.

  2. Δ(x):=Pr⁡[1]−Pr⁡[0]=2−h∑b,b′[end(b)=end(b′)] (−1)ϕ(b)+ϕ(b′)+1+end(b)1\Delta(x) := \Pr[1]-\Pr[0] = 2^{-h}\sum_{b,b'}\big[\mathrm{end}(b) = \mathrm{end}(b')\big]\,(-1)^{\phi(b)+\phi(b')+1+\mathrm{end}(b)_1}

    Expand ∣⟨y∣C∣x⟩∣2\abs{\bra{y}C\ket{x}}^2 as a double sum over pairs of paths and weight each output yy by (−1)1+y1(-1)^{1+y_1}. Only pairs of paths with the same endpoint interfere.

  3. g(x):=2h Δ(x)∈GapPg(x) := 2^h\,\Delta(x)\in\mathsf{GapP}

    Each summand is a polynomial-time computable value in {−1,0,+1}\{-1,0,+1\}; a nondeterministic machine guesses (b,b′)(b,b') and accepts, rejects, or splits into one accepting and one rejecting branch.

  4. x∈L⇒Δ(x)≥13>0,x∉L⇒Δ(x)≤−13<0⟹L∈PP■x\in L\Rightarrow\Delta(x)\ge\tfrac13>0,\qquad x\notin L\Rightarrow\Delta(x)\le-\tfrac13<0\qquad\Longrightarrow\qquad L\in\mathsf{PP}\quad\blacksquare

    Only the sign of gg was used.

Refinements: BQP⊆AWPP⊆PP\mathsf{BQP}\subseteq\mathsf{AWPP}\subseteq\mathsf{PP} (Fortnow & Rogers 1999), which implies that BQP is low for PP: PPBQP=PP\mathsf{PP}^{\mathsf{BQP}} = \mathsf{PP}. Aaronson (2005) showed PostBQP=PP\mathsf{PostBQP} = \mathsf{PP}, quantum computation with postselection, giving another route to BQP⊆PP\mathsf{BQP}\subseteq\mathsf{PP} and a one-paragraph proof that PP is closed under intersection. Since PP⊆PSPACE\mathsf{PP}\subseteq\mathsf{PSPACE}, the path sum also runs in polynomial space.

Check your understanding

The ADH proof uses only the sign of g(x)=2h(Pr⁡[1]−Pr⁡[0])g(x) = 2^h(\Pr[1]-\Pr[0]). What does this immediately imply?

  1. BQP=PP\mathsf{BQP} = \mathsf{PP}
  2. Quantum computation with unbounded error (accept with probability >1/2>1/2 versus ≤1/2\le1/2) is no more powerful than PP
  3. BQP⊆NP\mathsf{BQP}\subseteq\mathsf{NP}
  4. Hadamard gates are unnecessary for universality
Show the answer

B. Quantum computation with unbounded error (accept with probability >1/2>1/2 versus ≤1/2\le1/2) is no more powerful than PP

The argument never used the gap 1/31/3, only which side of 1/21/2 the acceptance probability lies on. So unbounded-error quantum polynomial time (PQP) is contained in PP; since quantum circuits can simulate PP machines, the two are equal.

Oracle worlds

Relative to an oracle OO, machines may query OO at unit cost. A proof technique that relativizes (treats subroutines as black boxes) cannot settle a question whose answer flips between oracles. Most of what is known about BQP versus classical classes is relativized.

SeparationOracle problemReference
BQPO⊈BPPO\mathsf{BQP}^O\not\subseteq\mathsf{BPP}^O (superpolynomial)recursive Fourier samplingBernstein & Vazirani 1997
BQPO⊈BPPO\mathsf{BQP}^O\not\subseteq\mathsf{BPP}^O (exponential)Simon's problemSimon 1997
NPO⊈BQPO\mathsf{NP}^O\not\subseteq\mathsf{BQP}^O for a random oracle, with probability 1unstructured searchBennett, Bernstein, Brassard & Vazirani 1997
BQPO⊈PHO\mathsf{BQP}^O\not\subseteq\mathsf{PH}^OForrelationRaz & Tal 2019, building on Aaronson 2010
DerivationForrelation in one query to each function (Aaronson 2010)
  1. Φf,g:=123n/2∑x,y∈{0,1}nf(x) (−1)x⋅y g(y),f,g:{0,1}n→{±1}\Phi_{f,g} := \frac{1}{2^{3n/2}}\sum_{x,y\in\{0,1\}^n}f(x)\,(-1)^{x\cdot y}\,g(y),\qquad f,g:\{0,1\}^n\to\{\pm1\}

    How strongly gg correlates with the Fourier transform of ff. Promise: either ∣Φ∣≤1/100\abs{\Phi}\le1/100 or Φ≥3/5\Phi\ge3/5.

  2. H⊗n Og H⊗n Of H⊗n∣0n⟩,Of∣x⟩=f(x)∣x⟩H^{\otimes n}\,O_g\,H^{\otimes n}\,O_f\,H^{\otimes n}\ket{0^n},\qquad O_f\ket{x} = f(x)\ket{x}

    Hadamards, a phase query to ff, Hadamards, a phase query to gg, Hadamards.

  3. ⟨0n∣H⊗nOgH⊗nOfH⊗n∣0n⟩=12n/2∑y(12n∑xf(x)(−1)x⋅y)g(y)=Φf,g\bra{0^n}H^{\otimes n}O_gH^{\otimes n}O_fH^{\otimes n}\ket{0^n} = \frac{1}{2^{n/2}}\sum_y\Big(\frac{1}{2^n}\sum_xf(x)(-1)^{x\cdot y}\Big)g(y) = \Phi_{f,g}

    So Pr⁡[0n]=Φ2\Pr[0^n] = \Phi^2: at least 0.360.36 in the yes case, at most 10−410^{-4} in the no case.

  4. Classical randomized algorithms need Ω~(N)\tilde\Omega(\sqrt N) queries (N=2nN = 2^n; Aaronson & Ambainis 2015), which makes Forrelation the problem that optimally separates quantum from classical query complexity.

Predict before you look

In a yes-instance with Φf,g=0.6\Phi_{f,g} = 0.6, what is the probability that the Forrelation circuit outputs 0n0^n?

Show the answer

0.36

The amplitude of 0n0^n is Φ\Phi, so the probability is Φ2=0.36\Phi^2 = 0.36, against at most 10−410^{-4} in no-instances. A constant number of repetitions decides the promise.

What we do not know

Key takeaways

  • PromiseBQP is defined by P-uniform polynomial-size circuits with bounded error; the class is robust to gate sets, error constants, measurements and machine models, and BQPBQP=BQP\mathsf{BQP}^{\mathsf{BQP}} = \mathsf{BQP}.
  • With Hadamard and Toffoli gates, 2h(Pr⁡[1]−Pr⁡[0])2^h(\Pr[1]-\Pr[0]) is a GapP function, so BQP⊆PP\mathsf{BQP}\subseteq\mathsf{PP} (indeed ⊆AWPP\subseteq\mathsf{AWPP}) and BQP⊆PSPACE\mathsf{BQP}\subseteq\mathsf{PSPACE}.
  • Forrelation's amplitude is a single Fourier correlation; Raz and Tal turned it into an oracle with BQPO⊈PHO\mathsf{BQP}^O\not\subseteq\mathsf{PH}^O via AC0\mathsf{AC}^0 lower bounds.
  • Unrelativized relations between BQP and NP or PH are open; exponential speedups need structure.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Which result shows that no relativizing technique can prove BQP⊆PH\mathsf{BQP}\subseteq\mathsf{PH}?

  1. Bennett, Bernstein, Brassard & Vazirani (1997)
  2. Simon (1997)
  3. Raz & Tal (2019)
  4. Adleman, DeMarrais & Huang (1997)
Show the answer

C. Raz & Tal (2019)

Raz and Tal constructed an oracle relative to which BQP contains a problem outside PH. Any proof of BQP⊆PH\mathsf{BQP}\subseteq\mathsf{PH} must therefore fail relative to that oracle, i.e. it cannot relativize.

Question 2

In the proof of BQP⊆PP\mathsf{BQP}\subseteq\mathsf{PP}, why is the Hadamard–Toffoli gate set convenient?

  1. Every path amplitude is ±2−h/2\pm2^{-h/2}, so probabilities become normalized differences of path counts, which are GapP functions
  2. It is the only universal gate set
  3. It makes circuits classically simulable
  4. It avoids measurements
Show the answer

A. Every path amplitude is ±2−h/2\pm2^{-h/2}, so probabilities become normalized differences of path counts, which are GapP functions

With uniform path weights, 2h(Pr⁡[1]−Pr⁡[0])2^h(\Pr[1]-\Pr[0]) is an integer computed as an exponential sum of polynomial-time ±1\pm1 values: exactly the shape of a GapP function.

Question 3

BQPBQP=BQP\mathsf{BQP}^{\mathsf{BQP}} = \mathsf{BQP}. Which ingredient makes BQP subroutines behave like a clean oracle?

  1. The no-cloning theorem
  2. Quantum error correction
  3. Postselection
  4. Error amplification followed by uncomputation, which returns the subroutine's work registers to ∣0⟩\ket0 so they do not spoil interference
Show the answer

D. Error amplification followed by uncomputation, which returns the subroutine's work registers to ∣0⟩\ket0 so they do not spoil interference

Amplification makes each answer nearly deterministic; computing, copying the answer and uncomputing leaves only exponentially small entangled garbage.

Question 4

Which statement about quantum query speedups is correct?

  1. Exponential speedups exist for some total Boolean functions
  2. For total Boolean functions, deterministic and quantum query complexities are polynomially related, so exponential speedups require a promise
  3. Quantum algorithms never give more than a quadratic speedup in query complexity
  4. Forrelation separates quantum and classical query complexity only polynomially
Show the answer

B. For total Boolean functions, deterministic and quantum query complexities are polynomially related, so exponential speedups require a promise

D(f)=O(Q(f)4)D(f) = \order{Q(f)^4} for every total ff. Exponential separations (Simon, period finding, Forrelation) all rely on a promise on the input.

Further reading

  • E. Bernstein & U. Vazirani, "Quantum complexity theory", SIAM Journal on Computing 26, 1411 (1997).
  • L. M. Adleman, J. DeMarrais & M.-D. A. Huang, "Quantum computability", SIAM Journal on Computing 26, 1524 (1997).
  • L. Fortnow & J. Rogers, "Complexity limitations on quantum computation", Journal of Computer and System Sciences 59, 240 (1999).
  • S. Aaronson, "BQP and the polynomial hierarchy", Proceedings of STOC (2010).
  • R. Raz & A. Tal, "Oracle separation of BQP and PH", Proceedings of STOC (2019); Journal of the ACM (2022).