$\mathsf{QAC}^0$ is the class of constant-depth $\mathrm{poly}(n)$-ancilla circuits obtained by extending $\mathsf{QNC}^0$, the class of local circuits, to include nonlocal interactions via arbitrary width Toffoli gates. It is believed to be weaker than its counterpart, $\mathsf{QNC}^0_f$, obtained by including arbitrary-width FANOUT gates instead ($\mathsf{QAC}^0 \subseteq \mathsf{QNC}^0_f$ [Moo99]).
In this note, we show that every $O(\log n)$-qubit state can be exactly and cleanly prepared by a $\mathrm{poly}(n)$-ancilla $\mathsf{QAC}^0$ circuit. Previous known $\mathrm{poly}(n)$-ancilla circuits for arbitrary such states are only known via additional access to either FANOUT or QRAM (indexing) gates [Ros21b, GGJ26b], neither of which are known to be in $\mathsf{QAC}^0$. Equivalently, prior constructions of arbitrary $n$-qubit states in $\mathsf{QAC}^0$ require doubly exponential size and we obtain an exponential factor improvement.
QAC0 is the class of constant-depth poly(n)-ancilla circuits obtained by extending QNC0, the class of local circuits, to include nonlocal interactions via arbitrary width Toffoli gates. It is believed to be weaker than its counterpart, QNCf0, obtained by including arbitrary-width FANOUT gates instead (QAC0⊆QNCf0 [Moo99]).
In this note, we show that every O(logn)-qubit state can be exactly and cleanly prepared by a poly(n)-ancilla QAC0 circuit. Previous known poly(n)-ancilla circuits for arbitrary such states are only known via additional access to either FANOUT or QRAM (indexing) gates [Ros21b, GGJ26b], neither of which are known to be in QAC0. Equivalently, prior constructions of arbitrary n-qubit states in QAC0 require doubly exponential size and we obtain an exponential factor improvement.
Polylogarithmic-Weight Dicke States in QAC0 and Arbitrary Symmetric States in QACf0
An n-qubit Dicke state of weight k, is the uniform superposition over all n-bit strings of Hamming weight k. Dicke states are central to quantum algorithms exhibiting speedups, such as Decoded Quantum Interferometry (Jordan et al., \emph{Nature}, 2025). In the NISQ era, quantum hardware is constrained by both depth and locality, motivating the question of which global operations suffice to prepare such states. QAC0, the quantum analogue of AC0, minimally extends local O(1)-depth quantum circuits by allowing arbitrary-width Toffoli (reversible AND) gates.
We show that Dicke states of polylog(n) weight can be prepared in QAC0. This gives the first QAC0 construction of any super-constant-weight n-qubit Dicke state, since previous constructions relied on the much more powerful FANOUTn gate. In general, we show that any weight-k Dicke state can be constructed using FANOUTmin(k,n−k) gates. Combined with recent hardness results, this yields a tight characterization: for k≤n/2, a n-qubit weight-k Dicke state can be prepared in QAC0 if and only if FANOUTk∈ QAC0. We develop a limited-fanout state-synthesis toolkit for QAC0 that yields further constant-depth, poly(n)-ancilla constructions:
1. Every n-qubit symmetric state supported on Hamming weight ≤k can be prepared using FANOUTk gates.
2. Every O(logn)-qubit state can be prepared using quantum random-access memory (QRAMn), which refers to a coherent indexing gate. QRAMn is a potentially weaker resource than FANOUTn and can be implemented in QACf0.
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 ε-approximates an arbitrary single-qubit gate using O(log1+δ(1/ε)) clean ancillae, Hadamard and T single-qubit gates, O(log(1/ε))-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(loglog(1/ε)), and we prove a matching Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(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-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∈/QAC0 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.
QAC0 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, along with the conjecture that QAC0 circuits can not compute PARITY. In this work we make progress on this longstanding conjecture: we show that any depth-dQAC0 circuit requires n1+3−d ancillae to compute a function with approximate degree Θ(n), which includes PARITY, MAJORITY and MODk. 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. Regarding PARITY, we show that any further improvement on the size of ancillae to n1+exp(−o(d)) would imply that PARITY ∈ QAC0. These lower bounds are derived by giving low-degree approximations to QAC0 circuits. We show that a depth-dQAC0 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 QLC0, corresponding to linear size QAC0 circuits, has approximate degree o(n). This is a quantum generalization of the result that LC0 circuits have approximate degree o(n) by Bun, Robin, and Thaler [SODA 2019]. Our result also implies that QLC0=NC1.
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
Dicke states serve as a critical resource in quantum metrology, communication, and computation. However, unitary preparation of Dicke states is limited to logarithmic depth in standard circuit models and existing constant-depth protocols require measurement and feed-forward. In this work, we present the first unitary, constant-depth protocols for exact Dicke state preparation. We overcome the logarithmic-depth barrier by moving beyond the standard circuit model and leveraging global interactions (native to architectures such as neutral atoms and trapped ions). Specifically, utilizing unbounded CZ gates (i.e. within the QAC0 circuit class), we offer circuits for exact computation of constant-weight Dicke states, using polynomial ancillae, and approximation of weight-1 Dicke states (i.e. W states), using only constant ancillae. Granted additional access to the quantum FAN-OUT operation (i.e. upgrading to the QACf0 circuit class), we also achieve exact and clean preparation of arbitrary-weight Dicke states, with polynomial ancillae. These protocols distinguish the constant-depth capabilities of quantum architectures based on connectivity and offer a novel path toward resolving a long-standing quantum complexity conjecture.
Bounds on the QAC0 Complexity of Approximating Parity
QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC0 circuits are QAC circuits of constant depth, and are quantum analogues of AC0 circuits. We prove the following:
∙ For all d≥7 and ε>0 there is a depth-dQAC circuit of size exp(poly(n1/d)log(n/ε)) that approximates the n-qubit parity function to within error ε on worst-case quantum inputs. Previously it was unknown whether QAC circuits of sublogarithmic depth could approximate parity regardless of size.
∙ We introduce a class of 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.
∙ Arbitrary depth-dQAC circuits require at least Ω(n/d) multi-qubit gates to achieve a 1/2+exp(−o(n/d)) approximation of parity. When d=Θ(logn) this nearly matches an easy O(n) size upper bound for computing parity exactly.
∙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.