HomePage | Recent Changes | Preferences

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


HomePage | Recent Changes | Preferences
This page is read-only | View other revisions
Last edited December 9, 2001 12:56 am by 151.202.181.xxx (diff)