Quantum complexity class BQP

Remarks

An equivalent definition uses uniform families of quantum circuits. A language $L$ is in BQP exactly when some classical polynomial-time algorithm does the following. On input $1^n$ it outputs a quantum circuit $C_n$ of polynomial size that decides $L$ on inputs of length $n$ with error at most $1/3$.

Example: every language in P is in BQP. A reversible version of a deterministic polynomial-time computation can be run on a quantum machine, and it gives the right answer with probability $1$.

Non-example: if in clause 2 one only asks for probability greater than $1/2$, with no gap from $1/2$, one gets the class PP, which contains BQP. With bounded error, repeating $M$ and taking the majority makes the error exponentially small, which is why $1/3$ can be replaced by any constant below $1/2$.

Known inclusions are $\mathrm{BPP} \subseteq \mathrm{BQP} \subseteq \mathrm{PP} \subseteq \mathrm{PSPACE}$.