Math Conjectures

BQPBQP versus BPPBPP

OPENLandmarkOpen problemProposed c. 1994 · Standard version

Canonical statement

Is
BPP≠BQP? BPP\ne BQP?
Here BPPBPP is classical probabilistic polynomial time with error at most 1/31/3, and BQPBQP is the analogous class decided by polynomial-time-uniform, polynomial-size quantum circuits over a fixed universal gate set, measured at the end, with error at most 1/31/3.
View source LaTeX
Is
\[
  BPP\ne BQP?
\]
Here \(BPP\) is classical probabilistic polynomial time with error at
most \(1/3\), and \(BQP\) is the analogous class decided by
polynomial-time-uniform, polynomial-size quantum circuits over a fixed
universal gate set,
measured at the end, with error at most \(1/3\).
TCS-023:[BernsteinVazirani1997][Shor1997Factoring][Watrous2009Quantum]
Theoretical computer scienceMathematical physics

Notes

The problem asks whether quantum computers are strictly stronger than classical randomized ones for decision problems: is BPP≠BQPBPP\ne BQP? The formulation emerged around 1994, as quantum complexity theory took shape; Bernstein and Vazirani laid its foundations and defined BQPBQP via uniform polynomial-size quantum circuits with bounded error [BernsteinVazirani1997].

The evidence for a separation is substantial but indirect. Shor's algorithm factors integers and computes discrete logarithms in quantum polynomial time [Shor1997Factoring], tasks with no known classical polynomial-time algorithm — but factoring is a function problem, and its classical hardness is unproven. Superpolynomial quantum speedups are also known relative to oracles [BernsteinVazirani1997]. Since BPP⊆BQP⊆PSPACEBPP\subseteq BQP\subseteq PSPACE, an unconditional separation would resolve longstanding classical questions as a byproduct, which partly explains its difficulty; the surrounding landscape is treated in Watrous's survey [Watrous2009Quantum].

No unrelativized decision language has been proved to lie in BQP∖BPPBQP\setminus BPP, and the problem remains open; a resolution requires either such a language or a classical simulation collapsing the two classes.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.