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.
AI Summary
The paper addresses the quantum-depth cost of preparing Dicke states and general permutation-symmetric states when measurements, classical feedforward, and ancillary qubits are available. It presents exact constant-depth adaptive protocols, trading quantum depth for ancillary space and, for the Dicke-state protocol, probabilistic success.
The starting primitive prepares a uniform superposition over subsets of size $k$ from an $n$-element set. This uses $O(k^2\log^2 n)$ ancillary qubits and succeeds with probability at least $1/k$. The primitive is then used to obtain an exact, probabilistic preparation of the Dicke state $\lvert D_{n,k}\rangle$ in constant quantum depth, with $O(n^2+k^2\log^2 n+kn\log n\log\log n)$ ancillary qubits. Parallel repetition makes the failure probability exponentially small without increasing quantum depth, at the cost of additional resources. The subset-superposition primitive also represents the uniform vertex state of a Johnson graph and appears in quantum-walk and topological-data-analysis algorithms.
For general symmetric states, the paper introduces a lifting framework that coherently combines clean unitary Dicke-state preparation circuits with polynomial ancillary overhead. Combining this framework with recent constant-depth unitary Dicke-state constructions gives exact constant-depth preparation of arbitrary $n$-qubit symmetric states using $O(n^3\sqrt{\log n})$ ancillary qubits.
The stated resource trade-offs are substantial ancillary overhead and reliance on adaptivity; the Dicke-state construction additionally has nonzero failure probability before repetition. The abstract does not specify gate-connectivity assumptions, classical feedforward costs, or detailed circuit constructions.
No sign of AI-generated textMissing comparison
Written by gpt-6.1-sol from the abstract only. Automated: it can be wrong.
Comments
19 pages, 2 figures, 4 tables. Comments are welcome!
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(k2log2n) ancillary qubits and success probability at least 1/k. This yields an exact, probabilistic, constant-depth Dicke-state preparation protocol using 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 n-qubit symmetric states using O(n3logn) ancillary qubits.
The paper addresses the quantum-depth cost of preparing Dicke states and general permutation-symmetric states when measurements, classical feedforward, and ancillary qubits are available. It presents exact constant-depth adaptive protocols, trading quantum depth for ancillary space and, for the Dicke-state protocol, probabilistic success.
The starting primitive prepares a uniform superposition over subsets of size k from an n-element set. This uses O(k2log2n) ancillary qubits and succeeds with probability at least 1/k. The primitive is then used to obtain an exact, probabilistic preparation of the Dicke state ∣Dn,k⟩ in constant quantum depth, with O(n2+k2log2n+knlognloglogn) ancillary qubits. Parallel repetition makes the failure probability exponentially small without increasing quantum depth, at the cost of additional resources. The subset-superposition primitive also represents the uniform vertex state of a Johnson graph and appears in quantum-walk and topological-data-analysis algorithms.
For general symmetric states, the paper introduces a lifting framework that coherently combines clean unitary Dicke-state preparation circuits with polynomial ancillary overhead. Combining this framework with recent constant-depth unitary Dicke-state constructions gives exact constant-depth preparation of arbitrary n-qubit symmetric states using O(n3logn) ancillary qubits.
The stated resource trade-offs are substantial ancillary overhead and reliance on adaptivity; the Dicke-state construction additionally has nonzero failure probability before repetition. The abstract does not specify gate-connectivity assumptions, classical feedforward costs, or detailed circuit constructions.
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 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 QACf0 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.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth.
We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential.
The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy.
Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension d and M≥d2−1 ports, we construct a unitary circuit of depth O(d), independent of M and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2. Thus, at fixed d, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on d can also be removed remains open.
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.
The n-qubit k-weight Dicke states ∣Dkn⟩, defined as the uniform superposition of all computational basis states with exactly k qubits in state ∣1⟩, form a basis of the symmetric subspace and represent an important class of entangled quantum states with broad applications in quantum computing. We propose deterministic quantum circuits for Dicke state preparation under two commonly seen qubit connectivity constraints: 1. All-to-all qubit connectivity: our circuit has depth O(log(k)log(n/k)+k), which improves the previous best bound of O(klog(n/k)). 2. Grid qubit connectivity ((n1×n2)-grid, n1≤n2): (a) For k≥n2/n1, we design a circuit with depth O(klog(n/k)+n2), surpassing the prior O(nk) bound. (b) For k<n2/n1, we design an optimal-depth circuit with depth O(n2). Furthermore, we establish the depth lower bounds of Ω(log(n)) for all-to-all qubit connectivity and Ω(n2) for (n1×n2)-grid connectivity constraints, demonstrating the near-optimality of our constructions.
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.
Adaptive quantum circuits, which combine local unitary gates, midcircuit measurements, and feedforward operations, have recently emerged as a promising avenue for efficient state preparation, particularly on near-term quantum devices limited to shallow-depth circuits. Matrix product states (MPS) comprise a significant class of many-body entangled states, efficiently describing the ground states of one-dimensional gapped local Hamiltonians and finding applications in a number of recent quantum algorithms. Recently, it has been shown that the Affleck-Kennedy-Lieb-Tasaki state—a paradigmatic example of an MPS—can be exactly prepared with an adaptive quantum circuit of constant depth, an impossible feat with local unitary gates alone due to its nonzero correlation length [Smith , PRX Quantum 4, 020315 (2023)]. In this work, we broaden the scope of this approach and demonstrate that a diverse class of MPS can be exactly prepared using constant-depth adaptive quantum circuits, outperforming theoretically optimal preparation with unitary circuits. We show that this class includes short- and long-ranged entangled MPS, symmetry-protected topological (SPT) and symmetry-broken states, MPS with finite Abelian, non-Abelian, and continuous symmetries, resource states for MBQC, and families of states with tunable correlation length. Moreover, we illustrate the utility of our framework for designing constant-depth sampling protocols, such as for random MPS or for generating MPS in a particular SPT phase. We present sufficient conditions for particular MPS to be preparable in constant time, with global on-site symmetry playing a pivotal role. Altogether, this work demonstrates the immense promise of adaptive quantum circuits for efficiently preparing many-body entangled states and provides explicit algorithms that outperform known protocols to prepare an essential class of states. Published by the American Physical Society 2024