Class Description

QAC0: Quantum AC0

The class of decision problems solvable by a family of constant-depth, polynomial-size quantum circuits. Here each layer of the circuit is a tensor product of one-qubit gates and Toffoli gates, or is a tensor product of controlled-NOT gates.

A uniformity condition may also be imposed.

Defined in [Moo99].

It is contained in QACf0, but it is not known if it contains AC0. Notice that the latter containment is not obvious, since the set of gates in QAC0 do not allow to implement fanout in any way we may take for granted.

Linked From

QAC0[m]: Quantum AC0[m]

Same as QAC0, except that now Mod-m gates are also allowed. A Mod-m gate computes whether the sum of a given set of bits is congruent to 0 modulo m, and exclusive-OR's the answer into another bit.

Defined in [Moo99].

More about...


QACf0: QAC0 With Fanout

Same as QAC0, except that an additional "quantum fanout" gate is available, which CNOT's a qubit into arbitrarily many target qubits in a single step.

Defined in [Moo99], where it was also shown that QACf0 =QAC0[2] = QACC0.Is equivalent to QNCf0 due to [Tak12].

More about...