The Structure of Circle Graph States

• URL: http://arxiv.org/abs/2603.08847v1
• Date: Mon, 09 Mar 2026 19:03:16 GMT
• Title: The Structure of Circle Graph States
• Abstract summary: Circle graph states are a structurally important family of graph states.<n>MBQC on circle graph states is actually efficiently classically simulable.<n>We show that the number of graph states LU-equivalent to a given graph state is $#mathsfP$-hard.
• Score: 0.06999740786886537
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Circle graph states are a structurally important family of graph states. The family's entanglement is a priori high enough to allow for universal measurement-based quantum computation (MBQC); however, MBQC on circle graph states is actually efficiently classically simulable. In this work, we paint a detailed picture of the local equivalence of circle graph states. First, we consider the class of all graph states that are local unitary (LU)-equivalent to circle graph states. In graph-theoretical terms, this LU-equivalence class is the set of all graphs reachable from the family of circle graphs by applying $r$-local complementations. We prove that the only graph states that are LU-equivalent to circle graph states are circle graph states themselves: circle graphs are closed under $r$-local complementation. Second, we show that bipartite circle graph states, i.e., 2-colorable circle graph states, are in one-to-one correspondence with planar code states, on which MBQC is known to be efficiently classically simulable. Leveraging this correspondence, we present alternative, simple proofs that (1) if a planar code state is LU-equivalent to a stabilizer state, they are in fact local Clifford (LC)-equivalent to it and that (2) MBQC on all circle graph states is efficiently classically simulable. Third and finally, we demonstrate that the problem of counting the number of graph states LU-equivalent to a given graph state is $\#\mathsf{P}$-hard.

Related papers

• Local Equivalences of Graph States [0.0]
  Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs.<n>It is crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations.<n>We prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence.
  arXiv  Detail & Related papers  (2025-11-27T09:49:57Z)
• Fermionic Insights into Measurement-Based Quantum Computation: Circle Graph States Are Not Universal Resources [5.552495672853301]
  Measurement-based quantum computation (MBQC) is a strong contender for realizing quantum computers.<n>A critical question for MBQC is the identification of resource graph states that can enable universal quantum computation.<n>We show that, in spite of their expressivity, circle graph states are not efficiently universal for MBQC.
  arXiv  Detail & Related papers  (2025-10-07T04:05:02Z)
• Strongly regular and strongly walk-regular graphs that admit perfect state transfer [0.0]
  We study perfect state transfer in Grover walks on two important classes of graphs: strongly regular graphs and strongly walk-regular graphs.<n>We first give a complete classification of strongly regular graphs that admit perfect state transfer. The only such graphs are the complete bipartite graph $K_2,2 and the complete graph $K_2,2,2.
  arXiv  Detail & Related papers  (2025-06-03T07:10:06Z)
• 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)
• A generalization of quantum pair state transfer [0.0]
  An $s$-pair state in a graph is a quantum state of the form $mathbfe_u+smathbfe_v$. We develop the theory of perfect $s$-pair state transfer in continuous quantum walks.
  arXiv  Detail & Related papers  (2024-04-25T14:45:49Z)
• A Graph is Worth $K$ Words: Euclideanizing Graph using Pure Transformer [47.25114679486907]
  We introduce GraphsGPT, featuring a Graph2Seq encoder that transforms Non-Euclidean graphs into learnable Graph Words. A GraphGPT decoder reconstructs the original graph from Graph Words to ensure information equivalence.
  arXiv  Detail & Related papers  (2024-02-04T12:29:40Z)
• MGNet: Learning Correspondences via Multiple Graphs [78.0117352211091]
  Learning correspondences aims to find correct correspondences from the initial correspondence set with an uneven correspondence distribution and a low inlier rate. Recent advances usually use graph neural networks (GNNs) to build a single type of graph or stack local graphs into the global one to complete the task. We propose MGNet to effectively combine multiple complementary graphs.
  arXiv  Detail & Related papers  (2024-01-10T07:58:44Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  Graphs with homophily-prone edges tend to connect nodes with the same class. Heterophily-prone edges tend to build relationships between nodes with different classes. Existing GNNs only take the original graph during training.
  arXiv  Detail & Related papers  (2023-06-13T08:06:10Z)
• Semi-Supervised Hierarchical Graph Classification [54.25165160435073]
  We study the node classification problem in the hierarchical graph where a 'node' is a graph instance. We propose the Hierarchical Graph Mutual Information (HGMI) and present a way to compute HGMI with theoretical guarantee. We demonstrate the effectiveness of this hierarchical graph modeling and the proposed SEAL-CI method on text and social network data.
  arXiv  Detail & Related papers  (2022-06-11T04:05:29Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• Topology-Aware Graph Pooling Networks [51.9008939769679]
  Pooling operations are effective on computer vision and natural language processing tasks. One challenge of performing pooling operations on graph data is the lack of locality that is not well-defined on graphs. We propose the topology-aware pooling (TAP) layer that explicitly considers graph topology.
  arXiv  Detail & Related papers  (2020-10-19T20:14:30Z)
• Graph model overview, events scales structure and chains of events [0.0]
  We present a graph model for a background independent, relational approach to spacetime. The graph coloring determines the graph structure in clusters of graph vertices (events) that can be monochromatic (homogeneous loops) or polychromatic (inhomogeneous loops) The emerging structure has self-similar characteristics on different scales (states)
  arXiv  Detail & Related papers  (2020-07-12T16:42:09Z)
• 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)

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.