# The complexity class BQP

Informally, the complexity class BQP contains all decision problems that can be solved efficiently by a quantum computer, with a probability of outputting the correct result at least $2/3$ for all problem instances.
The decision problem for factoring is in BQP: given $n$ and $k$, is there a non-trivial factor of $n$ smaller than $k$? This is easily seen to be equivalent to having a polynomial-time quantum algorithm to find a non-trivial factor of any composite number $n$, with probability of outputting such a factor of at least $2/3$. Shor's efficient quantum algorithm for factoring can be used to find factors in this way, and so it follows that the decision problem for factoring is in BQP.