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 [math]\displaystyle{ 2/3 }[/math] for all problem instances.

Example

The decision problem for factoring is in BQP: given [math]\displaystyle{ n }[/math] and [math]\displaystyle{ k }[/math], is there a non-trivial factor of [math]\displaystyle{ n }[/math] smaller than [math]\displaystyle{ k }[/math]? This is easily seen to be equivalent to having a polynomial-time quantum algorithm to find a non-trivial factor of any composite number [math]\displaystyle{ n }[/math], with probability of outputting such a factor of at least [math]\displaystyle{ 2/3 }[/math]. 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.