Bounded-Error Quantum Polynomial-Time
The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error.
See the complexity zoo entry here.
Notable problems
- Discrete logarithm and factoring can are contained in BQP