Title: On the Complexity of Quantum ACC
Authors: Green, Frederic; Homer, Steven; and Pollett, Christopher
Date: Jan 20, 2000
Abstract:
For any q > 1, let MOD_q be a quantum gate that determines if the
number of 1's in the input is divisible by q. We show that for any
q,t > 1, MOD_q is equivalent to MOD_t (up to constant depth). Based
on the case q=2, Moore has shown that quantum analogs of AC^(0),
ACC[q], and ACC, denoted QAC^(0)_wf, QACC[2], QACC respectively,
define the same class of operators, leaving q > 2 as an open
question. Our result resolves this question, implying that QAC^(0)_wf
= QACC[q] = QACC for all q. We also prove the first upper bounds for
QACC in terms of related language classes. We define classes of
languages EQACC, NQACC (both for arbitrary complex amplitudes) and
BQACC (for rational number amplitudes) and show that they are all
contained in TC^(0). To do this, we show that a TC^(0) circuit can
keep track of the amplitudes of the state resulting from the
application of a QACC operator using a constant width polynomial size
tensor sum. In order to accomplish this, we also show that TC^(0) can
perform iterated addition and multiplication in certain field
extensions.