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:2410.06499 · ACM Symposium on Theory of Computing (STOC)

On the Computational Power of QAC0 with Barely Superlinear Ancillae

Anurag Anshu, Yangjing Dong, Fengning Ou, Penghui Yao

Published Jun 15, 2025• 1 citation
arXivHTMLPDF

Abstract

$\mathrm{QAC}^0$ is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore [arXiv: 9903046] as a quantum counterpart of $\mathrm{AC}^0$, along with the conjecture that $\mathrm{QAC}^0$ circuits can not compute PARITY. In this work we make progress on this longstanding conjecture: we show that any depth-$d$ $\mathrm{QAC}^0$ circuit requires $n^{1+3^{-d}}$ ancillae to compute a function with approximate degree $Θ(n)$, which includes PARITY, MAJORITY and $\mathrm{MOD}_k$. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first superlinear lower bound on the super-linear sized $\mathrm{QAC}^0$. Regarding PARITY, we show that any further improvement on the size of ancillae to $n^{1+\exp(-o(d))}$ would imply that PARITY $\not\in$ QAC0. These lower bounds are derived by giving low-degree approximations to $\mathrm{QAC}^0$ circuits. We show that a depth-$d$ $\mathrm{QAC}^0$ circuit with $a$ ancillae, when applied to low-degree operators, has a degree $(n+a)^{1-3^{-d}}$ polynomial approximation in the spectral norm. This implies that the class $\mathrm{QLC}^0$, corresponding to linear size $\mathrm{QAC}^0$ circuits, has approximate degree $o(n)$. This is a quantum generalization of the result that $\mathrm{LC}^0$ circuits have approximate degree $o(n)$ by Bun, Robin, and Thaler [SODA 2019]. Our result also implies that $\mathrm{QLC}^0\neq\mathrm{NC}^1$.

DOI
10.1145/3717823.3718189

Related papers

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•0 citations

On the Computational Power of Geometrically Local QAC circuits

Yangjing Dong, Fengning Ou, Penghui Yao

The computational power of $\mathsf{QAC}$, which are constant-depth quantum circuit families consisting of arbitrary single-qubit unitaries and n-qubit generalized Toffoli gates, has gained tremendous focus recently. In this work, we initiate the study of the computational complexity of geometrically local $\mathsf{QAC}$ circuits, where the qubits are arranged in a high-dimensional grid, and all the generalized Toffoli gates act on contiguous qubits along one direction. We prove that $\mathsf{2D\text{-}QAC}$ circuits are universal: any $\mathsf{QAC}$ circuit can be exactly simulated by a two-dimensional geometrically local $\mathsf{QAC}$ circuit. Therefore, we focus on the computational power of $\mathsf{2D\text{-}QAC}$ circuits with grid width $w$. We prove that $\mathsf{PARITY}$ computation has a tight width--depth tradeoff of $w=n^{Θ(1/d)}$ in the constant-depth regime if the circuit allows arbitrary ancilla. Moreover, for polynomial-size circuits, a width lower bound of $n^{ω(1/d)}$ for $\mathsf{PARITY}$ would imply $\mathsf{PARITY}\notin\mathsf{QAC}^0$. We also establish Fourier tail and sensitivity bounds, together with tight width lower bounds and tight depth lower bounds in $\mathsf{1D\text{-}QAC}$ circuits for $\mathsf{MAJORITY}$ and $\mathsf{MOD}$ computation. Our main tool is \emph{local measurement variance}, the maximum variance of normalized sums of observables on separated regions. We use a hybrid argument to show that each layer of a $\mathsf{2D\text{-}QAC}^0$ circuit increases this variance by at most a factor depending only on its width, yielding a variance bound for every $\mathsf{2D\text{-}QAC}^0$ state. The high local measurement variance of cat and Dicke states then gives the width lower bounds.

quant-pharXiv:2604.07178•Apr 9, 2026•0 citations

On the Pauli Spectrum of QAC0

Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos +1 more

The circuit class QAC0 was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower bounds against such circuits is a longstanding challenge in quantum circuit complexity; in particular, showing that polynomial-size QAC0 cannot compute the parity function has remained an open question for over 20 years. In this work, we identify a notion of the Pauli spectrum of QAC0 circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical AC0 circuits. We conjecture that the Pauli spectrum of QAC0 circuits satisfies low-degree concentration, in analogy to the famous Linial, Mansour, Nisan (LMN) theorem on the low-degree Fourier concentration of AC0 circuits. If true, this conjecture immediately implies that polynomial-size QAC0 circuits cannot compute parity. We prove this conjecture for the class of depth-d, polynomial-size QAC0 circuits with at most nO(1/d) auxiliary qubits. We obtain new circuit lower bounds and learning results as applications: this class of circuits cannot correctly compute the n-bit parity function on more than (1/2 + 2−Ω(n1/d))-fraction of inputs, and the n-bit majority function on more than (1/2 + O(n−1/4))-fraction of inputs. Additionally we show that this class of QAC0 circuits with limited auxiliary qubits can be learned with quasipolynomial sample complexity, giving the first learning result for QAC0 circuits. More broadly, our results add evidence that “Pauli-analytic” techniques can be a powerful tool in studying quantum circuits.

arXiv:2311.09631•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•11 citations

Depth-Optimal Quantum Compilation

Francisca Vasconcelos

We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $δ>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+δ}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, $T$, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth $O(\log\log(1/\varepsilon))$, and we prove a matching $Ω(\log\log(1/\varepsilon))$-depth lower bound. Overall, we establish that $Θ(\log\log(1/\varepsilon))$-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-$d$ QAC circuit can be simulated in depth $O(d)$ using only Hadamard, $X$, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity$\notin$QAC$^0$ to proving a Parity lower bound against circuits consisting only of Hadamard, $X$, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.

quant-pharXiv:2609.34659•Sep 29, 2026•0 citations

Low-degree approximation of QAC$^0$ circuits

Ashley Montanaro, Changpeng Shao, Dominic Verdon

QAC$^0$ is the class of constant-depth quantum circuits with polynomially many ancillary qubits, where Toffoli gates on arbitrarily many qubits are allowed. In this work, we show that the parity function cannot be computed in QAC$^0$, resolving a long-standing open problem in quantum circuit complexity more than twenty years old. As a result, this proves ${\rm QAC}^0 \subsetneqq {\rm QAC}_{\rm wf}^0$. We also show that any QAC circuit of depth $d$ that approximately computes parity on $n$ bits requires $2^{\widetildeΩ(n^{1/d})}$ ancillary qubits, which is close to tight. This implies a similar lower bound on approximately preparing cat states using QAC circuits. Finally, we prove a quantum analog of the Linial-Mansour-Nisan theorem for QAC$^0$. This implies that, for any QAC$^0$ circuit $U$ with $a={\rm poly}(n)$ ancillary qubits, and for any $x\in\{0,1\}^n$, the correlation between $Q(x)$ and the parity function is bounded by ${1}/{2} + 2^{-\widetildeΩ(n^{1/d})}$, where $Q(x)$ denotes the output of measuring the output qubit of $U|x,0^a\rangle$. All the above consequences rely on the following technical result. If $U$ is a QAC$^0$ circuit with $a={\rm poly}(n)$ ancillary qubits, then there is a distribution $\mathcal{D}$ of bounded polynomials of degree polylog$(n)$ such that with high probability, a random polynomial from $\mathcal{D}$ approximates the function $\langle x,0^a| U^†Z_{n+1} U |x,0^a\rangle$ for a large fraction of $x\in \{0,1\}^n$. This result is analogous to the Razborov-Smolensky result on the approximation of AC$^0$ circuits by random low-degree polynomials.

arXiv:2411.00976•Nov 1, 2024•0 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•0 citations
QAC0\mathrm{QAC}^0QAC0 is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore [arXiv: 9903046] as a quantum counterpart of AC0\mathrm{AC}^0AC0, along with the conjecture that QAC0\mathrm{QAC}^0QAC0 circuits can not compute PARITY. In this work we make progress on this longstanding conjecture: we show that any depth-ddd QAC0\mathrm{QAC}^0QAC0 circuit requires n1+3−dn^{1+3^{-d}}n1+3−d ancillae to compute a function with approximate degree Θ(n)Θ(n)Θ(n), which includes PARITY, MAJORITY and MODk\mathrm{MOD}_kMODk​. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first superlinear lower bound on the super-linear sized QAC0\mathrm{QAC}^0QAC0. Regarding PARITY, we show that any further improvement on the size of ancillae to n1+exp⁡(−o(d))n^{1+\exp(-o(d))}n1+exp(−o(d)) would imply that PARITY ∉\not\in∈ QAC0. These lower bounds are derived by giving low-degree approximations to QAC0\mathrm{QAC}^0QAC0 circuits. We show that a depth-ddd QAC0\mathrm{QAC}^0QAC0 circuit with aaa ancillae, when applied to low-degree operators, has a degree (n+a)1−3−d(n+a)^{1-3^{-d}}(n+a)1−3−d polynomial approximation in the spectral norm. This implies that the class QLC0\mathrm{QLC}^0QLC0, corresponding to linear size QAC0\mathrm{QAC}^0QAC0 circuits, has approximate degree o(n)o(n)o(n). This is a quantum generalization of the result that LC0\mathrm{LC}^0LC0 circuits have approximate degree o(n)o(n)o(n) by Bun, Robin, and Thaler [SODA 2019]. Our result also implies that QLC0≠NC1\mathrm{QLC}^0\neq\mathrm{NC}^1QLC0=NC1.
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
The computational power of QAC\mathsf{QAC}QAC, which are constant-depth quantum circuit families consisting of arbitrary single-qubit unitaries and n-qubit generalized Toffoli gates, has gained tremendous focus recently. In this work, we initiate the study of the computational complexity of geometrically local QAC\mathsf{QAC}QAC circuits, where the qubits are arranged in a high-dimensional grid, and all the generalized Toffoli gates act on contiguous qubits along one direction. We prove that 2D-QAC\mathsf{2D\text{-}QAC}2D-QAC circuits are universal: any QAC\mathsf{QAC}QAC circuit can be exactly simulated by a two-dimensional geometrically local QAC\mathsf{QAC}QAC circuit. Therefore, we focus on the computational power of 2D-QAC\mathsf{2D\text{-}QAC}2D-QAC circuits with grid width www. We prove that PARITY\mathsf{PARITY}PARITY computation has a tight width--depth tradeoff of w=nΘ(1/d)w=n^{Θ(1/d)}w=nΘ(1/d) in the constant-depth regime if the circuit allows arbitrary ancilla. Moreover, for polynomial-size circuits, a width lower bound of nω(1/d)n^{ω(1/d)}nω(1/d) for PARITY\mathsf{PARITY}PARITY would imply PARITY∉QAC0\mathsf{PARITY}\notin\mathsf{QAC}^0PARITY∈/QAC0. We also establish Fourier tail and sensitivity bounds, together with tight width lower bounds and tight depth lower bounds in 1D-QAC\mathsf{1D\text{-}QAC}1D-QAC circuits for MAJORITY\mathsf{MAJORITY}MAJORITY and MOD\mathsf{MOD}MOD computation. Our main tool is \emph{local measurement variance}, the maximum variance of normalized sums of observables on separated regions. We use a hybrid argument to show that each layer of a 2D-QAC0\mathsf{2D\text{-}QAC}^02D-QAC0 circuit increases this variance by at most a factor depending only on its width, yielding a variance bound for every 2D-QAC0\mathsf{2D\text{-}QAC}^02D-QAC0 state. The high local measurement variance of cat and Dicke states then gives the width lower bounds.
The circuit class QAC0 was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower bounds against such circuits is a longstanding challenge in quantum circuit complexity; in particular, showing that polynomial-size QAC0 cannot compute the parity function has remained an open question for over 20 years. In this work, we identify a notion of the Pauli spectrum of QAC0 circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical AC0 circuits. We conjecture that the Pauli spectrum of QAC0 circuits satisfies low-degree concentration, in analogy to the famous Linial, Mansour, Nisan (LMN) theorem on the low-degree Fourier concentration of AC0 circuits. If true, this conjecture immediately implies that polynomial-size QAC0 circuits cannot compute parity. We prove this conjecture for the class of depth-d, polynomial-size QAC0 circuits with at most nO(1/d) auxiliary qubits. We obtain new circuit lower bounds and learning results as applications: this class of circuits cannot correctly compute the n-bit parity function on more than (1/2 + 2−Ω(n1/d))-fraction of inputs, and the n-bit majority function on more than (1/2 + O(n−1/4))-fraction of inputs. Additionally we show that this class of QAC0 circuits with limited auxiliary qubits can be learned with quasipolynomial sample complexity, giving the first learning result for QAC0 circuits. More broadly, our results add evidence that “Pauli-analytic” techniques can be a powerful tool in studying quantum circuits.
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant δ>0δ>0δ>0, it ε\varepsilonε-approximates an arbitrary single-qubit gate using O(log⁡1+δ(1/ε))O(\log^{1+δ}(1/\varepsilon))O(log1+δ(1/ε)) clean ancillae, Hadamard and TTT single-qubit gates, O(log⁡(1/ε))O(\log(1/\varepsilon))O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, TTT, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth O(log⁡log⁡(1/ε))O(\log\log(1/\varepsilon))O(loglog(1/ε)), and we prove a matching Ω(log⁡log⁡(1/ε))Ω(\log\log(1/\varepsilon))Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(log⁡log⁡(1/ε))Θ(\log\log(1/\varepsilon))Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-ddd QAC circuit can be simulated in depth O(d)O(d)O(d) using only Hadamard, XXX, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity∉\notin∈/QAC0^00 to proving a Parity lower bound against circuits consisting only of Hadamard, XXX, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.
Low-degree approximation of QAC0^00 circuits
QAC0^00 is the class of constant-depth quantum circuits with polynomially many ancillary qubits, where Toffoli gates on arbitrarily many qubits are allowed. In this work, we show that the parity function cannot be computed in QAC0^00, resolving a long-standing open problem in quantum circuit complexity more than twenty years old. As a result, this proves QAC0⫋QACwf0{\rm QAC}^0 \subsetneqq {\rm QAC}_{\rm wf}^0QAC0⫋QACwf0​. We also show that any QAC circuit of depth ddd that approximately computes parity on nnn bits requires 2Ω~(n1/d)2^{\widetildeΩ(n^{1/d})}2Ω(n1/d) ancillary qubits, which is close to tight. This implies a similar lower bound on approximately preparing cat states using QAC circuits. Finally, we prove a quantum analog of the Linial-Mansour-Nisan theorem for QAC0^00. This implies that, for any QAC0^00 circuit UUU with a=poly(n)a={\rm poly}(n)a=poly(n) ancillary qubits, and for any x∈{0,1}nx\in\{0,1\}^nx∈{0,1}n, the correlation between Q(x)Q(x)Q(x) and the parity function is bounded by 1/2+2−Ω~(n1/d){1}/{2} + 2^{-\widetildeΩ(n^{1/d})}1/2+2−Ω(n1/d), where Q(x)Q(x)Q(x) denotes the output of measuring the output qubit of U∣x,0a⟩U|x,0^a\rangleU∣x,0a⟩. All the above consequences rely on the following technical result. If UUU is a QAC0^00 circuit with a=poly(n)a={\rm poly}(n)a=poly(n) ancillary qubits, then there is a distribution D\mathcal{D}D of bounded polynomials of degree polylog(n)(n)(n) such that with high probability, a random polynomial from D\mathcal{D}D approximates the function ⟨x,0a∣U†Zn+1U∣x,0a⟩\langle x,0^a| U^†Z_{n+1} U |x,0^a\rangle⟨x,0a∣U†Zn+1​U∣x,0a⟩ for a large fraction of x∈{0,1}nx\in \{0,1\}^nx∈{0,1}n. This result is analogous to the Razborov-Smolensky result on the approximation of AC0^00 circuits by random low-degree polynomials.
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.