In complexity theory, 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.
This class is defined for a quantum computer. The corresponding class for an ordinary Turing machine plus a source of randomness is BPP
![[Home]](wikipedia.png)