Class Description

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

Linked From

AC0[m]: AC0 With MOD m Gates

Same as AC0, but now "MOD m" gates (for a specific m) are allowed in addition to AND, OR, and NOT gates. (A MOD m gate outputs 0 if the sum of its inputs is congruent to 0 modulo m, and 1 otherwise.)

If m is a power of a prime p, then for any prime q not equal to p, deciding whether the sum of n bits is congruent to 0 modulo q is not in AC0[m] [Raz87] [Smo87]. It follows that, for any such m, AC0[m] is strictly contained in NC1.

However, if m is a product of distinct primes (e.g. 6), then it is not even known whether AC0[m] = NP!

See also: QAC0[m].

More about...


QACC0: Quantum ACC0

Same as QAC0[m], except that Mod-m gates are allowed for any m.

Defined in [Moo99].

[GHP00] showed that QACC0 equals QAC0[p] for any prime p.

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