BQP

BQP, short for bounded-error quantum polynomial time, is the class of decision problems solvable by a quantum computer in polynomial time with error probability kept strictly below a fixed bound, typically at most 1/3 for all inputs. Concretely, a language L is in BQP if there exists a family of quantum circuits of polynomial size, uniformly generated in polynomial time, such that for every input x, the circuit outputs 1 with probability at least 2/3 when x is in L, and outputs 0 with probability at least 2/3 when x is not in L.

The standard model uses the quantum circuit paradigm: computation proceeds via unitary gates on qubits, followed by measurements whose outcomes are probabilistic. Uniformity means a classical Turing machine can efficiently produce the description of the circuit C_n for input length n. Error reduction is possible by repeating the computation and taking a majority vote, or through amplitude amplification, enabling the success probability to be made arbitrarily close to 1.

Relations with other complexity classes are well-studied. It is known that P ⊆ BQP and BPP ⊆ BQP, since quantum computers can simulate deterministic and probabilistic classical computation with polynomial overhead. BQP is contained in EXP, since any quantum computation can be simulated by a classical computer in exponential time. It is not known whether BQP contains NP or is contained in NP, and most researchers do not expect BQP to equal NP, though definitive separations are not established. A key example of a BQP-complete problem is factoring integers, via Shor’s algorithm, which runs in polynomial time on a quantum computer but is not known to be efficiently solvable classically.