Every kind of computer comes with a fine-print clause: "efficient" means this family of problems and no more. For an ordinary laptop that clause is the class P — the problems it can chew through in polynomial time. A quantum computer runs a quantum circuit instead of a classical program, so it comes with its own fine print, a new class of "efficiently solvable" problems called BQP. This page pins down exactly what that clause says — and, just as importantly, what it does not say. (Spoiler: a quantum computer is not a magic box that cracks every hard problem.)

What BQP stands for

BQP is short for Bounded-error Quantum Polynomial time. Take the name apart word by word and you have the whole definition:

• Quantum — the machine is a quantum circuit: qubits, gates, and a measurement at the end.
• Polynomial time — the circuit has polynomial size: on an input of length n it uses at most p(n) gates for some fixed polynomial p. (Technically we need a uniform family of circuits, one per input length, that a classical computer can print out quickly — so there is no cheating by hiding the answer inside an impossible-to-build circuit.)
• Bounded error — measuring is random, so we do not demand a guaranteed answer. We only demand that the circuit gives the correct yes/no answer with probability at least \tfrac{2}{3}.

Put together: a decision problem is in BQP if a polynomial-size quantum circuit answers it correctly with probability at least \tfrac{2}{3}. It is the quantum analogue of P — and, because it allows randomness, more precisely of the classical randomised class BPP (Bounded-error Probabilistic Polynomial time). BQP is our formal answer to the question "what can a quantum computer solve efficiently?"

Why \tfrac{2}{3} is not a fussy choice

The threshold \tfrac{2}{3} looks arbitrary, and it is — any constant safely above \tfrac{1}{2} would define the very same class. That is the whole point of bounded error: a small, fixed edge over a coin flip can be amplified to near-certainty for free. Run the circuit many times and take a majority vote; because each run is an independent nudge toward the right answer, the votes pile up and the chance of the majority being wrong collapses exponentially.

Formally, if each run is correct with probability p = \tfrac{2}{3}, then over k independent runs the probability that a majority are wrong shrinks like

a bound from the Chernoff/Hoeffding inequality. So to reach any target confidence you repeat only a constant number of times, and to drive the error below 2^{-n} you repeat a mere O(n) times — still polynomial. Repetition is cheap, so the exact starting threshold simply does not matter.

Worked example 1: amplifying \tfrac{2}{3} to near-certainty

Suppose a BQP circuit answers correctly with probability p = \tfrac{2}{3} and we want to be more sure. Run it three independent times and take the majority of the three answers. The majority is wrong only if two or three of the runs are wrong. With q = 1 - p = \tfrac13 the chance of a wrong run,

Three runs already pull the error from 0.33 down to about 0.26. Push to, say, k = 100 runs and the bound e^{-k/18} = e^{-100/18} \approx 0.0039 puts the error under half a percent; a few hundred more runs make it astronomically small. The lesson: bounded error is not a weakness — the \tfrac23 guarantee is as good as certainty once you are willing to repeat a handful of times.

Where BQP sits

How powerful is a quantum computer, then? The honest answer is that we know it sits between two familiar classical classes, but we cannot yet pin it exactly. Every containment below is a proven theorem:

The lower end says a quantum computer is at least as strong as a classical (even randomised) one — anything in BPP is in BQP, since a quantum circuit can just simulate a classical one. The upper end, \mathrm{BQP} \subseteq \mathrm{PSPACE}, is the crucial ceiling: a classical machine can simulate any quantum circuit using only polynomial memory (by summing over amplitudes one path at a time), so a quantum computer is no more than exponentially faster and is not known to solve PSPACE-hard problems. Quantum computing bends the landscape; it does not blow the roof off it.

The class picture — and NP off to one side

The nesting \mathrm{P} \subseteq \mathrm{BPP} \subseteq \mathrm{BQP} \subseteq \mathrm{PSPACE} is a tidy stack of Russian dolls. But the class everyone wants BQP to swallow — NP, the home of the notoriously hard NP-complete problems — does not nest neatly at all. Step through the figure: the quantum stack builds up, and then NP is drawn as a separate blob that overlaps BQP without either one containing the other.

Both BQP and NP contain P, so they must overlap somewhere. But neither is known to contain the other: no NP-complete problem is known to be in BQP, and BQP is not known to sit inside NP. They are believed to be incomparable — two different kinds of power that happen to share a common core.

Worked example 2: sorting real problems into the picture

The map earns its keep when you drop actual problems onto it.

• Integer factoring and the discrete logarithm — famously in BQP, thanks to Shor's algorithm. Neither is known to be in P or BPP, so they are our strongest evidence that BQP is strictly bigger than BPP: quantum genuinely buys something. Crucially, factoring is not believed to be NP-complete — it lives in the mild NP∩co-NP corner, not among the hardest NP problems — so cracking it says nothing about whether quantum beats NP in general.
• Unstructured search — finding a marked item among N with Grover's algorithm — a quantum computer needs about \sqrt{N} steps instead of N. A real speed-up, but only quadratic: it does not make an exponential search polynomial, so it does not put NP-complete problems into BQP.
• Sorting, primality testing, shortest paths — already in P, hence automatically in BQP. A quantum computer inherits everything a classical one can do efficiently.

Notice the pattern: the problems quantum helps with (factoring, discrete log) have hidden algebraic structure a quantum circuit can exploit. Generic, structureless NP-complete problems show no such handle — which is exactly why nobody expects BQP to contain them.

Summary