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.
Quantum state preparation is a central primitive in many quantum algorithms, yet it is generally resource intensive, with efficient constructions known only for structured families of states. This work introduces a method for preparing quantum states whose amplitudes are given by a degree−d polynomial, using circuits with logarithmic depth in the number n of qubits and only O(n) ancilla qubits, improving previous approaches that required linear-depth circuits. The construction first relies on a block-encoding of an affine diagonal operator based on its Pauli-basis decomposition, which involves only n terms. A modified linear-combination-of-unitaries (LCU) technique is introduced to implement this decomposition in logarithmic depth, together with a novel circuit for the EXACT-one oracle that flags basis states in which exactly one qubit is in the state ∣1⟩. It then uses a generalized quantum eigenvalue transformation (GQET) to promote this affine operator to an arbitrary degree polynomial. Theoretical analysis and numerical simulations are reported along with a proof-of-principle implementation on a trapped-ion quantum processor using 14 qubits and more than 500 primitive quantum gates. Because polynomial approximations are ubiquitous in scientific computing, this construction provides a scalable and resource-efficient approach to quantum state preparation, further improving the potential of quantum algorithms in fields such as chemistry, physics, engineering, and finance.