## Sunday, 8 September 2013

### 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.