W-state graphs: Structure and Algorithms

• URL: http://arxiv.org/abs/2605.04855v1
• Date: Wed, 06 May 2026 12:52:10 GMT
• Title: W-state graphs: Structure and Algorithms
• Abstract summary: We study the class of edge-coloured graphs arising from the graph-theoretic representation of quantum photonic experiments.<n>We introduce W-state graphs: matching-covered graphs equipped with a half-edge 2-colouring.<n>Our results place W-state graphs firmly within the classical matching theory and precisely delineate the structures capable of realizing idealized W-states.
• Score: 1.1763194962402104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• DiPhon: Diffusion on Graphons for Scalable Graph Generation [100.75398811422308]
  Diffusion models represent a leading paradigm for graph generation, with notable impact in domains such as molecular design.<n>We propose DiPhon, a discretized graph-level process that mimics these dynamics on finite graphs.<n>We prove that DiPhon matches exactly the first moment of the marginal distributions induced by the continuous graphon process, and approximates the second moment up to a closed-form discrepancy.
  arXiv  Detail & Related papers  (2026-07-08T10:15:17Z)
• Symmetric and Antisymmetric Quantum States from Graph Structure and Orientation [0.0]
  We prove that a graph state is fully symmetric under particle permutations if and only if the underlying graph is complete.<n>We show that complete directed graphs endowed with appropriate orientations, for an odd number of qudits generate fully antisymmetric multipartite states.
  arXiv  Detail & Related papers  (2026-01-27T18:12:52Z)
• Simultaneous variances of Pauli strings, weighted independence numbers, and a new kind of perfection of graphs [13.60873698530933]
  A graph that encodes its commutatitivity structure, i.e., by its frustration graph, provides a natural interface between graph theory and quantum information.<n>We call this class $hbar$-perfect, as it extends the class of perfect and $h$-perfect graphs.<n>We find efficient schemes for entanglement detection, a connection to the complexity of shadow tomography, tight uncertainty relations and a construction for computing good lower on ground state energies.
  arXiv  Detail & Related papers  (2025-11-17T16:05:28Z)
• Real state transfer on edge perturbed graphs with generalized clusters [0.0]
  We study the existence of real state transfer in edge-perturbed graphs containing generalized clusters.<n>A central observation is that the evolution of certain quantum states depends solely on the local structure of the underlying graph.
  arXiv  Detail & Related papers  (2025-05-12T18:26:59Z)
• Distinguishing Graph States by the Properties of Their Marginals [0.0]
  We study equivalence relations between graph states under local unitaries (LU)<n>We show that these invariants uniquely identify the entanglement classes of every graph state up to 8 qubits.<n>We generalize tools to test for local Clifford (LC) equivalence of graph states that work by condensing large graphs into smaller graphs.
  arXiv  Detail & Related papers  (2024-06-14T12:03:10Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning [65.1042892570989]
  We propose a contrastive graph matching network (CGMN) for self-supervised graph similarity learning. We employ two strategies, namely cross-view interaction and cross-graph interaction, for effective node representation learning. We transform node representations into graph-level representations via pooling operations for graph similarity computation.
  arXiv  Detail & Related papers  (2022-05-30T13:20:26Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2022-05-07T04:11:23Z)
• Residual2Vec: Debiasing graph embedding with random graphs [1.9280643035418397]
  We propose residual2vec, a general graph embedding method that can debias various structural biases in graphs by using random graphs. We demonstrate that this debiasing not only improves link prediction and clustering performance but also allows us to explicitly model salient structural properties in graph embedding.
  arXiv  Detail & Related papers  (2021-10-14T18:24:11Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  We introduce an unsupervised graph embedding that trades off local node similarity and connectivity, and global structure. The embedding is based on a generalized graph Laplacian, whose eigenvectors compactly capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2020-09-30T04:59:10Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version [27.544219236164764]
  Graph convolutional networks (GCNs) are a widely used method for graph representation learning. We investigate the power of GCNs to distinguish between different random graph models on the basis of the embeddings of their sample graphs.
  arXiv  Detail & Related papers  (2020-02-13T17:58:42Z)
• Bridging Knowledge Graphs to Generate Scene Graphs [49.69377653925448]
  We propose a novel graph-based neural network that iteratively propagates information between the two graphs, as well as within each of them. Our Graph Bridging Network, GB-Net, successively infers edges and nodes, allowing to simultaneously exploit and refine the rich, heterogeneous structure of the interconnected scene and commonsense graphs.
  arXiv  Detail & Related papers  (2020-01-07T23:35:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.