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

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

Lucas Gretta, Meghal Gupta, Malvika Raj Joshi

quant-phcs.DSSubmitted Apr 16, 2026• Announced Apr 17, 2026• 0 citations• Revised Aug 25, 2026 (v3)
v1 · Apr 16, 2026v2 · Jul 13, 2026v3 · Aug 25, 2026
arXivHTMLPDF

Abstract

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

Related papers

QAC0 Can Prepare Every Logarithmic-Qubit State

Lucas Gretta, Meghal Gupta, Malvika Raj Joshi

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

quant-pharXiv:2609.17408•Sep 16, 2026•0 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•0 citations

Constant-depth adaptive preparation of Dicke and symmetric states

Rui Luo, Junjie Chen, Xiongfeng Ma

Efficient preparation of Dicke states and, more generally, permutation-symmetric states is important for quantum metrology, quantum networking, and collective quantum information processing. Measurements and classical feedforward enable low-depth preparations of these states, with a cost of ancillary qubits. In this work, we introduce an exact constant-depth adaptive preparation protocol for arbitrary Dicke-$(n,k)$ states and further symmetric states. We first provide a protocol preparing the uniform subset superposition state, as a primitive, using constant-depth adaptive circuit with $O(k^2\log^2 n)$ ancillary qubits and success probability at least $1/k$. This yields an exact, probabilistic, constant-depth Dicke-state preparation protocol using $O\left(n^2+k^2\log^2 n+kn\log n\log\log n\right)$ ancillary qubits. Parallel repetition suppresses the failure probability exponentially without increasing the quantum depth. Moreover, the uniform subset superposition state is also of independent interest as the uniform vertex state of the Johnson graph and as the compact uniform subset state appearing in quantum-walk and topological-data-analysis algorithms. We further establish a general lifting framework that coherently combines clean unitary Dicke-state preparation circuits to prepare arbitrary symmetric states with only polynomial ancillary overhead. Combined with recent constant-depth unitary Dicke-state constructions, this gives an exact constant-depth preparation protocol for arbitrary $n$-qubit symmetric states using $O(n^3\sqrt{\log n})$ ancillary qubits.

quant-pharXiv:2608.01144•Aug 4, 2026•0 citations

Short-Depth Circuits for Dicke State Preparation

Andreas Bärtschi, Stephan Eidenbenz

We present short-depth quantum circuits to deterministically prepare any Dicke state $\left| {D_k^n} \right\rangle $, which is the equal-amplitude superposition of all n-qubit computational basis states with Hamming Weight k. Dicke states are an important class of entangled quantum states with a large variety of applications, and a long history of experimental creation in physical systems. On the other hand, not much is known regarding efficient scalable quantum circuits for Dicke state preparation on realistic quantum computing hardware connectivities.Concretely, we present preparation circuits for Dicke states $\left| {D_k^n} \right\rangle $ with (i) depth of $\mathcal{O}\left( {k\log \frac{n}{k}} \right)$ for all-to-all connectivity (such as on current ion trap devices); (ii) depth of $\mathcal{O}\left( {k\surd \frac{n}{k}} \right) = \mathcal{O}(\sqrt {nk} )$ for Grid connectivity on grids of size $\Omega \left( {\surd \frac{n}{s}} \right) \times \mathcal{O}(\sqrt {ns} )$ with s ≤ k (such as on most current superconducting qubit devices).Both approaches have a total gate count of $\mathcal{O}(kn)$, need no ancilla qubits, and generalize to preparation and compression of those symmetric pure states, in which all non-zero amplitudes correspond to states with Hamming weight at most k. Our work significantly improves and expands previous state-of-the art circuits which had depth $\mathcal{O}(n)$ on a Linear Nearest Neighbor connectivity for arbitrary k (FCT 2019 [4]) and depth $\mathcal{O}(\log n)$ on all-to-all connectivity for k = 1 (AQT 2019 [9]).

arXiv:2207.09998•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•43 citations

Exact quantum Hamming-weight computation at optimal depth and minimum width

Wei Zi, Pei Yuan, Junhong Nie

Hamming-weight computation and symmetric Boolean functions are basic primitives for quantum arithmetic and state preparation, where circuit depth and qubit overhead matter. We construct an exact circuit computing the Hamming weight of an $n$-qubit register with depth $O(\log n)$ and size $O(n\log n)$, using only the $n$ input qubits and $m=\lceil\log_2(n+1)\rceil$ binary output qubits. The circuit uses arbitrary one-qubit gates and CNOTs with all-to-all connectivity. Both depth and total width are optimal. Our constructions combine tree structures and pipelining, temporarily using input qubits as workspace. We also give exact circuits for every symmetric Boolean function with the same depth and size bounds, using only $m$ ancillary qubits returned to zero. Finally, we apply the counter to exact preparation of balanced Dicke states for even $n$. With only $O(\log n)$ ancillary qubits, we obtain expected depth $O(\log^2 n)$ using measurements and classical feedforward, and depth $O(n^{1/4}\log n)$ using unitary gates alone.

quant-pharXiv:2610.25315•Oct 20, 2026•0 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
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​.
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.
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.
Efficient preparation of Dicke states and, more generally, permutation-symmetric states is important for quantum metrology, quantum networking, and collective quantum information processing. Measurements and classical feedforward enable low-depth preparations of these states, with a cost of ancillary qubits. In this work, we introduce an exact constant-depth adaptive preparation protocol for arbitrary Dicke-(n,k)(n,k)(n,k) states and further symmetric states. We first provide a protocol preparing the uniform subset superposition state, as a primitive, using constant-depth adaptive circuit with O(k2log⁡2n)O(k^2\log^2 n)O(k2log2n) ancillary qubits and success probability at least 1/k1/k1/k. This yields an exact, probabilistic, constant-depth Dicke-state preparation protocol using O(n2+k2log⁡2n+knlog⁡nlog⁡log⁡n)O\left(n^2+k^2\log^2 n+kn\log n\log\log n\right)O(n2+k2log2n+knlognloglogn) ancillary qubits. Parallel repetition suppresses the failure probability exponentially without increasing the quantum depth. Moreover, the uniform subset superposition state is also of independent interest as the uniform vertex state of the Johnson graph and as the compact uniform subset state appearing in quantum-walk and topological-data-analysis algorithms. We further establish a general lifting framework that coherently combines clean unitary Dicke-state preparation circuits to prepare arbitrary symmetric states with only polynomial ancillary overhead. Combined with recent constant-depth unitary Dicke-state constructions, this gives an exact constant-depth preparation protocol for arbitrary nnn-qubit symmetric states using O(n3log⁡n)O(n^3\sqrt{\log n})O(n3logn​) ancillary qubits.
We present short-depth quantum circuits to deterministically prepare any Dicke state $\left| {D_k^n} \right\rangle $, which is the equal-amplitude superposition of all n-qubit computational basis states with Hamming Weight k. Dicke states are an important class of entangled quantum states with a large variety of applications, and a long history of experimental creation in physical systems. On the other hand, not much is known regarding efficient scalable quantum circuits for Dicke state preparation on realistic quantum computing hardware connectivities.Concretely, we present preparation circuits for Dicke states $\left| {D_k^n} \right\rangle $ with (i) depth of O(klog⁡nk)\mathcal{O}\left( {k\log \frac{n}{k}} \right)O(klogkn​) for all-to-all connectivity (such as on current ion trap devices); (ii) depth of O(k√nk)=O(nk)\mathcal{O}\left( {k\surd \frac{n}{k}} \right) = \mathcal{O}(\sqrt {nk} )O(k√kn​)=O(nk​) for Grid connectivity on grids of size Ω(√ns)×O(ns)\Omega \left( {\surd \frac{n}{s}} \right) \times \mathcal{O}(\sqrt {ns} )Ω(√sn​)×O(ns​) with s ≤ k (such as on most current superconducting qubit devices).Both approaches have a total gate count of O(kn)\mathcal{O}(kn)O(kn), need no ancilla qubits, and generalize to preparation and compression of those symmetric pure states, in which all non-zero amplitudes correspond to states with Hamming weight at most k. Our work significantly improves and expands previous state-of-the art circuits which had depth O(n)\mathcal{O}(n)O(n) on a Linear Nearest Neighbor connectivity for arbitrary k (FCT 2019 [4]) and depth O(log⁡n)\mathcal{O}(\log n)O(logn) on all-to-all connectivity for k = 1 (AQT 2019 [9]).
Hamming-weight computation and symmetric Boolean functions are basic primitives for quantum arithmetic and state preparation, where circuit depth and qubit overhead matter. We construct an exact circuit computing the Hamming weight of an nnn-qubit register with depth O(log⁡n)O(\log n)O(logn) and size O(nlog⁡n)O(n\log n)O(nlogn), using only the nnn input qubits and m=⌈log⁡2(n+1)⌉m=\lceil\log_2(n+1)\rceilm=⌈log2​(n+1)⌉ binary output qubits. The circuit uses arbitrary one-qubit gates and CNOTs with all-to-all connectivity. Both depth and total width are optimal. Our constructions combine tree structures and pipelining, temporarily using input qubits as workspace. We also give exact circuits for every symmetric Boolean function with the same depth and size bounds, using only mmm ancillary qubits returned to zero. Finally, we apply the counter to exact preparation of balanced Dicke states for even nnn. With only O(log⁡n)O(\log n)O(logn) ancillary qubits, we obtain expected depth O(log⁡2n)O(\log^2 n)O(log2n) using measurements and classical feedforward, and depth O(n1/4log⁡n)O(n^{1/4}\log n)O(n1/4logn) using unitary gates alone.
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