'''BQP''', in [[computational complexity theory]], stands for "[[bounded-error|'''B'''ounded error]], '''Q'''uantum, [[polynomial time|'''P'''olynomial 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 [[mathematical constant|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 [[exponential decay|exponentially-small]] chance that the majority of the runs are wrong.
The number of [[qubit]]s in the computer is allowed to be a [[function (mathematics)|function]] of the instance size.
For example, algorithms are known for factoring an ''n''-bit integer using just over 2''n'' qubits.
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|Integer factorization]] (see [[Shor's algorithm]])
*[[Discrete logarithm]]
*Simulation of quantum systems (see [[universal quantum computer]])
This class is defined for a quantum computer. The corresponding class for an ordinary [[Turing machine]] plus a source of randomness is '''[[BPP]]'''.
BQP contains '''[[P (complexity)|P]]''' and '''[[BPP]]''' and is contained in '''[[PP (complexity)|PP]]''' and '''[[PSPACE]]'''. In fact, BQP is [[low (complexity)|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.
{{FromWikipedia}}
[[Category:Computational Complexity]]
[[Category:Quantum Computation]]
