BQP

The complexity class BQP (bounded error quantum polynomial time) is a concept from complexity theory, a branch of theoretical computer science. For BQP are all problems that are solvable in polynomial time on a quantum computer with an error probability of at most 1/3. It is the equivalent of the class BPP, which is defined for the time spent on Turing machines. BPP as the class defining the error probability to be 1/ 3 is also arbitrarily on BQP, by repeatedly applying a BQP algorithm can arbitrarily low probability of error is achieved.

Relation to other complexity classes

Complexity classes P and BPP contained in BQP, BQP contained in PP and thus also in PSPACE. It is unknown whether these inclusions are genuine or not.

Problems in BQP

There are several problems in BQP known, of which it is assumed that they are not in BPP. The most famous is the factoring problem that can be solved using the algorithm of Shor.