Quantum complexity class BQP

Summary

BQP, for bounded-error quantum polynomial time, is a complexity class of decision problems. It contains the problems that a quantum computer solves in polynomial time with error probability at most $1/3$. It is the quantum analogue of BPP. It contains BPP and is contained in PSPACE. Integer factorization, in its decision form, lies in BQP by Shor's algorithm, while no classical polynomial-time algorithm for it is known.