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

QAC0 Can Prepare Every Logarithmic-Qubit State

Lucas Gretta, Meghal Gupta, Malvika Raj Joshi

quant-phSubmitted Sep 15, 2026• Announced Sep 16, 2026• 2 citations
arXivHTMLPDF

Abstract

$\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.

AI Summary

Queued: an LLM will read the paper as soon as there is capacity.

Related papers

Polylogarithmic-Weight Dicke States in QAC$^0$ and Arbitrary Symmetric States in QAC$^0_f$

Lucas Gretta, Meghal Gupta, Malvika Raj Joshi

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. QAC$^0$, the quantum analogue of AC$^0$, minimally extends local $O(1)$-depth quantum circuits by allowing arbitrary-width Toffoli (reversible AND) gates. We show that Dicke states of $\mathrm{polylog}(n)$ weight can be prepared in QAC$^0$. This gives the first QAC$^0$ construction of any super-constant-weight $n$-qubit Dicke state, since previous constructions relied on the much more powerful FANOUT$_n$ gate. In general, we show that any weight-$k$ Dicke state can be constructed using FANOUT$_{\min(k,n-k)}$ gates. Combined with recent hardness results, this yields a tight characterization: for $k \leq n/2$, a $n$-qubit weight-$k$ Dicke state can be prepared in QAC$^0$ if and only if FANOUT$_k$ $\in$ QAC$^0$. We develop a limited-fanout state-synthesis toolkit for QAC$^0$ that yields further constant-depth, poly$(n)$-ancilla constructions: 1. Every $n$-qubit symmetric state supported on Hamming weight $\leq k$ can be prepared using FANOUT$_k$ gates. 2. Every $O(\log n)$-qubit state can be prepared using quantum random-access memory (QRAM$_n$), which refers to a coherent indexing gate. QRAM$_n$ is a potentially weaker resource than FANOUT$_n$ and can be implemented in QAC$^0_f$.

quant-pharXiv:2604.15298•Apr 17, 2026•5 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

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•1 citation

On the Computational Power of QAC0 with Barely Superlinear Ancillae

Anurag Anshu, Yangjing Dong, Fengning Ou +1 more

$\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$.

arXiv:2410.06499•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•19 citations

Constant-Depth Unitary Preparation of Dicke States

Malvika Raj Joshi, Francisca Vasconcelos

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 QAC$^0$ 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 QAC$_f^0$ 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.

quant-pharXiv:2601.10693•Jan 16, 2026•6 citations

Single-shot GHZ characterization with connectivity-aware fanout constructions

Giancarlo Gatti

We propose a practical recipe to transform any depth-$L$ block of CNOTs that prepares $n$-qubit GHZ states into an $n$-qubit fanout gate (multitarget-CNOT) of depth $2L-1$, without the need for ancilla qubits. Considering known logarithmic-depth circuits to prepare GHZ-states, this allows us to construct an $n$-qubit fanout gate with depth $2\log_2(n)-1$, reproducing previous ancillaless constructions. We employ our recipe to construct $n$-qubit fanout gates under heavy-hex connectivity restrictions, obtaining a depth of $O(n^{1/2})$, again reproducing previous complexity theory constructions. Using this recipe on the \textit{ibm\_fez} architecture yields a $156$-qubit fanout construction with depth $33$. Additionally, we show how to employ these $n$-qubit fanout constructions to measure complete sets of commuting observables from the $n$-body Pauli group with the same depth, allowing for efficient single-shot characterization of any GHZ-like state in a given known basis, e.g. fully characterizing a single copy of a $156$-qubit GHZ state using circuit depth $33$ in $\textit{ibm\_fez}$ (its preparation requires an additional depth of $17$).

quant-pharXiv:2602.11839•Feb 13, 2026•0 citations
QAC0\mathsf{QAC}^0QAC0 is the class of constant-depth poly(n)\mathrm{poly}(n)poly(n)-ancilla circuits obtained by extending QNC0\mathsf{QNC}^0QNC0, the class of local circuits, to include nonlocal interactions via arbitrary width Toffoli gates. It is believed to be weaker than its counterpart, QNCf0\mathsf{QNC}^0_fQNCf0​, obtained by including arbitrary-width FANOUT gates instead (QAC0⊆QNCf0\mathsf{QAC}^0 \subseteq \mathsf{QNC}^0_fQAC0⊆QNCf0​ [Moo99]).
In this note, we show that every O(log⁡n)O(\log n)O(logn)-qubit state can be exactly and cleanly prepared by a poly(n)\mathrm{poly}(n)poly(n)-ancilla QAC0\mathsf{QAC}^0QAC0 circuit. Previous known poly(n)\mathrm{poly}(n)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\mathsf{QAC}^0QAC0. Equivalently, prior constructions of arbitrary nnn-qubit states in QAC0\mathsf{QAC}^0QAC0 require doubly exponential size and we obtain an exponential factor improvement.
Polylogarithmic-Weight Dicke States in QAC0^00 and Arbitrary Symmetric States in QACf0^0_ff0​
An nnn-qubit Dicke state of weight kkk, is the uniform superposition over all nnn-bit strings of Hamming weight kkk. 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^00, the quantum analogue of AC0^00, minimally extends local O(1)O(1)O(1)-depth quantum circuits by allowing arbitrary-width Toffoli (reversible AND) gates. We show that Dicke states of polylog(n)\mathrm{polylog}(n)polylog(n) weight can be prepared in QAC0^00. This gives the first QAC0^00 construction of any super-constant-weight nnn-qubit Dicke state, since previous constructions relied on the much more powerful FANOUTn_nn​ gate. In general, we show that any weight-kkk Dicke state can be constructed using FANOUTmin⁡(k,n−k)_{\min(k,n-k)}min(k,n−k)​ gates. Combined with recent hardness results, this yields a tight characterization: for k≤n/2k \leq n/2k≤n/2, a nnn-qubit weight-kkk Dicke state can be prepared in QAC0^00 if and only if FANOUTk_kk​ ∈\in∈ QAC0^00. We develop a limited-fanout state-synthesis toolkit for QAC0^00 that yields further constant-depth, poly(n)(n)(n)-ancilla constructions: 1. Every nnn-qubit symmetric state supported on Hamming weight ≤k\leq k≤k can be prepared using FANOUTk_kk​ gates. 2. Every O(log⁡n)O(\log n)O(logn)-qubit state can be prepared using quantum random-access memory (QRAMn_nn​), which refers to a coherent indexing gate. QRAMn_nn​ is a potentially weaker resource than FANOUTn_nn​ and can be implemented in QACf0^0_ff0​.
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
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.
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.
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^00 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. WWW states), using only constant ancillae. Granted additional access to the quantum FAN-OUT operation (i.e. upgrading to the QACf0_f^0f0​ 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.
We propose a practical recipe to transform any depth-LLL block of CNOTs that prepares nnn-qubit GHZ states into an nnn-qubit fanout gate (multitarget-CNOT) of depth 2L−12L-12L−1, without the need for ancilla qubits. Considering known logarithmic-depth circuits to prepare GHZ-states, this allows us to construct an nnn-qubit fanout gate with depth 2log⁡2(n)−12\log_2(n)-12log2​(n)−1, reproducing previous ancillaless constructions. We employ our recipe to construct nnn-qubit fanout gates under heavy-hex connectivity restrictions, obtaining a depth of O(n1/2)O(n^{1/2})O(n1/2), again reproducing previous complexity theory constructions. Using this recipe on the \textit{ibm\_fez} architecture yields a 156156156-qubit fanout construction with depth 333333. Additionally, we show how to employ these nnn-qubit fanout constructions to measure complete sets of commuting observables from the nnn-body Pauli group with the same depth, allowing for efficient single-shot characterization of any GHZ-like state in a given known basis, e.g. fully characterizing a single copy of a 156156156-qubit GHZ state using circuit depth 333333 in ibm_fez\textit{ibm\_fez}ibm_fez (its preparation requires an additional depth of 171717).