BQP (Bounded-Error Quantum Polynomial Time)

BQP stands for Bounded-Error Quantum Polynomial Time. Formally, a decision problem belongs to BQP if there exists a uniform family of polynomial-size quantum circuits such that, for every input of length n, the circuit accepts with probability at least 2/3 when the answer is “yes” and rejects with probability at least 2/3 when the answer is “no.” The 1/3 error bound is somewhat arbitrary: by repeating the computation O(k) times and taking the majority vote, the error probability can be reduced exponentially to 2^(-k), so the exact threshold does not change the class. BQP contains P (classical deterministic polynomial time) and BPP (classical bounded-error probabilistic polynomial time) as subsets, because a classical algorithm can be simulated by a quantum circuit with no overhead beyond a polynomial blowup.

The relationship between BQP and NP is one of the most important open questions in computational complexity. It is widely believed, but not proven, that BQP is not contained in NP and that NP is not contained in BQP. Shor’s algorithm for integer factoring shows that the factoring problem lies in BQP; factoring is not known to be NP-complete and is widely believed not to be, which is consistent with the conjecture that BQP does not solve all of NP. Grover’s algorithm provides a quadratic speedup for unstructured search, which is the prototypical NP-style problem, but a quadratic speedup does not collapse BQP and NP together. The oracle separation results of Bernstein and Vazirani, and later the Forrelation problem studied by Aaronson and Ambainis, show that relative to specific oracles, BQP is strictly larger than BPP, confirming that quantum computation is strictly more powerful than classical probabilistic computation in the black-box model.

Practically, BQP defines the scope of problems for which quantum algorithms offer a rigorous, provable speedup over all classical approaches. Integer factoring and discrete logarithm both fall in BQP via Shor’s algorithm, which is why quantum computers threaten RSA and elliptic-curve cryptography. Simulating quantum mechanical systems is also in BQP, motivating quantum chemistry and materials science applications. Understanding BQP matters for course learners because it sets realistic expectations: quantum computers do not solve all hard problems, only a specific (and still not fully characterized) class of them. The open BQP-vs-NP question suggests that problems like the traveling salesman problem or satisfiability are unlikely to become easy on a quantum computer, even in principle.