2026/04/16 by Lucas Gretta, Meghal Gupta, Malvika Raj Joshi · 1 voice · 2 citations
Physics and Astronomy · Computer Science · #quant-ph #cs.DS
arxiv published 2026/04/16 · arxiv updated 2026/07/13
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., 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(log n)-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 QAC0f.