arXiv:2609.22564

Generating Dicke State Graphs

Rebekah Herrman

quant-phmath.COSubmitted Sep 18, 2026• Announced Sep 22, 2026• 0 citations

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.

Related papers

W-state graphs: Structure and Algorithms

Rishikesh Gajjala, Saurabh Ray, Dimitrios M. Thilikos

quant-pharXiv:2605.04855May 7, 2026

Connectivity Bounds for GHZ Graphs

L. Sunil Chandran, Rishikesh Gajjala

quant-pharXiv:2610.22190Oct 16, 20260 citations

Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation

Pei Yuan, Shengyu Zhang

arXiv:2505.15413May 21, 20250 citations

Quantum experiments and graphs. III. High-dimensional and multiparticle entanglement

Xuemei Gu, Lijun Chen, Anton Zeilinger +1 more

arXiv:1812.09558Physical Review AMar 25, 201950 citations

Heralded Linear Optical Generation of Dicke States

Minhyeok Kang, Jaehee Kim, William J. Munro +2 more

quant-pharXiv:2512.20881New Journal of PhysicsDec 25, 20251 citation

Generation of Genuine Multipartite Entangled States via Indistinguishability of Identical Particles

Kobra Mahdavipour, Farzam Nosrati, Stefania Sciara +2 more

arXiv:2403.17171PRX QuantumDec 27, 20247 citations

arXiv:2609.22564

Generating Dicke State Graphs

Rebekah Herrman

quant-phmath.COSubmitted Sep 18, 2026• Announced Sep 22, 2026• 0 citations

arXiv HTML PDF

Abstract

|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.

Related papers

W-state graphs: Structure and Algorithms

Rishikesh Gajjala, Saurabh Ray, Dimitrios M. Thilikos

We study the class of edge-coloured graphs arising from the graph-theoretic representation of quantum photonic experiments that generate multipartite W-states. Abstracting away physical amplitudes and phases, we introduce W-state graphs: matching-covered graphs equipped with a half-edge 2-colouring such that every perfect matching contains exactly one bichromatic edge and every vertex is incident with a red half-edge. Our main contribution is a complete structural characterization of W-state graphs. We show that a graph is a W-state graph if and only if each of its 3-connected components is a W-cone, a simple and rigid building block defined by a universal vertex and a factor-critical base. This characterization implies that no W-state graph is simple and yields a recognition algorithm running as fast as verifying whether a graph is matching-covered. We also show that the natural generalization to Dicke states encounters a complexity barrier: verifying one of the two Dicke state conditions is itself coNP-complete, resolving an open problem of Vardi and Zhang [IJCAI 2023]. Our results place W-state graphs firmly within classical matching theory and precisely delineate the combinatorial structures capable of realizing idealized W-states in the experiment-graph framework.We study the class of edge-coloured graphs arising from the graph-theoretic representation of quantum photonic experiments that generate multipartite W-states. Abstracting away physical amplitudes and phases, we introduce W-state graphs: matching-covered graphs equipped with a half-edge 2-colouring such that every perfect matching contains exactly one bichromatic edge and every vertex is incident with a red half-edge. Our main contribution is a complete structural characterization of W-state graphs. We show that a graph is a W-state graph if and only if each of its 3-connected components is a W-cone, a simple and rigid building block defined by a universal vertex and a factor-critical base. This characterization implies that no W-state graph is simple and yields a recognition algorithm running as fast as verifying whether a graph is matching-covered. We also show that the natural generalization to Dicke states encounters a complexity barrier: verifying one of the two Dicke state conditions is itself coNP-complete, resolving an open problem of Vardi and Zhang [IJCAI 2023]. Our results place W-state graphs firmly within classical matching theory and precisely delineate the combinatorial structures capable of realizing idealized W-states in the experiment-graph framework.

quant-pharXiv:2605.04855May 7, 2026

Connectivity Bounds for GHZ Graphs

L. Sunil Chandran, Rishikesh Gajjala

Greenberger-Horne-Zeilinger (GHZ) states are multipartite entangled quantum states that play a central role in quantum information theory, with applications in quantum communication, cryptography, and distributed quantum computing. A major experimental goal is to create high-dimensional GHZ states using multiple entangled parties. Krenn, Gu and Zeilinger discovered a surprising bridge between these quantum-optical experiments and graph theory: certain photonic experiments can be represented by edge-coloured, edge-weighted graphs, and the dimension of the produced GHZ state equals the number of feasible monochromatic inherited vertex colourings. This led Krenn and Gu to conjecture that every GHZ graph with more than four vertices has dimension at most $2$ . A counterexample would give a new high-dimensional multipartite GHZ construction, while a proof would clarify fundamental resource limitations in quantum optics. It is known that the conjecture holds for graphs of vertex connectivity at most $2$ [MFCS 2024], and that simple GHZ graphs with $n>4$ vertices have dimension less than $n/\sqrt{2}$ [Quantum 2024]. However, no general upper bound depending only on vertex connectivity was known. We prove that every simple connected GHZ graph $G$ with at least four vertices has dimension at most $2^{κ(G)-1}+\binom{κ(G)}{2}$ , where $κ(G)$ is the vertex connectivity of $G$ . We also prove new bounds in terms of edge connectivity and maximum degree.Greenberger-Horne-Zeilinger (GHZ) states are multipartite entangled quantum states that play a central role in quantum information theory, with applications in quantum communication, cryptography, and distributed quantum computing. A major experimental goal is to create high-dimensional GHZ states using multiple entangled parties. Krenn, Gu and Zeilinger discovered a surprising bridge between these quantum-optical experiments and graph theory: certain photonic experiments can be represented by edge-coloured, edge-weighted graphs, and the dimension of the produced GHZ state equals the number of feasible monochromatic inherited vertex colourings. This led Krenn and Gu to conjecture that every GHZ graph with more than four vertices has dimension at most $2$. A counterexample would give a new high-dimensional multipartite GHZ construction, while a proof would clarify fundamental resource limitations in quantum optics. It is known that the conjecture holds for graphs of vertex connectivity at most $2$ [MFCS 2024], and that simple GHZ graphs with $n>4$ vertices have dimension less than $n/\sqrt{2}$ [Quantum 2024]. However, no general upper bound depending only on vertex connectivity was known. We prove that every simple connected GHZ graph $G$ with at least four vertices has dimension at most $2^{κ(G)-1}+\binom{κ(G)}{2}$, where $κ(G)$ is the vertex connectivity of $G$. We also prove new bounds in terms of edge connectivity and maximum degree.

quant-pharXiv:2610.22190Oct 16, 20260 citations

Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation

Pei Yuan, Shengyu Zhang

The $n$ -qubit $k$ -weight Dicke states $|D^n_k\rangle$ , defined as the uniform superposition of all computational basis states with exactly $k$ qubits in state $|1\rangle$ , 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(k\log(n/k))$ . 2. Grid qubit connectivity ( $(n_1\times n_2)$ -grid, $n_1\le n_2$ ): (a) For $k\ge n_2/n_1$ , we design a circuit with depth $O(k\log(n/k)+n_2)$ , surpassing the prior $O(\sqrt{nk})$ bound. (b) For $k< n_2/n_1$ , we design an optimal-depth circuit with depth $O(n_2)$ . Furthermore, we establish the depth lower bounds of $Ω(\log(n))$ for all-to-all qubit connectivity and $Ω(n_2)$ for $(n_1\times n_2)$ -grid connectivity constraints, demonstrating the near-optimality of our constructions.The $n$-qubit $k$-weight Dicke states $|D^n_k\rangle$, defined as the uniform superposition of all computational basis states with exactly $k$ qubits in state $|1\rangle$, 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(k\log(n/k))$. 2. Grid qubit connectivity ($(n_1\times n_2)$-grid, $n_1\le n_2$): (a) For $k\ge n_2/n_1$, we design a circuit with depth $O(k\log(n/k)+n_2)$, surpassing the prior $O(\sqrt{nk})$ bound. (b) For $k< n_2/n_1$, we design an optimal-depth circuit with depth $O(n_2)$. Furthermore, we establish the depth lower bounds of $Ω(\log(n))$ for all-to-all qubit connectivity and $Ω(n_2)$ for $(n_1\times n_2)$-grid connectivity constraints, demonstrating the near-optimality of our constructions.

arXiv:2505.15413May 21, 20250 citations

Quantum experiments and graphs. III. High-dimensional and multiparticle entanglement

Xuemei Gu, Lijun Chen, Anton Zeilinger +1 more

Quantum entanglement plays an important role in quantum information processes, such as quantum computation and quantum communication. Experiments in laboratories are unquestionably crucial to increase our understanding of quantum systems and inspire new insights into future applications. However, there are no general recipes for the creation of arbitrary quantum states with many particles entangled in high dimensions. Here we exploit a recent connection between quantum experiments and graph theory and answer this question for a plethora of classes of entangled states. We find experimental setups for Greenberger-Horne-Zeilinger states, $W$ states, general Dicke states, and asymmetrically high-dimensional multipartite entangled states. This result sheds light on the producibility of arbitrary quantum states using photonic technology with probabilistic pair sources and allows us to understand the underlying technological and fundamental properties of entanglement.Quantum entanglement plays an important role in quantum information processes, such as quantum computation and quantum communication. Experiments in laboratories are unquestionably crucial to increase our understanding of quantum systems and inspire new insights into future applications. However, there are no general recipes for the creation of arbitrary quantum states with many particles entangled in high dimensions. Here we exploit a recent connection between quantum experiments and graph theory and answer this question for a plethora of classes of entangled states. We find experimental setups for Greenberger-Horne-Zeilinger states, $W$ states, general Dicke states, and asymmetrically high-dimensional multipartite entangled states. This result sheds light on the producibility of arbitrary quantum states using photonic technology with probabilistic pair sources and allows us to understand the underlying technological and fundamental properties of entanglement.

arXiv:1812.09558Physical Review AMar 25, 201950 citations

Heralded Linear Optical Generation of Dicke States

Minhyeok Kang, Jaehee Kim, William J. Munro +2 more

Entanglement is a fundamental feature of quantum mechanics and a key resource for quantum information processing. Among multipartite entangled states, Dicke states $|D_n^k\rangle$ are distinguished by their permutation symmetry, which provides robustness against particle loss and enables applications for quantum communication and computation. Although Dicke states have been realized in various platforms, most optical implementations rely on postselection, which destroys the state upon detection and prevents its further use. A heralded optical scheme is therefore highly desirable. Here, we present a linear-optical heralded scheme for generating arbitrary Dicke states $|D_n^k\rangle$ with $3n+k$ photons through the framework of the linear quantum graph (LQG) picture. By mapping the scheme design into the graph-finding problem, and exploiting the permutation symmetry of Dicke states, we overcome the structural complexity that has hindered previous approaches. Our results provide a resource-efficient pathway toward practical heralded preparation of Dicke states for quantum technologies.Entanglement is a fundamental feature of quantum mechanics and a key resource for quantum information processing. Among multipartite entangled states, Dicke states $|D_n^k\rangle$ are distinguished by their permutation symmetry, which provides robustness against particle loss and enables applications for quantum communication and computation. Although Dicke states have been realized in various platforms, most optical implementations rely on postselection, which destroys the state upon detection and prevents its further use. A heralded optical scheme is therefore highly desirable. Here, we present a linear-optical heralded scheme for generating arbitrary Dicke states $|D_n^k\rangle$ with $3n+k$ photons through the framework of the linear quantum graph (LQG) picture. By mapping the scheme design into the graph-finding problem, and exploiting the permutation symmetry of Dicke states, we overcome the structural complexity that has hindered previous approaches. Our results provide a resource-efficient pathway toward practical heralded preparation of Dicke states for quantum technologies.

quant-pharXiv:2512.20881New Journal of PhysicsDec 25, 20251 citation

Generation of Genuine Multipartite Entangled States via Indistinguishability of Identical Particles

Kobra Mahdavipour, Farzam Nosrati, Stefania Sciara +2 more

Indistinguishability of identical particles is a resource for quantum information processing and has been utilized to generate entanglement from independent particles that spatially overlap only at the detection stage. Here, we introduce a controllable scheme capable of generating via three steps, i.e., initialization, deformation, and postselection, different classes of multipartite entangled states starting from a product state of N spatially distinguishable identical qubits. While our scheme is generalizable to any class of entangled bosonic and fermionic systems, we provide an explicit recipe for the generation of W , Dicke, GHZ, and cluster states, which are resource states for quantum information processing. Using graph-based representations within the framework of spatially localized operations and classical communication (sLOCC), we mathematically demonstrate a direct translation of the generation schemes of specific entangled states into colored, complex, and weighted digraphs, each corresponding to a given experimental setup. We also show that this graph-theoretical approach allows for the optimization of the generation efficiency of specific multipartite entangled states by exploring a variety of generation schemes. The presented theoretical approach, while already implementable with current linear optics architectures, has the potential to bring clear advantages over existing technologies, such as in quantum computing search algorithms and in the design of new experiments in quantum optics or other platforms. Published by the American Physical Society 2024Indistinguishability of identical particles is a resource for quantum information processing and has been utilized to generate entanglement from independent particles that spatially overlap only at the detection stage. Here, we introduce a controllable scheme capable of generating via three steps, i.e., initialization, deformation, and postselection, different classes of multipartite entangled states starting from a product state of N spatially distinguishable identical qubits. While our scheme is generalizable to any class of entangled bosonic and fermionic systems, we provide an explicit recipe for the generation of W , Dicke, GHZ, and cluster states, which are resource states for quantum information processing. Using graph-based representations within the framework of spatially localized operations and classical communication (sLOCC), we mathematically demonstrate a direct translation of the generation schemes of specific entangled states into colored, complex, and weighted digraphs, each corresponding to a given experimental setup. We also show that this graph-theoretical approach allows for the optimization of the generation efficiency of specific multipartite entangled states by exploring a variety of generation schemes. The presented theoretical approach, while already implementable with current linear optics architectures, has the potential to bring clear advantages over existing technologies, such as in quantum computing search algorithms and in the design of new experiments in quantum optics or other platforms. Published by the American Physical Society 2024

arXiv:2403.17171PRX QuantumDec 27, 20247 citations

|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.

2

. A counterexample would give a new high-dimensional multipartite GHZ construction, while a proof would clarify fundamental resource limitations in quantum optics. It is known that the conjecture holds for graphs of vertex connectivity at most

2

[MFCS 2024], and that simple GHZ graphs with

n>4

vertices have dimension less than

n/\sqrt{2}

[Quantum 2024]. However, no general upper bound depending only on vertex connectivity was known. We prove that every simple connected GHZ graph

G

with at least four vertices has dimension at most

2^{κ(G)-1}+\binom{κ(G)}{2}

, where

κ(G)

is the vertex connectivity of

G

. We also prove new bounds in terms of edge connectivity and maximum degree.

The

n

-qubit

k

-weight Dicke states

|D^n_k\rangle

, defined as the uniform superposition of all computational basis states with exactly

k

qubits in state

|1\rangle

, 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(k\log(n/k))

. 2. Grid qubit connectivity (

(n_1\times n_2)

-grid,

n_1\le n_2

): (a) For

k\ge n_2/n_1

, we design a circuit with depth

O(k\log(n/k)+n_2)

, surpassing the prior

O(\sqrt{nk})

bound. (b) For

k< n_2/n_1

, we design an optimal-depth circuit with depth

O(n_2)

. Furthermore, we establish the depth lower bounds of

Ω(\log(n))

for all-to-all qubit connectivity and

Ω(n_2)

for

(n_1\times n_2)

-grid connectivity constraints, demonstrating the near-optimality of our constructions.

W

states, general Dicke states, and asymmetrically high-dimensional multipartite entangled states. This result sheds light on the producibility of arbitrary quantum states using photonic technology with probabilistic pair sources and allows us to understand the underlying technological and fundamental properties of entanglement.

Entanglement is a fundamental feature of quantum mechanics and a key resource for quantum information processing. Among multipartite entangled states, Dicke states

|D_n^k\rangle

are distinguished by their permutation symmetry, which provides robustness against particle loss and enables applications for quantum communication and computation. Although Dicke states have been realized in various platforms, most optical implementations rely on postselection, which destroys the state upon detection and prevents its further use. A heralded optical scheme is therefore highly desirable. Here, we present a linear-optical heralded scheme for generating arbitrary Dicke states

|D_n^k\rangle

with

3n+k

photons through the framework of the linear quantum graph (LQG) picture. By mapping the scheme design into the graph-finding problem, and exploiting the permutation symmetry of Dicke states, we overcome the structural complexity that has hindered previous approaches. Our results provide a resource-efficient pathway toward practical heralded preparation of Dicke states for quantum technologies.