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 .
- Prove with GapP functions and the Hadamard–Toffoli gate set.
- Derive the Forrelation amplitude and state the Raz–Tal separation , including the role of 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 or ; estimating local-Hamiltonian dynamics 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 . It is universal for BQP despite having real entries (Shi 2003; Aharonov 2003): a complex amplitude is carried by an extra qubit as .
A Hadamard maps input bit to output bit with amplitude ; Toffolis permute basis states. A path is the string of Hadamard outputs, and both its sign and its endpoint are polynomial-time computable.
Expand as a double sum over pairs of paths and weight each output by . Only pairs of paths with the same endpoint interfere.
Each summand is a polynomial-time computable value in ; a nondeterministic machine guesses and accepts, rejects, or splits into one accepting and one rejecting branch.
Only the sign of was used.
Refinements: (Fortnow & Rogers 1999), which implies that BQP is low for PP: . Aaronson (2005) showed , quantum computation with postselection, giving another route to and a one-paragraph proof that PP is closed under intersection. Since , the path sum also runs in polynomial space.
The ADH proof uses only the sign of . What does this immediately imply?
- Quantum computation with unbounded error (accept with probability versus ) is no more powerful than PP
- Hadamard gates are unnecessary for universality
Show the answer
B. Quantum computation with unbounded error (accept with probability versus ) is no more powerful than PP
The argument never used the gap , only which side of 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 , machines may query 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.
| Separation | Oracle problem | Reference |
|---|---|---|
| (superpolynomial) | recursive Fourier sampling | Bernstein & Vazirani 1997 |
| (exponential) | Simon's problem | Simon 1997 |
| for a random oracle, with probability 1 | unstructured search | Bennett, Bernstein, Brassard & Vazirani 1997 |
| Forrelation | Raz & Tal 2019, building on Aaronson 2010 |
How strongly correlates with the Fourier transform of . Promise: either or .
Hadamards, a phase query to , Hadamards, a phase query to , Hadamards.
So : at least in the yes case, at most in the no case.
Classical randomized algorithms need queries (; Aaronson & Ambainis 2015), which makes Forrelation the problem that optimally separates quantum from classical query complexity.
In a yes-instance with , what is the probability that the Forrelation circuit outputs ?
Show the answer
0.36
The amplitude of is , so the probability is , against at most 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 .
- With Hadamard and Toffoli gates, is a GapP function, so (indeed ) and .
- Forrelation's amplitude is a single Fourier correlation; Raz and Tal turned it into an oracle with via 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.
Which result shows that no relativizing technique can prove ?
- Bennett, Bernstein, Brassard & Vazirani (1997)
- Simon (1997)
- Raz & Tal (2019)
- 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 must therefore fail relative to that oracle, i.e. it cannot relativize.
In the proof of , why is the Hadamard–Toffoli gate set convenient?
- Every path amplitude is , so probabilities become normalized differences of path counts, which are GapP functions
- It is the only universal gate set
- It makes circuits classically simulable
- It avoids measurements
Show the answer
A. Every path amplitude is , so probabilities become normalized differences of path counts, which are GapP functions
With uniform path weights, is an integer computed as an exponential sum of polynomial-time values: exactly the shape of a GapP function.
. Which ingredient makes BQP subroutines behave like a clean oracle?
- The no-cloning theorem
- Quantum error correction
- Postselection
- Error amplification followed by uncomputation, which returns the subroutine's work registers to so they do not spoil interference
Show the answer
D. Error amplification followed by uncomputation, which returns the subroutine's work registers to so they do not spoil interference
Amplification makes each answer nearly deterministic; computing, copying the answer and uncomputing leaves only exponentially small entangled garbage.
Which statement about quantum query speedups is correct?
- Exponential speedups exist for some total Boolean functions
- For total Boolean functions, deterministic and quantum query complexities are polynomially related, so exponential speedups require a promise
- Quantum algorithms never give more than a quadratic speedup in query complexity
- 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
for every total . 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).