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

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\le 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 $\le 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${}_f^0$.