arXiv:2609.22564
Generating Dicke State Graphs
Rebekah Herrman
Abstract
Graph theory is a powerful tool in quantum computing, with applications ranging from quantum circuit synthesis and optimization to entanglement mapping. Recent work has shown how one can use edge-colored graphs to model photonic experiments that generate GHZ and W states. However, the latter work also proved that verifying that a graph models a Dicke state experiment is coNP-complete. In this work, we provide families of graphs that generate $|D_{k}^a\rangle \otimes |0\rangle^{\otimes b }$, where $b = |a-2k|$ is the number of spectator modes. The graph setup consists of a doubled complete subgraph on $a$ vertices and a collection of auxiliary vertices. We prove that every coincidence carries exactly $k$ excitations, every weight-$k$ computational basis state on bitstrings of length $a$ is realized, and each of those bitstrings is realized exactly $(n/2)!$ times, where $n = a+b$. Since verifying the Dicke FORALL condition is coNP-complete in general, constructing explicit families that provably generate Dicke states is of interest.
AI Summary
The paper addresses explicit preparation of Dicke states in the edge-colored graph model of postselected photonic experiments, where vertices represent optical paths, edges represent pair-emission sources, and perfect matchings contribute computational-basis amplitudes. Although checking the Dicke FORALL condition is coNP-complete in general, it constructs a family whose support and equal amplitudes can be proved directly. For any $a\geq1$ and $0\leq k\leq a$, the construction generates $|D_k^a\rangle\otimes|0\rangle^{\otimes b}$ with $b=|a-2k|$ spectator paths. It uses $n=2\max(k,a-k)$ total paths and $a(a-1)+ab$ sources. The signal subgraph is a doubled complete graph, with opposite single-excitation orientations on parallel edges. Spectators connect to every signal vertex through sources emitting either no excitation or one excitation into the signal arm. The proof decomposes each perfect matching into an injection from spectators to signal vertices and a matching on the remaining core. Excitation counting fixes the output weight at $k$; a bijection count shows that every weight-$k$ signal pattern occurs exactly $(n/2)!$ times. The total number of matchings is $a!/\min(k,a-k)!$. For $k\geq a/2$, the construction saturates the bound $n\geq2k$ for sources emitting at most one excitation per pair. Below half filling it need not be mode-optimal; existing W-state constructions use fewer paths. Reducing the source count and characterizing other suitable graphs remain open. A doubled $K_{3,3}$ example shows that vertex- and edge-transitivity alone do not ensure uniform amplitudes.
The author used Claude Opus 5 to verify the FORALL Dicke state condition for sample graphs, write preliminary drafts of the mathematical statements, and to generate Tikz code.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.