Class Description

QNC: Quantum NC

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.

Linked From

BQNC: Alternate Name for QNC

More about...


NC: Nick's Class

(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].

More about...


QNC1: Quantum NC1

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

More about...


RNC: Randomized NC

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.

More about...