Quantum Complexity Classes

There exists generalizations of the time complexity classes described in Section 3 for classical models that describe related classes for quantum computation. Generalizations of the classical complexity classes \(P\) and \(BPP\) are made as follows. The analog of \({P}\) is called \(EQP\) (Exact Quantum Polynomial time). The class \(EQP\) consists of those languages that can be recognized by a quantum circuit family with a probability of success \(1\). This class is a special case of the class \(BQP\) (Bounded-error Quantum Polynomial time), which is the generalization of the classical complexity class \(BPP\). A language is in \(BQP\) if there exists a uniformly polynomial quantum circuit family which recognizes the language with a probability of success greater than \(1/2\). Once again, the \(1/2\) given here can be replaced by any number \(p\) such that  \(1/2< p \leq1\). The reason why this can be done is because  a probabilistic computation can be repeated an arbitrary number of times to increase the confidence of a certain output being correct.