Class Description

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

Linked From

No class.