For any q>1, let MOD/sub 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, MODP is equivalent to MOD/sub t/ (up to constant depth). Based on the case q=2, C. Moore (1999) has shown that quantum analogs of AC/sup (0)/, ACC[q], and ACC, denoted QAC/sub wf//sup (0)/ QACC[2], QACC respectively, define the same class of operators, leaving q>2 as an open question. Our result resolves this question, proving that QAC/sub wf//sup (0)/=QACC[q] QACC for all q. We also develop techniques for proving upper bounds for QACC in terms of related language classes. We define classes of languages EQACC, NQACC and BQACC/sub Q/. We define a notion of log-planar QACC operators and show the appropriately restricted versions of QACC and BQACC are contained in P/poly. We also define a notion of log-gate restricted QACC operators and show the appropriately restricted versions of QACC and NQACC are contained in TC/sup (0)/. To do this last proof; we show that TC/sup (0)/ can perform iterated addition and multiplication in certain field extensions. We also introduce the notion of a polynomial-size tensor graph and we show that families of such graphs can encode the amplitudes resulting from applying an arbitrary QACC operator to an initial state.
For any q>1, let MOD/sub 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, MODP is equivalent to MOD/sub t/ (up to constant depth). Based on the case q=2, C. Moore (1999) has shown that quantum analogs of AC/sup (0)/, ACC[q], and ACC, denoted QAC/sub wf//sup (0)/ QACC[2], QACC respectively, define the same class of operators, leaving q>2 as an open question. Our result resolves this question, proving that QAC/sub wf//sup (0)/=QACC[q] QACC for all q. We also develop techniques for proving upper bounds for QACC in terms of related language classes. We define classes of languages EQACC, NQACC and BQACC/sub Q/. We define a notion of log-planar QACC operators and show the appropriately restricted versions of QACC and BQACC are contained in P/poly. We also define a notion of log-gate restricted QACC operators and show the appropriately restricted versions of QACC and NQACC are contained in TC/sup (0)/. To do this last proof; we show that TC/sup (0)/ can perform iterated addition and multiplication in certain field extensions. We also introduce the notion of a polynomial-size tensor graph and we show that families of such graphs can encode the amplitudes resulting from applying an arbitrary QACC operator to an initial state.
We propose definitions of QAC^0, the quantum analog of the classical class AC^0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC[q], the analog of the class ACC[q] where Mod_q gates are also allowed. We prove that parity or fanout allows us to construct quantum MOD_q gates in constant depth for any q, so QACC[2] = QACC. More generally, we show that for any q,p > 1, MOD_q is equivalent to MOD_p (up to constant depth and polynomial size). This implies that QAC^0 with unbounded fanout gates, denoted QACwf^0, is the same as QACC[q] and QACC for all q. Since \ACC[p] \ne ACC[q] whenever p and q are distinct primes, QACC[q] is strictly more powerful than its classical counterpart, as is QAC^0 when fanout is allowed. This adds to the growing list of quantum complexity classes which are provably more powerful than their classical counterparts. We also develop techniques for proving upper bounds for QACC in terms of related language classes. We define classes of languages closely related to QACC[2] and show that restricted versions of them can be simulated by polynomial-size circuits. With further restrictions, language classes related to QACC[2] operators can be simulated by classical threshold circuits of polynomial size and constant depth.
We propose definitions of $\QAC^0$, the quantum analog of the classical class $\AC^0$ of constant-depth circuits with AND and OR gates of arbitrary fan-in, and $\QACC[q]$, the analog of the class $\ACC[q]$ where $\Mod_q$ gates are also allowed. We prove that parity or fanout allows us to construct quantum $\MOD_q$ gates in constant depth for any q, so $\QACC[2] = \QACC$. More generally, we show that for any q,p>1, $\MOD_q$ is equivalent to $\MOD_p$ (up to constant depth). This implies that $\QAC^0$ with unbounded fanout gates, denoted $\QACwf^0$, is the same as $\QACC[q]$ and $\QACC$ for all q. Since $\ACC[p] \ne \ACC[q]$ whenever p and q are distinct primes, $\QACC[q]$ is strictly more powerful than its classical counterpart, as is $\QAC^0$ when fanout is allowed. This adds to the growing list of quantum complexity classes which are provably more powerful than their classical counterparts. We also develop techniques for proving upper bounds for $\QACC^0$ in terms of related language classes. We define classes of languages $\EQACC$, $\NQACC$ and $\BQACC_{\rats}$. We define a notion of log-planar $\QACC$ operators and show the appropriately restricted versions of $\EQACC$ and $\NQACC$ are contained in $¶/\poly$. We also define a notion of log-gate restricted $\QACC$ operators and show the appropriately restricted versions of $\EQACC$ and $\NQACC$ are contained in $\TC^0$.
We propose definitions of QAC^0, the quantum analog of the classical class AC^0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC^0[q], where n-ary Mod-q gates are also allowed. We show that it is possible to make a `cat' state on n qubits in constant depth if and only if we can construct a parity or Mod-2 gate in constant depth; therefore, any circuit class that can fan out a qubit to n copies in constant depth also includes QACC^0[2]. In addition, we prove the somewhat surprising result that parity or fanout allows us to construct Mod-q gates in constant depth for any q, so QACC^0[2] = QACC^0. Since ACC^0[p] != ACC^0[q] whenever p and q are mutually prime, QACC^0[2] is strictly more powerful than its classical counterpart, as is QAC^0 when fanout is allowed.
In this work, we prove the strongest known lower bounds for QAC0, allowing polynomially many gates and ancillae. Our main results show that:
(1) Depth-3 QAC0 circuits cannot compute PARITY, and require Ω(exp(n)) gates to compute MAJORITY.
(2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size.
We develop new classical simulation techniques for QAC0 to obtain our depth-3 bounds. In these results, we relax the output requirement of the quantum circuit to a single bit, making our depth 2 approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC0 circuits, which can compute PARITY exactly in depth 2 (exp size). Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth 2 QAC0 circuits, regardless of size, cannot exactly synthesize an n-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth 2 exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound). Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems
QAC0 Contains TC0 (with Many Copies of the Input)
QAC0 is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical AC0 lower bounds to QAC0 have failed.
We give one possible explanation of this: QAC0 circuits are significantly more powerful than their classical counterparts. We show the unconditional separation QAC0⊂AC0[p] for decision problems, which also resolves for the first time whether AC0 could be more powerful than QAC0. Moreover, we prove that QAC0 circuits can compute a wide range of Boolean functions if given multiple copies of the input: TC0⊆QAC0∘NC0. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.