Difference between revisions of "Complexity Zoo:O"

From Complexity Zoo
Jump to navigation Jump to search
m (1 revision: Complexity zoo import.)
 
Line 5: Line 5:
 
The class of problems solvable by a [[Complexity Zoo:B#bqp|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.)
 
The class of problems solvable by a [[Complexity Zoo:B#bqp|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 [[Complexity Zoo:B#bqp|BQP]] by first initializing the computer to the all-0 state.  Parker and Plenio [[zooref#pp00|[PP00]]] failed to appreciate this point.
+
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 [[Complexity Zoo:B#bqp|BQP]] by first initializing the computer to the all-0 state.
  
 
Defined by [[zooref#asv00|[ASV00]]] (though they didn't use the name OCQ), who also showed that if OCQ = [[Complexity Zoo:B#bqp|BQP]], something other than gate-by-gate simulation will be needed to show this.
 
Defined by [[zooref#asv00|[ASV00]]] (though they didn't use the name OCQ), who also showed that if OCQ = [[Complexity Zoo:B#bqp|BQP]], something other than gate-by-gate simulation will be needed to show this.
  
 
----
 
----
 +
 
===== <span id="optp" style="color:red">OptP</span>: Optimum Polynomial-Time =====
 
===== <span id="optp" style="color:red">OptP</span>: Optimum Polynomial-Time =====
 
The class of functions computable by taking the maximum of the output values over all accepting paths of an [[Complexity Zoo:N#np|NP]] machine.
 
The class of functions computable by taking the maximum of the output values over all accepting paths of an [[Complexity Zoo:N#np|NP]] machine.

Revision as of 21:21, 28 August 2014

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References


Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform


OIP - OMA - ONP - OptP - O2P


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.

Defined by [ASV00] (though they didn't use the name OCQ), who also showed that if OCQ = BQP, something other than gate-by-gate simulation will be needed to show this.


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.