Class Description

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.

Linked From

ACC0: AC0 With Arbitrary MOD Gates

Same as AC0[m], but now the constant-depth circuit can contain MOD m gates for any m.

Contained in TC0.

Indeed, can be simulated by depth-3 threshold circuits of quasipolynomial size [Yao90].

According to [All96], there is no good evidence for the existence of cryptographically secure functions in ACC0.

There is no non-uniform ACC0 circuits of polynomial size for NTIMES[2n] and no ACC0 circuit of size 2nO(1) for ENP (The class E with an NP oracle). These are the only two known nontrivial lower bounds against ACC0 and were recently discovered by [Wil11].

Contains 4-PBP [BT88].

See also: QACC0 and CC0.

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


QNCf0: Quantum NC0 With Unbounded Fanout

Constant-depth quantum circuits with unbounded-fanout gates.

Defined in [Spa02].

Contains QNC0, and is contained in QACC0.Is equivalent to QACf0 due to [Tak12].


More about...