The complexity class BQP

From Polymath1Wiki
Jump to: navigation, search

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

Example

The decision problem for factoring is in BQP: given [math]n[/math] and [math]k[/math], is there a non-trivial factor of [math]n[/math] smaller than [math]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]n[/math], with probability of outputting such a factor of at least [math]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.