Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0002057 · IEEE Conference on Computational Complexity (CCC)

On the complexity of quantum ACC

F. Green, Steven Thomas Homer, Chris Pollett

Published Nov 7, 2002• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/ccc.2000.856756

Related papers

Counting, fanout and the complexity of quantum ACC

F. Green, Steven Thomas Homer, Cristopher Moore +1 more

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.

arXiv:quant-ph/0106017•Quantum Information and Computation•Jan 1, 2002•69 citations

Quantum Circuits: Fanout, Parity, and Counting

Cristopher Moore

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.

arXiv:quant-ph/9903046•Mar 13, 1999•71 citations

Improved Lower Bounds for QAC0

Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos +1 more

In this work, we prove the strongest known lower bounds for QAC$^0$, allowing polynomially many gates and ancillae. Our main results show that: (1) Depth-3 QAC$^0$ circuits cannot compute PARITY, and require $Ω(\exp(\sqrt{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 QAC$^0$ 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 AC$^0$ 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$ QAC$^0$ 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

quant-pharXiv:2512.14643•ACM Symposium on Theory of Computing (STOC)•Dec 17, 2025•6 citations

Bounds on the QAC$^0$ Complexity of Approximating Parity

Gregory Rosenthal

QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC$^0$ circuits are QAC circuits of constant depth, and are quantum analogues of AC$^0$ circuits. We prove the following: $\bullet$ For all $d \ge 7$ and $\varepsilon>0$ there is a depth-$d$ QAC circuit of size $\exp(\mathrm{poly}(n^{1/d}) \log(n/\varepsilon))$ that approximates the $n$-qubit parity function to within error $\varepsilon$ on worst-case quantum inputs. Previously it was unknown whether QAC circuits of sublogarithmic depth could approximate parity regardless of size. $\bullet$ We introduce a class of "mostly classical" QAC circuits, including a major component of our circuit from the above upper bound, and prove a tight lower bound on the size of low-depth, mostly classical QAC circuits that approximate this component. $\bullet$ Arbitrary depth-$d$ QAC circuits require at least $Ω(n/d)$ multi-qubit gates to achieve a $1/2 + \exp(-o(n/d))$ approximation of parity. When $d = Θ(\log n)$ this nearly matches an easy $O(n)$ size upper bound for computing parity exactly. $\bullet$ QAC circuits with at most two layers of multi-qubit gates cannot achieve a $1/2 + \exp(-o(n))$ approximation of parity, even non-cleanly. Previously it was known only that such circuits could not cleanly compute parity exactly for sufficiently large $n$. The proofs use a new normal form for quantum circuits which may be of independent interest, and are based on reductions to the problem of constructing certain generalizations of the cat state which we name "nekomata" after an analogous cat yōkai.

arXiv:2008.07470•Leibniz international proceedings in informatics•Aug 17, 2020•24 citations

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)

Daniel Grier, Jackson Morris, Kewen Wu

$\mathsf{QAC}^0$ 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 $\mathsf{AC}^0$ lower bounds to $\mathsf{QAC}^0$ have failed. We give one possible explanation of this: $\mathsf{QAC}^0$ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation $\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]$ for decision problems, which also resolves for the first time whether $\mathsf{AC}^0$ could be more powerful than $\mathsf{QAC}^0$. Moreover, we prove that $\mathsf{QAC}^0$ circuits can compute a wide range of Boolean functions if given multiple copies of the input: $\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0$. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.

cs.CCCross-listedarXiv:2601.03243•Jan 7, 2026•10 citations

Bounds on the Power of Constant-Depth Quantum Circuits

Fenner, Stephen, Frederic Green, Steven Thomas Homer +1 more

We show that if a language is recognized within certain error bounds by constant-depth quantum circuits over a finite family of gates, then it is computable in (classical) polynomial time. In particular, our results imply EQNC^0 is contained in P, where EQNC^0 is the constant-depth analog of the class EQP. On the other hand, we adapt and extend ideas of Terhal and DiVincenzo (quant-ph/0205133) to show that, for any family F of quantum gates including Hadamard and CNOT gates, computing the acceptance probabilities of depth-five circuits over F is just as hard as computing these probabilities for circuits over F. In particular, this implies that NQNC^0 = NQACC = NQP = coC=P where NQNC^0 is the constant-depth analog of the class NQP. This essentially refutes a conjecture of Green et al. that NQACC is contained in TC^0 (quant-ph/0106017).

arXiv:quant-ph/0312209•Dec 28, 2003•9 citations
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^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^00, allowing polynomially many gates and ancillae. Our main results show that: (1) Depth-3 QAC0^00 circuits cannot compute PARITY, and require Ω(exp⁡(n))Ω(\exp(\sqrt{n}))Ω(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^00 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 222 approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC0^00 circuits, which can compute PARITY exactly in depth 222 (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 222 QAC0^00 circuits, regardless of size, cannot exactly synthesize an nnn-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth 222 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
Bounds on the QAC0^00 Complexity of Approximating Parity
QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC0^00 circuits are QAC circuits of constant depth, and are quantum analogues of AC0^00 circuits. We prove the following: ∙\bullet∙ For all d≥7d \ge 7d≥7 and ε>0\varepsilon>0ε>0 there is a depth-ddd QAC circuit of size exp⁡(poly(n1/d)log⁡(n/ε))\exp(\mathrm{poly}(n^{1/d}) \log(n/\varepsilon))exp(poly(n1/d)log(n/ε)) that approximates the nnn-qubit parity function to within error ε\varepsilonε on worst-case quantum inputs. Previously it was unknown whether QAC circuits of sublogarithmic depth could approximate parity regardless of size. ∙\bullet∙ We introduce a class of "mostly classical" QAC circuits, including a major component of our circuit from the above upper bound, and prove a tight lower bound on the size of low-depth, mostly classical QAC circuits that approximate this component. ∙\bullet∙ Arbitrary depth-ddd QAC circuits require at least Ω(n/d)Ω(n/d)Ω(n/d) multi-qubit gates to achieve a 1/2+exp⁡(−o(n/d))1/2 + \exp(-o(n/d))1/2+exp(−o(n/d)) approximation of parity. When d=Θ(log⁡n)d = Θ(\log n)d=Θ(logn) this nearly matches an easy O(n)O(n)O(n) size upper bound for computing parity exactly. ∙\bullet∙ QAC circuits with at most two layers of multi-qubit gates cannot achieve a 1/2+exp⁡(−o(n))1/2 + \exp(-o(n))1/2+exp(−o(n)) approximation of parity, even non-cleanly. Previously it was known only that such circuits could not cleanly compute parity exactly for sufficiently large nnn. The proofs use a new normal form for quantum circuits which may be of independent interest, and are based on reductions to the problem of constructing certain generalizations of the cat state which we name "nekomata" after an analogous cat yōkai.
QAC0\mathsf{QAC}^0QAC0 Contains TC0\mathsf{TC}^0TC0 (with Many Copies of the Input)
QAC0\mathsf{QAC}^0QAC0 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\mathsf{AC}^0AC0 lower bounds to QAC0\mathsf{QAC}^0QAC0 have failed. We give one possible explanation of this: QAC0\mathsf{QAC}^0QAC0 circuits are significantly more powerful than their classical counterparts. We show the unconditional separation QAC0⊄AC0[p]\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]QAC0⊂AC0[p] for decision problems, which also resolves for the first time whether AC0\mathsf{AC}^0AC0 could be more powerful than QAC0\mathsf{QAC}^0QAC0. Moreover, we prove that QAC0\mathsf{QAC}^0QAC0 circuits can compute a wide range of Boolean functions if given multiple copies of the input: TC0⊆QAC0∘NC0\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0TC0⊆QAC0∘NC0. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.
We show that if a language is recognized within certain error bounds by constant-depth quantum circuits over a finite family of gates, then it is computable in (classical) polynomial time. In particular, our results imply EQNC^0 is contained in P, where EQNC^0 is the constant-depth analog of the class EQP. On the other hand, we adapt and extend ideas of Terhal and DiVincenzo (quant-ph/0205133) to show that, for any family F of quantum gates including Hadamard and CNOT gates, computing the acceptance probabilities of depth-five circuits over F is just as hard as computing these probabilities for circuits over F. In particular, this implies that NQNC^0 = NQACC = NQP = coC=P where NQNC^0 is the constant-depth analog of the class NQP. This essentially refutes a conjecture of Green et al. that NQACC is contained in TC^0 (quant-ph/0106017).