Difference between revisions of "Complexity Zoo:O"
m (1 revision: Complexity zoo import.)
Revision as of 03:10, 18 November 2012
OCQ: One Clean Qubit
The class of problems solvable by a BQP machine in which a single qubit is initialized to the '0' state, and the remaining qubits are initialized to the maximally mixed state. (This definition is not known to be robust, so one also needs to specify a gate set.)
We also need to stipulate that there are no "strong measurements" -- intermediate measurements on which later operations are conditioned -- since otherwise we can do all of BQP by first initializing the computer to the all-0 state. Parker and Plenio [PP00] failed to appreciate this point.
OptP: Optimum Polynomial-Time
The class of functions computable by taking the maximum of the output values over all accepting paths of an NP machine.
Defined in [Kre88].
Contrast with FNP.