Source-linked AI summary
Deterministic Preparation of Dicke States
Andreas Bärtschi, Stephan Eidenbenz
TL;DR
Preparing Dicke states is an important quantum-computing task, including as a starting point for combinatorial optimization. The paper presents a deterministic, ancilla-free circuit with linear depth and extends the construction to symmetric-state preparation and quantum compression.
Problem
Efficient quantum state preparation is a distinct research problem, and Dicke states are useful in quantum networking, metrology, and combinatorial optimization.
Method
The paper constructs a deterministic circuit that transforms an easily prepared computational-basis state into a Dicke state and leverages the construction inductively for broader symmetric-state preparation.
Results
The Dicke-state circuit uses O(kn) gates, depth O(n) independent of k, and no ancilla qubits; the bounds also hold for Linear Nearest Neighbor architectures.
Takeaways & Limitations
The construction extends to arbitrary symmetric pure states and, in reverse, provides quantum compression with quasilinear depth instead of quadratic depth.
Abstract
from arXiv · showhide
The Dicke state $|D_k^n\rangle$ is an equal-weight superposition of all $n$-qubit states with Hamming Weight $k$ (i.e. all strings of length $n$ with exactly $k$ ones over a binary alphabet). Dicke states are an important class of entangled quantum states that among other things serve as starting states for combinatorial optimization quantum algorithms. We present a deterministic quantum algorithm for the preparation of Dicke states. Implemented as a quantum circuit, our scheme uses $O(kn)$ gates, has depth $O(n)$ and needs no ancilla qubits. The inductive nature of our approach allows for linear-depth preparation of arbitrary symmetric pure states and -- used in reverse -- yields a quasilinear-depth circuit for efficient compression of quantum information in the form of symmetric pure states, improving on existing work requiring quadratic depth. All of these properties even hold for Linear Nearest Neighbor architectures.
1 Introduction
Dicke states are a useful class of entangled states, but efficient deterministic circuits for arbitrary Dicke-state preparation have received limited attention. The paper presents a circuit with linear depth, controlled gate count, no ancillas, and extensions to symmetric-state preparation and compression.
- Motivation: Efficient state preparation is a distinct research problem, and Dicke states are one important class admitting polynomial-time preparation algorithms.General arbitrary-state preparation can require Θ(2^n) gates, while Dicke states have structured support.
- Motivation: Dicke states are equal superpositions of n-qubit computational-basis states with fixed Hamming weight k.They have been studied in quantum networking, game theory, metrology, and combinatorial optimization.
- Contribution: The proposed deterministic circuit maps |0⟩^(n−k)|1⟩^k to |D_k^n⟩ without relying on probabilistic postselection.The input is itself an easily prepared computational-basis state and one term of the target superposition.
- Contribution: O(n) depth and O(kn) gates characterize the circuit, while prior approaches used probabilistic preparation, ancillas, or superlinear and quadratic resources.The paper identifies depth with runtime and gate count with overall resource needs.
- Extensions: The construction also supports Linear Nearest Neighbor architectures, arbitrary symmetric pure states, and compression into ⌈log(n + 1)⌉ qubits.Used in reverse, the circuit gives compression depth ˜O(n), compared with prior Θ(n^2) depth.
2 Deterministic Dicke State Preparation
The preparation scheme constructs unitaries U_n,k inductively from Split & Cyclic Shift unitaries and smaller preparation unitaries, mapping computational-basis inputs to Dicke states. The construction uses no ancillas and is deterministic, with explicit gate-level realizations of the required transformations.
- Inductive construction: U_n,k maps each input |0>^n−ℓ|1>^ℓ for ℓ≤k to the corresponding Dicke state |D_n^ℓ>.Requiring this property for all ℓ≤k enables the inductive construction.
- Split & Cyclic Shift: SCS_n,k acts on the last k+1 qubits, splitting each relevant input term into two components and cyclically shifting one component by one position.It acts trivially on the first n−k−1 qubits.
- Inductive construction: The inductive step builds U_n,k by applying SCS_n,k before U_n−1,k, with the base construction U_k,k formed from successive smaller unitaries.The composition is U_n,k = (U_n−1,k ⊗ Id) · SCS_n,k.
- Explicit construction: SCS_n,k is constructed from 1 two-qubit gate and k−1 three-qubit gates, each implementing one non-trivial mapping.The gates are controlled Y-rotations, with CNOT-conjugated constructions used for the three-qubit operations.
- Explicit construction: Applying the gates in increasing ℓ completes SCS_n,k because each relevant basis state is affected by exactly one matching gate.The resulting construction composes examples such as SCS_5,3, SCS_4,3, SCS_3,2, and SCS_2,1 into U_5,3.
3 Circuit Size and Depth
The circuit achieves linear depth while preserving favorable size bounds, including on Linear Nearest Neighbor architectures. Parallelizing compatible SCS operations and grouping them prevents the depth and gate count from becoming quadratic.
- Main bounds: O(min(k, n−k) · n) gates and O(n) depth suffice to prepare |D_n^k>, even on Linear Nearest Neighbor architectures.The theorem gives the symmetry between k and n−k explicitly in the size bound.
- Depth analysis: O(n) depth follows by parallelizing O(k) compatible three-qubit-gate stairs across the SCS unitaries.The total number of gates is O(kn), divided across k* ∈ O(k) parallelizable stairs.
- Gate count: At most 5kn+O(n) CNOT gates and 4kn+O(n) arbitrary-precision Ry gates compile the construction for arbitrary two-qubit gates.Each relevant three-qubit gate is implemented using 5 CNOTs and 4 Ry gates.
- LNN implementation: On LNN architectures, qubit sifting and grouped blocks of k consecutive SCS unitaries maintain O(kn) size and O(n) depth.Each group requires O(k^2) gates and O(k) depth, and there are ⌊n/k⌋−1 such groups plus a final group smaller than 2k.
4 Symmetric Pure States and Quantum Compression
The inductive Dicke-state circuit extends to arbitrary symmetric pure states and, in reverse, enables quasilinear-depth compression into logarithmically many qubits, including on Linear Nearest Neighbor architectures.
- Symmetric Pure States: Arbitrary superpositions are prepared by creating amplitudes and relative phases on computational-basis inputs, then applying unitary U_n,n.
- Symmetric Pure States: Every symmetric pure state can be expanded in the orthonormal Dicke-state basis of the (n + 1)-dimensional symmetric subspace.
- Symmetric Pure States: O(n^2) gates and O(n) depth suffice to prepare every symmetric pure n-qubit state, even on Linear Nearest Neighbor architectures.
- Quantum Compression: O(n^2) gates and quasilinear depth ˜O(n) compress every symmetric pure n-qubit state into ⌈log(n + 1)⌉ qubits, even on Linear Nearest Neighbor architectures.
- Quantum Compression: Compression reverses U_n,n, converts Dicke states to one-hot encodings, and maps those encodings to binary representations of their Hamming weights.
- Quantum Compression: The LNN compression implementation uses parallel qubit sifting, requiring O(n^2) gates but only O(n) depth for that movement.
5 Conclusions
The paper presents deterministic, linear-depth Dicke-state preparation and extends the construction to symmetric-state preparation and quantum compression. These bounds also hold for Linear Nearest Neighbor architectures, while characterizing polynomial-time preparable states remains open.
- Dicke states are prepared deterministically with depth O(n) and O(kn) gates in total.
- The bounds hold for Linear Nearest Neighbor architectures, and the circuit extends to arbitrary symmetric pure-state preparation and quantum compression.
- Characterizing the quantum states that can be prepared in polynomial time remains an open problem.
A Quantum Compression: Comparison with other Work
The paper compares its compression circuit with prior work by accumulating excited qubits into a contiguous block rather than counting them in a one-hot register. This mapping enables parallelization and reduces circuit depth from O(n^2) to O(n).
- Circuit mappings: The paper maps each Dicke state to |0⟩⊗n−ℓ|1⟩⊗ℓ, whereas prior work maps its Hamming weight to the one-hot state |0⟩⊗ℓ−1|1⟩|0⟩⊗n−ℓ.The two mappings differ in whether encountered excitations are accumulated at the bottom or counted in a one-hot encoding.
- Circuit mappings: The paper’s rounds scan qubits and accumulate encountered |1⟩ states, while existing work counts them in a one-hot register.After each round, the resulting states are equivalent up to a transformation on the first a qubits.
- Depth comparison: O(n) depth is achieved by pushing stair-shaped gates into one another, unlike the prior circuit’s wraparound gate of type (III).The type (III) gate prevents parallelization in the compared one-hot circuit, forcing sequential application of all gates.
- Depth comparison: O(n^2) depth results for the direct one-hot circuit because its gates must be applied sequentially.The comparison identifies gate structure, rather than the target Dicke state, as the source of the depth difference.
- Gate requirements: For a Dicke state |D_n^ℓ⟩, gates of type (III) are required through round a = n − ℓ + 1.This is the latest position where an excited state may be encountered for the first time.