BQP, in computational complexity theory, stands for "Bounded error, Quantum, Polynomial time". It denotes the class of problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/4 for all instances.
In other words, there is an algorithm for a quantum computer that is guaranteed to run in polynomial time. On any given run of the algorithm, it has a probability of at most 1/4 that it will give the wrong answer. That is true, whether the answer is YES or NO.
The choice of 1/4 in the definition is arbitrary. Changing the constant to any real number k such that 0 < k < 1/2 does not change the set BQP. The idea is that there is a small probability of error, but running the algorithm many times produces an exponentially-small chance that the majority of the runs are wrong.
Quantum computers have gained widespread interest because some problems of practical interest are known to be in BQP, but suspected to be outside P. Currently, only three such problems are known:
- Integer factorization (see Shor's algorithm)
- Discrete logarithm
- Simulation of quantum systems (see universal quantum computer)
BQP contains P and BPP and is contained in PP and PSPACE. In fact, BQP is low for PP, meaning that a PP machine achieves no benefit from being able to solve BQP problems instantly, an indication of the vast difference in power between these similar classes.