Super-Constant Weight Dicke States in Constant Depth Without Fanout

1. Problem Statement

The paper addresses a fundamental question in quantum circuit complexity regarding the preparation of Dicke states in shallow (constant-depth) circuits.

• Dicke States: An $n$-qubit Dicke state of weight $k$, denoted $|D_n^k\rangle$, is the uniform superposition of all $n$-bit strings with Hamming weight $k$. These states are crucial resources for quantum metrology, Decoded Quantum Interferometry (DQI), and form a basis for the symmetric subspace.
• The Complexity Class: The authors focus on QAC$^0$, the quantum analogue of the classical AC$^0$ class. QAC$^0$ consists of constant-depth circuits with polynomial size, using multi-qubit Toffoli gates and single-qubit unitaries. Crucially, QAC$^0$ does not include the FANOUT gate (the ability to copy a classical bit to $n$ copies) by default.
• The Gap:
  • For constant weight $k = O(1)$, $|D_n^k\rangle$ can be prepared in QAC$^0$.
  • For super-constant weight $k = \omega(1)$ (e.g., $k = \text{polylog}(n)$), previous constant-depth constructions relied on the FANOUT$_n$ gate.
  • It was known that FANOUT$_k$ is necessary to prepare $|D_n^k\rangle$ (based on recent hardness results [GGJ26]), but it was unknown if FANOUT$_k$ was sufficient to construct these states in constant depth without resorting to the full FANOUT$_n$ gate.
  • Existing techniques for $k = \omega(1)$ either required deep circuits (logarithmic depth) or relied on FANOUT$_n$ to aggregate parallel amplification runs.

Core Question: Can $|D_n^k\rangle$ be prepared in constant depth using only FANOUT$_k$ (or no fanout if $k$ is small) for super-constant $k$?

2. Methodology and Key Techniques

The authors develop a novel construction that avoids the need for FANOUT$_n$ by utilizing a "bucketing" strategy combined with amplitude shaping and controlled state preparation.

A. The Bucketing Strategy (Approximation)

Instead of trying to generate the exact uniform superposition immediately, the authors first construct a state with constant fidelity to $|D_n^k\rangle$.

1. Partitioning: The $n$ qubits are divided into $\ell \approx k^3$ buckets, each of size $m = n/\ell$.
2. Occupancy Control: They prepare a Dicke state $|D_\ell^k\rangle$ on $\ell$ ancilla qubits, where each ancilla represents a bucket.
3. Expansion: If an ancilla (bucket) is in state $|1\rangle$, the corresponding $m$ target qubits are mapped to a specific state (initially a W-state $|W_m\rangle$). If $|0\rangle$, they map to $|0^m\rangle$.
4. Fidelity Argument: By the birthday paradox, if $\ell = \omega(k^2)$, the probability of two "1"s falling into the same bucket is negligible. Thus, the resulting state is a superposition of strings with weight $k$ where each bucket has at most one "1". This state has constant overlap with the true $|D_n^k\rangle$, but it misses strings where multiple 1s fall into the same bucket.

B. Correcting the Missing Strings (Generalization)

To achieve an exact state, the authors generalize the construction to handle cases where buckets contain multiple 1s (i.e., $j < k$ non-empty buckets).

1. Controlled Damped Binomial States: They introduce a new primitive state $|S_m^k\rangle$, a superposition of Dicke states $|D_m^j\rangle$ with specific weights $s(j)$ derived from a "damped binomial" distribution. This state allows a bucket to have more than one 1 with controlled probability.
2. Amplitude Rescaling: Using a new primitive (Lemma 4.1), they adjust the amplitudes of different branches (corresponding to different numbers of non-empty buckets $j$) to ensure that every string of weight $k$ in the final superposition has the exact same amplitude.
3. Post-Selection via Amplitude Amplification:
   • The construction produces a state of the form $\sqrt{\alpha} |D_n^k\rangle|1\rangle + \sqrt{1-\alpha} |\text{bad}\rangle|0\rangle$.
   • Crucially, they prove that the total mass $\alpha$ on the "good" (weight $k$) branch is constant ($\Theta(1)$), even though individual branches for specific $j$ might have vanishing mass.
   • They apply Grover's amplitude amplification (which is possible in QAC$^0$) to boost the amplitude of the weight-$k$ component to 1, yielding the exact $|D_n^k\rangle$.

C. Controlled Unitaries and Fanout Efficiency

• The authors construct controlled versions of these state preparations.
• They show that with access to FANOUT$_k$, they can implement controlled operations for circuits of size $\text{poly}(k)$ without blowing up the depth.
• This allows them to construct arbitrary superpositions of Dicke states (symmetric states) supported on weights up to $k$.

3. Key Contributions and Results

Main Theorem: Exact Preparation with Limited Fanout

Theorem 1.1: For any $n$ and $k \le n/2$, the state $|D_n^k\rangle$ can be exactly and cleanly prepared by a constant-depth circuit using FANOUT$_k$ gates (and poly$(n)$ ancillae).

• Implication: This closes the gap between the known lower bound (FANOUT$_k$ is necessary) and the upper bound (previously FANOUT$_n$ was required).
• Corollary 1.3 (Equivalence): $|D_n^k\rangle$ can be prepared in QAC$^0$ if and only if FANOUT$_k \in$ QAC$^0$. This provides a tight characterization of the complexity of Dicke state preparation.

Poly-Logarithmic Weight in Pure QAC$^0$

Corollary 1.2: For $k = \text{polylog}(n)$, since FANOUT$_k$ can be implemented in QAC$^0$ (using existing results), $|D_n^k\rangle$ can be prepared in pure QAC$^0$ (using only Toffoli and single-qubit gates) in constant depth.

• This is the first construction of super-constant weight Dicke states in constant depth without relying on the powerful FANOUT$_n$ gate.

Arbitrary Symmetric States

Theorem 1.4 / 5.12: The technique extends to arbitrary symmetric states (superpositions of Dicke states) supported on Hamming weights up to $k$.

• Any such state can be prepared in constant depth using QAC$^0$ with access to FANOUT$_k$.
• Corollary 1.5: Any symmetric state on $n$ qubits can be prepared in constant depth using FANOUT$_n$. This is the first $O(1)$-depth unitary construction for arbitrary symmetric states.

4. Significance and Impact

1. Complexity Theory Breakthrough: The paper establishes a precise equivalence between the power of the FANOUT gate and the ability to generate specific entangled resources (Dicke states). It proves that the "hardness" of preparing $|D_n^k\rangle$ is exactly equivalent to the hardness of FANOUT$_k$.
2. NISQ and Hardware Relevance:
   • Many quantum hardware platforms (e.g., trapped ions) support global entangling operations (effectively FANOUT$_n$) natively. The paper shows that these architectures can prepare any symmetric state in constant depth.
   • For architectures with limited connectivity, the result for $k=\text{polylog}(n)$ in pure QAC$^0$ suggests that shallow circuits can still generate complex entanglement structures without requiring global fanout, provided the weight is logarithmic.
3. New Primitive Techniques: The paper introduces new tools for constant-depth state synthesis, including:
   • Controlled state preparation using limited fanout.
   • Amplitude rescaling primitives for structured superpositions.
   • "Damped binomial" distributions to manage bucket collisions in superpositions.
4. Applications: Since Dicke states are central to Decoded Quantum Interferometry (DQI) and quantum metrology, this work enables the theoretical implementation of these protocols on shallow circuits, potentially making them more feasible for near-term devices.

In summary, the paper resolves a long-standing open problem by showing that the "super-constant" regime of Dicke state preparation does not inherently require the full power of FANOUT$_n$, but rather scales precisely with the weight $k$, and provides the first constant-depth construction for arbitrary symmetric states.