W-state graphs: Structure and Algorithms
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909017687719936 |
|---|---|
| author | Gajjala, Rishikesh Ray, Saurabh Thilikos, Dimitrios M. |
| author_facet | Gajjala, Rishikesh Ray, Saurabh Thilikos, Dimitrios M. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_04855 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | W-state graphs: Structure and Algorithms Gajjala, Rishikesh Ray, Saurabh Thilikos, Dimitrios M. Quantum Physics Discrete Mathematics Combinatorics 68R05, 68W05, 05C70, 05C75, 05C85, 05C90 F.2.2 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. |
| title | W-state graphs: Structure and Algorithms |
| topic | Quantum Physics Discrete Mathematics Combinatorics 68R05, 68W05, 05C70, 05C75, 05C85, 05C90 F.2.2 |
| url | https://arxiv.org/abs/2605.04855 |