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:2411.00976

Low-degree approximation of QAC$^0$ circuits

Ashley Montanaro, Changpeng Shao, Dominic Verdon

Published Nov 1, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2411.00976

Related papers

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

Bounds on the $\mathrm{QAC}^0$ Complexity of Approximating Parity

Gregory Rosenthal

$\mathrm{QAC}$ circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. $\mathrm{QAC}^0$ circuits are $\mathrm{QAC}$ circuits of constant depth, and are quantum analogues of $\mathrm{AC}^0$ circuits. We prove the following: $\bullet$ For all $d \ge 7$ and $\varepsilon>0$ there is a depth-$d$ $\mathrm{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 $\mathrm{QAC}$ circuits of sublogarithmic depth could approximate parity regardless of size. $\bullet$ We introduce a class of $\mathrm{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 $\mathrm{QAC}$ circuits that approximate this component. $\bullet$ Arbitrary depth-$d$ $\mathrm{QAC}$ circuits require at least $\Omega(n/d)$ multi-qubit gates to achieve a $1/2 + \exp(-o(n/d))$ approximation of parity. When $d = \Theta(\log n)$ this nearly matches an easy $O(n)$ size upper bound for computing parity exactly. $\bullet$ $\mathrm{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\=okai.

•Aug 17, 2020•0 citations

Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated

Lucas Gretta, Meghal Gupta, Malvika Raj Joshi

A major open problem in understanding shallow quantum circuits (QAC$^0$) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC$^0$: any QAC$^0$ circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC$^0$. Thus, proving a quantum analog of the seminal LMN theorem for AC$^0$ is necessary to bound the quantum circuit complexity of PARITY. In the other direction, LMN does not fully capture the limitations of AC$^0$. For example, despite MAJORITY having $99\%$ of its weight on low-degree Fourier coefficients, no AC$^0$ circuit can non-trivially correlate with it. In contrast, we provide a QAC$^0$ circuit that achieves $(1-o(1))$ correlation with MAJORITY, establishing the first average-case decision separation between AC$^0$ and QAC$^0$. This suggests a uniquely quantum phenomenon: unlike in the classical setting, Fourier concentration may largely characterize the power of QAC$^0$. PARITY is also known to be equivalent in QAC$^0$ to inherently quantum tasks such as preparing GHZ states to high fidelity. We extend this equivalence to a broad class of state-synthesis tasks. We demonstrate that existing metrics such as trace distance, fidelity, and mutual information are insufficient to capture these states and introduce a new measure, felinity. We prove that preparing any state with non-negligible felinity, or derived states such as poly(n)-weight Dicke states, implies PARITY $\in$ QAC$^0$.

quant-pharXiv:2604.02793•Apr 6, 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 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.
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.
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\mathrm{QAC}^0QAC0 Complexity of Approximating Parity
QAC\mathrm{QAC}QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC0\mathrm{QAC}^0QAC0 circuits are QAC\mathrm{QAC}QAC circuits of constant depth, and are quantum analogues of AC0\mathrm{AC}^0AC0 circuits. We prove the following: ∙\bullet∙ For all d≥7d \ge 7d≥7 and ε>0\varepsilon>0ε>0 there is a depth-ddd QAC\mathrm{QAC}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\mathrm{QAC}QAC circuits of sublogarithmic depth could approximate parity regardless of size. ∙\bullet∙ We introduce a class of QAC\mathrm{QAC}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\mathrm{QAC}QAC circuits that approximate this component. ∙\bullet∙ Arbitrary depth-ddd QAC\mathrm{QAC}QAC circuits require at least Ω(n/d)\Omega(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 = \Theta(\log n)d=Θ(logn) this nearly matches an easy O(n)O(n)O(n) size upper bound for computing parity exactly. ∙\bullet∙ QAC\mathrm{QAC}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\=okai.
Parity ∉\notin∈/ QAC0   ⟺  \iff⟺ QAC0 is Fourier-Concentrated
A major open problem in understanding shallow quantum circuits (QAC0^00) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC0^00: any QAC0^00 circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC0^00. Thus, proving a quantum analog of the seminal LMN theorem for AC0^00 is necessary to bound the quantum circuit complexity of PARITY. In the other direction, LMN does not fully capture the limitations of AC0^00. For example, despite MAJORITY having 99%99\%99% of its weight on low-degree Fourier coefficients, no AC0^00 circuit can non-trivially correlate with it. In contrast, we provide a QAC0^00 circuit that achieves (1−o(1))(1-o(1))(1−o(1)) correlation with MAJORITY, establishing the first average-case decision separation between AC0^00 and QAC0^00. This suggests a uniquely quantum phenomenon: unlike in the classical setting, Fourier concentration may largely characterize the power of QAC0^00. PARITY is also known to be equivalent in QAC0^00 to inherently quantum tasks such as preparing GHZ states to high fidelity. We extend this equivalence to a broad class of state-synthesis tasks. We demonstrate that existing metrics such as trace distance, fidelity, and mutual information are insufficient to capture these states and introduce a new measure, felinity. We prove that preparing any state with non-negligible felinity, or derived states such as poly(n)-weight Dicke states, implies PARITY ∈\in∈ QAC0^00.
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.