Mapping graph state orbits under local complementation

Jeremy C. Adcock; Sam Morley-Short; Axel Dahlberg; Joshua W. Silverstone

doi:10.22331/q-2020-08-07-305

Mapping graph state orbits under local complementation

Jeremy C. Adcock¹, Sam Morley-Short¹, Axel Dahlberg², and Joshua W. Silverstone¹

¹Quantum Engineering Technology (QET) Labs, H. H. Wills Physics Laboratory & Department of Electrical & Electronic Engineering, University of Bristol, Merchant Venturers Building, Woodland Road, Bristol BS8 1UB, UK
²QuTech - TU Delft, Lorentzweg 1, 2628CJ Delft, The Netherlands

Published:	2020-08-07, volume 4, page 305
Eprint:	arXiv:1910.03969v2
Doi:	https://doi.org/10.22331/q-2020-08-07-305
Citation:	Quantum 4, 305 (2020).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Graph states, and the entanglement they posses, are central to modern quantum computing and communications architectures. Local complementation – the graph operation that links all local-Clifford equivalent graph states – allows us to classify all stabiliser states by their entanglement. Here, we study the structure of the orbits generated by local complementation, mapping them up to 9 qubits and revealing a rich hidden structure. We provide programs to compute these orbits, along with our data for each of the $587$ orbits up to $9$ qubits and a means to visualise them. We find direct links between the connectivity of certain orbits with the entanglement properties of their component graph states. Furthermore, we observe the correlations between graph-theoretical orbit properties, such as diameter and colourability, with Schmidt measure and preparation complexity and suggest potential applications. It is well known that graph theory and quantum entanglement have strong interplay – our exploration deepens this relationship, providing new tools with which to probe the nature of entanglement.

Featured image: Local complementation produces complex orbits of locally equivalent graph states. Here we study these orbits and relate them to properties of their quantum states.

Popular summary

Graph states are ubiquitous representations of entanglement in quantum information science, and classify the most studied set of quantum states—clifford states—by the entanglement they possess.

However, many graph states are locally equivalent to one another, that is, they possess the same type of entanglement. Graph states which are locally equivalent can be transformed into one another by successive applications of the graph operation local complementation (example shown above). Using this operation, we can analyse only graph structure of the state, which is much simpler than analysing the exponentially large quantum state vector. This equivalence of graph states has been studied previously, with all graph states up to 12 qubits classified.

However, local complementation gives us more than sets of locally equivalent graphs: it also gives us an orbit (example shown above) which tells us how different graphs are related via local complementation. In this work we study these orbits, and relate their properties to properties of the entangled quantum states they contain. We find that orbit properties, such as colourability, correlate with entanglement properties, such as schmidt measure, and discuss applications of local complementation in quantum technology.

► BibTeX data

@article{Adcock2020mappinggraphstate,
  doi = {10.22331/q-2020-08-07-305},
  url = {https://doi.org/10.22331/q-2020-08-07-305},
  title = {Mapping graph state orbits under local complementation},
  author = {Adcock, Jeremy C. and Morley-Short, Sam and Dahlberg, Axel and Silverstone, Joshua W.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {305},
  month = aug,
  year = {2020}
}

► References

[1] Raussendorf, R. Measurement-based quantum computation with cluster states. International Journal of Quantum Information 7, 1053–1203 (2009).
https://doi.org/10.1103/PhysRevA.68.022312

[2] Veldhorst, M., Eenink, H., Yang, C. & Dzurak, A. Silicon cmos architecture for a spin-based quantum computer. Nature Communications 8, 1766 (2017).
https://doi.org/10.1038/s41467-017-01905-6

[3] Lekitsch, B. et al. Blueprint for a microwave trapped ion quantum computer. Science Advances 3, e1601540 (2017).
https://doi.org/10.1126/sciadv.1601540

[4] Alexander, R. N. et al. One-way quantum computing with arbitrarily large time-frequency continuous-variable cluster states from a single optical parametric oscillator. Physical Review A 94, 032327 (2016).
https://doi.org/10.1103/PhysRevA.94.032327

[5] Asavanant, W. et al. Time-domain multiplexed 2-dimensional cluster state: Universal quantum computing platform. Science366, 373-376 (2019).
https://doi.org/10.1126/science.aay2645

[6] Barends, R. et al. Superconducting quantum circuits at the surface code threshold for fault tolerance. Nature 508, 500 (2014).
https://doi.org/10.1038/nature13171

[7] Markham, D. & Sanders, B. C. Graph states for quantum secret sharing. Physical Review A 78, 042309 (2008).
https://doi.org/10.1103/PhysRevA.78.042309

[8] Ji, Z., Chen, J., Wei, Z. & Ying, M. The LU-LC conjecture is false. arXiv preprint arXiv:0709.1266 (2007).
arXiv:0709.1266

[9] Cabello, A., López-Tarrida, A. J., Moreno, P. & Portillo, J. R. Entanglement in eight-qubit graph states. Physics Letters A 373, 2219–2225 (2009).
https://doi.org/10.1016/j.physleta.2009.04.055

[10] Anders, S. & Briegel, H. J. Fast simulation of stabilizer circuits using a graph-state representation. Physical Review A 73, 022334 (2006).
https://doi.org/10.1103/PhysRevA.73.022334

[11] Hein, M., Eisert, J. & Briegel, H. J. Multiparty entanglement in graph states. Physical Review A 69, 062311 (2004).
https://doi.org/10.1103/PhysRevA.69.062311

[12] Van den Nest, M., Dehaene, J. & De Moor, B. Graphical description of the action of local Clifford transformations on graph states. Physical Review A 69, 022316 (2004).
https://doi.org/10.1103/PhysRevA.69.022316

[13] Hein, M. et al. Multiparty entanglement in graph states. arXiv preprint quant-ph/0602096 (2006).
arXiv:quant-ph/0602096

[14] Dahlberg, A. & Wehner, S. Transforming graph states using single-qubit operations. Phil. Trans. R. Soc. A 376, 20170325 (2018).
https://doi.org/10.1098/rsta.2017.0325

[15] Dahlberg, A., Helsen, J. & Wehner, S. The complexity of the vertex-minor problem. arXiv preprint arXiv:1906.05689 (2019).
arXiv:1906.05689

[16] Danielsen, L. E. & Parker, M. G. On the classification of all self-dual additive codes over GF(4) of length up to 12. Journal of Combinatorial Theory, Series A 113, 1351–1367 (2006).
https://doi.org/10.1016/j.jcta.2005.12.004

[17] Cabello, A., Danielsen, L. E., Lopez-Tarrida, A. J. & Portillo, J. R. Optimal preparation of graph states. Physical Review A 83, 042314 (2011).
https://doi.org/10.1103/PhysRevA.83.042314

[18] Bouchet, A. An efficient algorithm to recognize locally equivalent graphs. Combinatorica 11, 315–329 (1991).
https://doi.org/10.1007/BF01275668

[19] Van den Nest, M., Dehaene, J. & De Moor, B. Efficient algorithm to recognize the local clifford equivalence of graph states. Physical Review A 70, 034302 (2004).
https://doi.org/10.1103/PhysRevA.70.034302

[20] Dahlberg, A., Helsen, J. & Wehner, S. How to transform graph states using single-qubit operations: computational complexity and algorithms. arXiv preprint arXiv:1805.05306 (2018).
arXiv:1805.05306

[21] Van den Nest, M., Dür, W., Vidal, G. & Briegel, H. Classical simulation versus universality in measurement-based quantum computation. Physical Review A 75, 012337 (2007).
https://doi.org/10.1103/PhysRevA.75.012337

[22] Dahlberg, A., Helsen, J. & Wehner, S. Counting single-qubit clifford equivalent graph states is #p-complete. arXiv preprint arXiv:1907.08024 (2019).
https://doi.org/10.1063/1.5120591
arXiv:1907.08024

[23] Adcock, J. C., Morley-Short, S., Silverstone, J. W. & Thompson, M. G. Hard limits on the postselectability of optical graph states. Quantum Science and Technology 4, 015010 (2019).
https://doi.org/10.1088/2058-9565/aae950

[24] Morley-Short, S., Graph state compass (2018).
https://doi.org/10.5281/zenodo.3692712

[25] Data and code to accompany this manuscript: (2020).
https://doi.org/10.5281/zenodo.3757948

[26] Rokicki, T., Kociemba, H., Davidson, M. & Dethridge, J. The diameter of the Rubik's cube group is twenty. SIAM Review 56, 645–670 (2014).
https://doi.org/10.1137/120867366

[27] McKay, B. D. & Piperno, A. Practical graph isomorphism II. Journal of Symbolic Computation 60, 94–112 (2014).
https://doi.org/10.1016/j.jsc.2013.09.003

[28] Eisert, J. & Briegel, H. J. Schmidt measure as a tool for quantifying multiparticle entanglement. Physical Review A 64, 022306 (2001).
https://doi.org/10.1103/PhysRevA.64.022306

[29] Schlingemann, D. & Werner, R.F. Quantum error-correcting codes associated with graphs. Physical Review A 65, 012308 (2001).
https://doi.org/10.1103/PhysRevA.65.012308

[30] Dür, W., Aschauer, H. & Briegel, H.-J Multiparticle entanglement purification for graph states. Physical review letters 91, 107903 (2003).
https://doi.org/10.1103/PhysRevLett.91.107903

[31] Erdős, P. & Rényi, A. Asymmetric graphs. Acta Mathematica Hungarica 14, 295–315 (1963).
https://doi.org/10.1007/BF01895716

[32] Oum, S.-I. Computing rank-width exactly. Information Processing Letters 109, 745–748 (2009).
https://doi.org/10.1016/j.ipl.2009.03.018

[33] SageMath, The Sage Mathematics Software System. (2020).
https://doi.org/10.5281/zenodo.820864

[34] Csárdi, G. & Nepusz, T., The igraph software package for complex network research. InterJournal Complex Systems, 1695, (2006).
https://doi.org/10.5281/zenodo.3709419

[35] Horvát, S., IGraph/M. (2016).
https://doi.org/10.5281/zenodo.3739056

[36] Hahn, F., Pappa, A. & Eisert, J. Quantum network routing and local complementation. NPJ Quantum Information 5.1, 5-7 (2019).
https://doi.org/10.1038/s41534-019-0191-6

[37] Joo, J. & Feder, D. L. Edge local complementation for logical cluster states. New Journal of Physics 13, 063025 (2011).
https://doi.org/10.1088/1367-2630/13/6/063025

[38] Zwerger, M., Dür, W. & Briegel, H. Measurement-based quantum repeaters. Physical Review A 85, 062326 (2012).
https://doi.org/10.1103/PhysRevA.85.062326

[39] Gimeno-Segovia, M., Shadbolt, P., Browne, D. E. & Rudolph, T. From three-photon Greenberger-Horne-Zeilinger states to ballistic universal quantum computation. Physical Review Letters 115, 020502 (2015).
https://doi.org/10.1103/PhysRevLett.115.020502

[40] Morley-Short, S. et al. Physical-depth architectural requirements for generating universal photonic cluster states. Quantum Science and Technology 3, 015005 (2017).
https://doi.org/10.1088/2058-9565/aa913b

[41] Rudolph, T. Physical-depth architectural requirements for generating universal photonic cluster states. APL Photonics 2, 030901 (2017).
https://doi.org/10.1063/1.4976737

[42] Morley-Short, S., Gimeno-Segovia, M., Rudolph, T. & Cable, H. Physical-depth architectural requirements for generating universal photonic cluster states. Quantum Science and Technology (2018).
https://doi.org/10.1088/2058-9565/aaf6c4

Cited by

[1] Fei Shi, Lin Chen, Giulio Chiribella, and Qi Zhao, "Entanglement Detection Length of Multipartite Quantum States", Physical Review Letters 134 5, 050201 (2025).

[2] Sitong Liu, Naphan Benchasattabuse, Darcy QC Morgan, Michal Hajdušek, Simon J. Devitt, and Rodney Van Meter, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 870 (2023) ISBN:979-8-3503-4323-6.

[3] Tobias Meuser, Jannis Weil, Aninda Lahiri, and Marius Paraschiv, "RELiQ: Scalable Entanglement Routing via Reinforcement Learning in Quantum Networks", IEEE Transactions on Communications 74, 1860 (2026).

[4] Sergey Bravyi, Yash Sharma, Mario Szegedy, and Ronald de Wolf, "Generating k EPR-pairs from an n-party resource state", Quantum 8, 1348 (2024).

[5] Adam Burchardt and Frederik Hahn, "The Foliage Partition: An Easy-to-Compute LC-Invariant for Graph States", Quantum 9, 1720 (2025).

[6] Madhav Krishnan Vijayan, Alexandru Paler, Jason Gavriel, Casey R Myers, Peter P Rohde, and Simon J Devitt, "Compilation of algorithm-specific graph states for quantum circuits", Quantum Science and Technology 9 2, 025005 (2024).

[7] Thierry N Kaldenbach and Matthias Heller, "Mapping quantum circuits to shallow-depth measurement patterns based on graph states", Quantum Science and Technology 10 1, 015010 (2025).

[8] Tristan Cam, Cyril Gavoille, Yvan Le Borgne, and Simon Martiel, Lecture Notes in Computer Science 15716, 54 (2025) ISBN:978-3-031-97062-7.

[9] Soh Kumabe, Ryuhei Mori, and Yusei Yoshimura, "Complexity of graph-state preparation by Clifford circuits", Quantum 10, 2165 (2026).

[10] Derek Zhang, "Bell pair extraction using graph foliage techniques", Journal of Mathematical Physics 66 2, 022204 (2025).

[11] Hitendra Kumar, Kumud Singh Porte, and R. B. Sandeep, Lecture Notes in Computer Science 16587, 400 (2026) ISBN:978-3-032-27731-2.

[12] Nirupam Basak and Goutam Paul, "Improved Routing of Multiparty Entanglement over Quantum Networks", ACM Transactions on Quantum Computing 7 3, 1 (2026).

[13] Sobhan Ghanbari, Jie Lin, Benjamin MacLellan, Luc Robichaud, Piotr Roztocki, and Hoi-Kwong Lo, "Optimization of deterministic photonic-graph-state generation via local operations", Physical Review A 110 5, 052605 (2024).

[14] Thomas J. Bell, Love A. Pettersson, and Stefano Paesani, "Optimizing Graph Codes for Measurement-Based Loss Tolerance", PRX Quantum 4 2, 020328 (2023).

[15] Jorge L. Perez-Ramos, Selene Ramirez-Rosales, Daniel Canton-Enriquez, Luis A. Diaz-Jimenez, Gabriela Xicotencatl-Ramirez, Ana M. Herrera-Navarro, and Hugo Jimenez-Hernandez, "Algorithm Based on Morphological Operators for Shortness Path Planning", Algorithms 17 5, 184 (2024).

[16] Piotr Mitosek, "Pauli Flow on Open Graphs with Unknown Measurement Labels", Electronic Proceedings in Theoretical Computer Science 406, 117 (2024).

[17] Mushkan Sureka and Saikat Guha, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 188 (2024) ISBN:979-8-3315-4137-8.

[18] Zheng-Hao Liu, Springer Theses 79 (2023) ISBN:978-981-99-6166-5.

[19] Konstantinos-Rafail Revis, Hrachya Zakaryan, and Zahra Raissi, " χ-colorable graph states: closed-form expressions and quantum orthogonal arrays", Journal of Physics A: Mathematical and Theoretical 58 35, 355301 (2025).

[20] Marcin Płodzień, Maciej Lewenstein, and Jan Chwedeńczuk, "Many-body quantum resources of graph states", Reports on Progress in Physics 88 7, 077601 (2025).

[21] Louis Schatzki, Linjian Ma, Edgar Solomonik, and Eric Chitambar, "Tensor rank and other multipartite entanglement measures of graph states", Physical Review A 110 3, 032409 (2024).

[22] Matthias C. Löbl, Love A. Pettersson, Stefano Paesani, and Anders S. Sørensen, "Transforming graph states via Bell state measurements", Quantum 9, 1795 (2025).

[23] Luise Prielinger, Kenneth Goodenough, Guus Avis, Stefan Krastanov, Don Towsley, and Gayane Vardoyan, "Piecemaker: A Resource-Efficient Entanglement Distribution Protocol", IEEE Journal on Selected Areas in Communications 44, 5341 (2026).

[24] Johannes Nokkala, Jyrki Piilo, and Ginestra Bianconi, "Complex quantum networks: a topical review", Journal of Physics A: Mathematical and Theoretical 57 23, 233001 (2024).

[25] Zheng-Hao Liu, Jie Zhou, Hui-Xian Meng, Mu Yang, Qiang Li, Yu Meng, Hong-Yi Su, Jing-Ling Chen, Kai Sun, Jin-Shi Xu, Chuan-Feng Li, and Guang-Can Guo, "Experimental test of the Greenberger–Horne–Zeilinger-type paradoxes in and beyond graph states", npj Quantum Information 7 1, 66 (2021).

[26] Matthias C. Löbl, Love A. Pettersson, Andrew Jena, Luca Dellantonio, Stefano Paesani, and Anders S. Sørensen, "Generating graph states with a single quantum emitter and the minimum number of fusions", Physical Review A 111 5, 052604 (2025).

[27] Love A. Pettersson, Anders S. Sørensen, and Stefano Paesani, "Deterministic Generation of Concatenated Graph Codes from Quantum Emitters", PRX Quantum 6 1, 010305 (2025).

[28] Hemant Sharma, Kenneth Goodenough, Johannes Borregaard, Filip Rozpędek, and Jonas Helsen, "Minimising the number of edges in LC-equivalent graph states", Quantum 10, 2001 (2026).

[29] Gerard Anglès Munné, Valentin Kasper, and Felix Huber, "Engineering holography with stabilizer graph codes", npj Quantum Information 10 1, 48 (2024).

[30] Alexander Pickston, Joseph Ho, Andrés Ulibarrena, Federico Grasselli, Massimiliano Proietti, Christopher L. Morrison, Peter Barrow, Francesco Graffitti, and Alessandro Fedrizzi, "Conference key agreement in a quantum network", npj Quantum Information 9 1, 82 (2023).

[31] Carlo Cafaro, "Geometric graph-theoretic aspects of quantum stabilizer codes", Physica Scripta 97 7, 075105 (2022).

[32] Zipeng Wu, Song Cheng, and Bei Zeng, "Efficient construction of stabilizer codes via ZX-calculus", Academia Quantum 3 2(2026).

[33] Anna Schroeder, Matthias Heller, and Mariami Gachechiladze, "Deterministic Ansätze for the measurement-based variational quantum eigensolver", New Journal of Physics 26 6, 063019 (2024).

[34] Vaisakh Mannalath and Anirban Pathak, "Multiparty entanglement routing in quantum networks", Physical Review A 108 6, 062614 (2023).

[35] Matthias C. Löbl, Stefano Paesani, and Anders S. Sørensen, "Loss-tolerant architecture for quantum computing with quantum emitters", Quantum 8, 1302 (2024).

[36] Sebastiano Corli and Enrico Prati, 2022 IEEE International Conference on Rebooting Computing (ICRC) 1 (2022) ISBN:979-8-3503-4709-8.

[37] Evangelia Takou, Edwin Barnes, and Sophia E. Economou, "Optimization complexity and resource minimization of emitter-based photonic graph state generation protocols", npj Quantum Information 11 1, 108 (2025).

[38] Matthias C. Löbl, Stefano Paesani, and Anders S. Sørensen, "Efficient percolation simulations for lossy photonic fusion networks", Physical Review Research 6 3, 033273 (2024).

[39] Zipeng Wu, Song Cheng, and Bei Zeng, "A ZX-Calculus Approach for the Construction of Graph Codes", arXiv:2304.08363, (2023).

[40] Andrey Boris Khesin, "Quantum Computing from Graphs", arXiv:2501.17959, (2025).

[41] Nathan Claudet, Mehdi Mhalla, and Simon Perdrix, "Small k-pairable states", arXiv:2309.09956, (2023).

[42] Victor V. Albert and Philippe Faist, "Handbook of Error-Correcting Codes", arXiv:2606.11484, (2026).

[43] Thierry N. Kaldenbach, Isaac D. Smith, Hendrik Poulsen Nautrup, Matthias Heller, and Hans J. Briegel, "Efficient Preparation of Resource States for Hamiltonian Simulation and Universal Quantum Computation", arXiv:2509.05404, (2025).

[44] Konstantinos-Rafail Revis, Hrachya Zakaryan, and Zahra Raissi, "Orbit classification and analysis of qutrit graph states under local complementation and local scaling", arXiv:2506.05478, (2025).

[45] Nathan Claudet, "Local Equivalences of Graph States", arXiv:2511.22271, (2025).

[46] Sitong Liu, Naphan Benchasattabuse, Darcy QC Morgan, Michal Hajdušek, Simon J. Devitt, and Rodney Van Meter, "A Substrate Scheduler for Compiling Arbitrary Fault-tolerant Graph States", arXiv:2306.03758, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-17 19:58:05) and SAO/NASA ADS (last updated successfully 2026-08-17 19:58:06). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.