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