The class of decision problems solvable by polylogarithmic-depth quantum circuits with bounded probability of error. (A uniformity condition may also be imposed.)
Has the same relation to NC as BQP does to P.
[CW00] showed that factoring is in ZPP with a QNC oracle.
Is incomparable with BPP as far as anyone knows.
See also: RNC.
(Named in honor of Nick Pippenger.)
NCi is the class of decision problems solvable by a uniform family of Boolean circuits, with polynomial size, depth O(logi(n)), and fan-in 2.
Then NC is the union of NCi over all nonnegative i.
Also, NC equals the union of PT/WK(logkn, nk)/poly over all constants k.
NCi is contained in ACi; thus, NC = AC.
Contains NL, in fact NL is contained in NC2.
Generalizations include RNC and QNC.
[IN96] construct a candidate pseudorandom generator in NC based on the subset sum problem.
For a random oracle A, (NCi)A is strictly contained in (NCi+1)A, and uniform NCA is strictly contained in PA, with probability 1 [Mil92].
In descriptive complexity, NC can be defined by FO[]
Log space uniform NC is contained in ATIME(poly(log(n))) = polyL [RUZ81].
Same as QNC, but logarithmic depth instead of polylogarithmic depth.
At one point, this wiki incorrectly said that it was QNC but with exact answers instead of bounded error; this was probably someone's confusion with classes like QCMA1 vs QCMA and QMA1 vs QMA. In theory this could be QNC1, but such a class does not seem to appear in the literature (yet)!
In contrast to NC1, it is not clear how to simulate QNC1 on a quantum computer in which one qubit is initialized to a pure state, and the remaining qubits are in the maximally mixed state [ASV00].
See also [MN02].
Has the same relation to NC as RP does to P.
Contains the maximum matching problem for bipartite graphs [MVV87].
Contained in QNC.
See also: coRNC.
