The Class BQP

$\mathsf{BQP}$ — bounded-error quantum polynomial time — is the class of decision problems a quantum computer can solve efficiently. It is the quantum analogue of the classical class $\mathsf{BPP}$ , and making its definition precise forces us to pin down what "a quantum computer" means as a uniform family of circuits with bounded error.

Quantum circuits and a finite gate set

A quantum algorithm on $n$ -bit inputs is a circuit $C_n$ acting on $\mathrm{poly}(n)$ qubits, built from a fixed finite gate set such as $\{H, T, \mathrm{CNOT}\}$ . The input $x$ is encoded in the starting computational-basis state $\ket{x}\ket{0\cdots 0}$ (extra qubits are ancillas initialized to $\ket{0}$ ), the circuit is applied, and a designated output qubit is measured in the computational basis. The number of gates is the circuit's size and stands for its running time.

Two facts make this well-posed. The Solovay–Kitaev theorem guarantees that the discrete set $\{H, T, \mathrm{CNOT}\}$ is universal: any fixed-size unitary — for instance any one- or two-qubit gate from another finite universal set — can be approximated to error $\varepsilon$ by a circuit of length $O(\log^c(1/\varepsilon))$ from this set. (That polylogarithmic bound is for gates of fixed dimension; an arbitrary $k$ -qubit unitary additionally requires $\exp(k)$ gates, since it has $\sim 4^k$ free parameters.) Approximating each gate of one universal construction by gates of another therefore changes running times by only polylogarithmic factors. And we require the family $\{C_n\}$ to be uniform: a single classical polynomial-time algorithm, given $n$ , outputs a description of $C_n$ . Uniformity rules out smuggling uncomputable information into the hardware, exactly as it does for classical circuit complexity.

The definition

A language $L \subseteq \{0,1\}^*$ is in $\mathsf{BQP}$ if there is a uniform family of polynomial-size quantum circuits $\{C_n\}$ such that, on input $x$ of length $n$ , the probability $p(x)$ that measuring the output qubit yields $1$ satisfies

x \in L \ \Rightarrow\ p(x) \ge \tfrac{2}{3}, \qquad x \notin L \ \Rightarrow\ p(x) \le \tfrac{1}{3}.

The gap between $2/3$ and $1/3$ is the bounded error, and the two thirds are nothing special.

Why bounded error, not exact

One might hope for an exact quantum class with $p(x) \in \{0,1\}$ . But quantum measurement is intrinsically probabilistic, and the gate set is finite, so amplitudes are generally irrational and exact certainty is unnatural. Bounded error is the right physical notion: a real device run a polynomial number of times gives an answer that is correct with overwhelming probability. This mirrors $\mathsf{BPP}$ , where classical randomized algorithms (e.g. for polynomial identity testing) are accepted as efficient despite a small, controllable error.

Robustness of the definition

$\mathsf{BQP}$ is remarkably stable under changes that might seem significant:

Gate set. Any universal set gives the same class, via Solovay–Kitaev.
Intermediate measurements. Measuring qubits part-way through and conditioning later gates on the outcomes adds no power — the principle of deferred measurement pushes all measurements to the end.
Ancillas and garbage. Borrowed work qubits can be uncomputed and returned to $\ket{0}$ , so they do not leak information or corrupt later runs.
Amplitude precision. Specifying gate angles to $\mathrm{poly}(n)$ bits of precision suffices.

Because of this robustness, $\mathsf{BQP}$ is the accepted formalization of "efficiently solvable by a quantum computer," and it is the protagonist of the next several lessons, where we locate it relative to the classical classes and ask which problems separate it from them.

Examples and the headline question

Integer factoring and discrete logarithm are in $\mathsf{BQP}$ via Shor's algorithm, even though no efficient classical algorithm is known for them. Whether $\mathsf{BQP}$ strictly contains $\mathsf{BPP}$ — whether quantum computers are genuinely more powerful than randomized classical ones for decision problems — is open, and is the central question this module circles back to repeatedly.