quantum-computing

The Structure of Circle Graph States

arXiv Quantum Physics

4 min read

0 likes

⚡ Quantum Brief

Researchers proved circle graph states—though highly entangled—remain classically simulable for measurement-based quantum computation (MBQC), resolving a paradox where their structure suggests universal computational power but lacks practical quantum advantage. The study shows circle graphs are closed under r-local complementation, meaning only circle graph states are locally unitary (LU)-equivalent to other circle graphs, restricting their equivalence class to themselves. Bipartite circle graph states (2-colorable) were found to directly correspond with planar code states, enabling simpler proofs of classical simulability for both classes under MBQC protocols. The team demonstrated that if a planar code state is LU-equivalent to any stabilizer state, it must also be local Clifford (LC)-equivalent, tightening the relationship between these equivalence frameworks. Counting LU-equivalent graph states for any given graph was proven #P-hard, establishing fundamental computational limits for classifying quantum graph state equivalences.

Summarize this article with:

Quantum Physics arXiv:2603.08847 (quant-ph) [Submitted on 9 Mar 2026] Title:The Structure of Circle Graph States Authors:Frederik Hahn, Rose McCarty, Hendrik Poulsen Nautrup, Nathan Claudet View a PDF of the paper titled The Structure of Circle Graph States, by Frederik Hahn and 3 other authors View PDF HTML (experimental) 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. Comments: Subjects: Quantum Physics (quant-ph); Mathematical Physics (math-ph) Cite as: arXiv:2603.08847 [quant-ph] (or arXiv:2603.08847v1 [quant-ph] for this version) https://doi.org/10.48550/arXiv.2603.08847 Focus to learn more arXiv-issued DOI via DataCite (pending registration) Submission history From: Frederik Hahn [view email] [v1] Mon, 9 Mar 2026 19:03:16 UTC (457 KB) Full-text links: Access Paper: View a PDF of the paper titled The Structure of Circle Graph States, by Frederik Hahn and 3 other authorsView PDFHTML (experimental)TeX Source view license Current browse context: quant-ph new | recent | 2026-03 Change to browse by: math math-ph math.MP References & Citations INSPIRE HEP NASA ADSGoogle Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv (What is alphaXiv?) Links to Code Toggle CatalyzeX Code Finder for Papers (What is CatalyzeX?) DagsHub Toggle DagsHub (What is DagsHub?) GotitPub Toggle Gotit.pub (What is GotitPub?) Huggingface Toggle Hugging Face (What is Huggingface?) Links to Code Toggle Papers with Code (What is Papers with Code?) ScienceCast Toggle ScienceCast (What is ScienceCast?) Demos Demos Replicate Toggle Replicate (What is Replicate?) Spaces Toggle Hugging Face Spaces (What is Spaces?) Spaces Toggle TXYZ.AI (What is TXYZ.AI?) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower (What are Influence Flowers?) Core recommender toggle CORE Recommender (What is CORE?) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs. Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)

Read Original

Source Information

Source: arXiv Quantum Physics

Website: https://arxiv.org/rss/quant-ph