BQP

From Wikipedia

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

BQP is bounded-error, quantum, polynomial time.

In complexity theory, the class of problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/4 for all instances.

In other words, there is an algorithm for a quantum computer that is guaranteed to run in polynomial time. On any given run of the algorithm, it has a probability of at most 1/4 that it will give the wrong answer. That is true, whether the answer is YES or NO.

This class is defined for a quantum computer. The corresponding class for an ordinary Turing machine plus a source of randomness is BPP


/Talk