The complexity class BQP

From Polymath1Wiki

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.

Example

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.