We present a divide-and-conquer approach to deterministically prepare Dicke states |Dkn> (i.e. equal-weight superpositions of all n-qubit states with Hamming Weight k) on quantum computers. In an experimental evaluation for up to n=6 qubits on IBM Quantum Sydney and Montreal devices, we achieve significantly higher state fidelity compared to previous results [Mukherjee et.al. TQE'2020, Cruz et.al. QuTe'2019]. The fidelity gains are achieved through several techniques: Our circuits first divide the Hamming weight between blocks of n/2 qubits, and then conquer those blocks with improved versions of Dicke state unitaries [Brtschi et.al. FCT'2019]. Due to the sparse connectivity on IBM's heavy-hex-architectures, these circuits are implemented for linear nearest neighbor topologies. Further gains in (estimating) the state fidelity are due to our use of measurement error mitigation and hardware progress.
We present a divide-and-conquer approach to deterministically prepare Dicke states |Dkn> (i.e. equal-weight superpositions of all n-qubit states with Hamming Weight k) on quantum computers. In an experimental evaluation for up to n=6 qubits on IBM Quantum Sydney and Montreal devices, we achieve significantly higher state fidelity compared to previous results [Mukherjee et.al. TQE'2020, Cruz et.al. QuTe'2019]. The fidelity gains are achieved through several techniques: Our circuits first divide the Hamming weight between blocks of n/2 qubits, and then conquer those blocks with improved versions of Dicke state unitaries [Brtschi et.al. FCT'2019]. Due to the sparse connectivity on IBM's heavy-hex-architectures, these circuits are implemented for linear nearest neighbor topologies. Further gains in (estimating) the state fidelity are due to our use of measurement error mitigation and hardware progress.
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(klogkn) for all-to-all connectivity (such as on current ion trap devices); (ii) depth of O(k√kn)=O(nk) for Grid connectivity on grids of size Ω(√sn)×O(ns) with s ≤ k (such as on most current superconducting qubit devices).Both approaches have a total gate count of 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) on a Linear Nearest Neighbor connectivity for arbitrary k (FCT 2019 [4]) and depth O(logn) on all-to-all connectivity for k = 1 (AQT 2019 [9]).
Efficient state preparation is a challenging and important problem in quantum computing. In this work, we present a recursive state preparation algorithm that combines logarithmic-depth Dicke state circuits with Hamming weight encoders for efficiently preparing ``leaf-separable" quantum states. The algorithm is built on binary partition trees, generalized weight distribution blocks (gWDBs), and leaf-level encoders. We evaluate the performance of the algorithm by numerically simulating it on randomly generated target states with between 4 and 15 qubits. Compared to general state preparation approaches which require O(2n) CX gates, our algorithm achieves a circuit depth of O(klogkn+2k) and uses O(n(k+2k)) two-qubit gates, where k<n denotes the subtree size. We also compare implementations of the algorithm with and without the use of ancilla qubits, providing a detailed analysis of the trade-offs in circuit depth and two-qubit gate counts. These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.
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(logn) and size O(nlogn), using only the n input qubits and m=⌈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 m ancillary qubits returned to zero. Finally, we apply the counter to exact preparation of balanced Dicke states for even n. With only O(logn) ancillary qubits, we obtain expected depth O(log2n) using measurements and classical feedforward, and depth O(n1/4logn) using unitary gates alone.
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.
Exact requirement of controlled NOT (CNOT) and single-qubit gates to implement a quantum algorithm in a given architecture is one of the central problems in this computational paradigm. In this article, we take a tutorial approach in explaining the preparation of Dicke states (|Dkn〉) using concise realizations of partially defined unitary transformations. We show how to efficiently implement the state-of-the-art deterministic Dicke state preparation circuits and in turn optimize them in terms of CNOT and single-qubit gate counts. We explain theoretical ideas in reducing the gate counts and observe how these improvements are reflected in actual implementation of the circuits. To emphasize the advantages, we describe the circuit for preparing |D24〉 on the “ibmqx2” machine of the IBM quantum experience (QX) service. Our approach shows that the error induced due to noise in the system is lesser in comparison to the existing works. We conclude by describing the CNOT map of the generic |Dkn〉 preparation circuit and analyze different ways of distributing the CNOT gates in the circuit and its effect on the induced error in the Noisy Intermediate Scale Quantum environment.