Mapping graph state orbits under local complementation

Jeremy C. Adcock1, Sam Morley-Short1, Axel Dahlberg2, and Joshua W. Silverstone1

1Quantum 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
2QuTech - TU Delft, Lorentzweg 1, 2628CJ Delft, The Netherlands

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


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.

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

► References

[1] Raussendorf, R. Measurement-based quantum computation with cluster states. International Journal of Quantum Information 7, 1053–1203 (2009).

[2] Veldhorst, M., Eenink, H., Yang, C. & Dzurak, A. Silicon cmos architecture for a spin-based quantum computer. Nature Communications 8, 1766 (2017).

[3] Lekitsch, B. et al. Blueprint for a microwave trapped ion quantum computer. Science Advances 3, e1601540 (2017).

[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).

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

[6] Barends, R. et al. Superconducting quantum circuits at the surface code threshold for fault tolerance. Nature 508, 500 (2014).

[7] Markham, D. & Sanders, B. C. Graph states for quantum secret sharing. Physical Review A 78, 042309 (2008).

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

[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).

[10] Anders, S. & Briegel, H. J. Fast simulation of stabilizer circuits using a graph-state representation. Physical Review A 73, 022334 (2006).

[11] Hein, M., Eisert, J. & Briegel, H. J. Multiparty entanglement in graph states. Physical Review A 69, 062311 (2004).

[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).

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

[14] Dahlberg, A. & Wehner, S. Transforming graph states using single-qubit operations. Phil. Trans. R. Soc. A 376, 20170325 (2018).

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

[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).

[17] Cabello, A., Danielsen, L. E., Lopez-Tarrida, A. J. & Portillo, J. R. Optimal preparation of graph states. Physical Review A 83, 042314 (2011).

[18] Bouchet, A. An efficient algorithm to recognize locally equivalent graphs. Combinatorica 11, 315–329 (1991).

[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).

[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).

[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).

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

[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).

[24] Morley-Short, S., Graph state compass (2018).

[25] Data and code to accompany this manuscript: (2020).

[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).

[27] McKay, B. D. & Piperno, A. Practical graph isomorphism II. Journal of Symbolic Computation 60, 94–112 (2014).

[28] Eisert, J. & Briegel, H. J. Schmidt measure as a tool for quantifying multiparticle entanglement. Physical Review A 64, 022306 (2001).

[29] Schlingemann, D. & Werner, R.F. Quantum error-correcting codes associated with graphs. Physical Review A 65, 012308 (2001).

[30] Dür, W., Aschauer, H. & Briegel, H.-J Multiparticle entanglement purification for graph states. Physical review letters 91, 107903 (2003).

[31] Erdős, P. & Rényi, A. Asymmetric graphs. Acta Mathematica Hungarica 14, 295–315 (1963).

[32] Oum, S.-I. Computing rank-width exactly. Information Processing Letters 109, 745–748 (2009).

[33] SageMath, The Sage Mathematics Software System. (2020).

[34] Csárdi, G. & Nepusz, T., The igraph software package for complex network research. InterJournal Complex Systems, 1695, (2006).

[35] Horvát, S., IGraph/​M. (2016).

[36] Hahn, F., Pappa, A. & Eisert, J. Quantum network routing and local complementation. NPJ Quantum Information 5.1, 5-7 (2019).

[37] Joo, J. & Feder, D. L. Edge local complementation for logical cluster states. New Journal of Physics 13, 063025 (2011).

[38] Zwerger, M., Dür, W. & Briegel, H. Measurement-based quantum repeaters. Physical Review A 85, 062326 (2012).

[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).

[40] Morley-Short, S. et al. Physical-depth architectural requirements for generating universal photonic cluster states. Quantum Science and Technology 3, 015005 (2017).

[41] Rudolph, T. Physical-depth architectural requirements for generating universal photonic cluster states. APL Photonics 2, 030901 (2017).

[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).

Cited by

[1] 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).

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

[3] 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.

[4] 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).

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

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

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

[8] 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).

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

[10] Anna Schroeder, Matthias Heller, and Mariami Gachechiladze, "Deterministic Ansätze for the Measurement-based Variational Quantum Eigensolver", arXiv:2312.13241, (2023).

[11] 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).

[12] Louis Schatzki, Linjian Ma, Edgar Solomonik, and Eric Chitambar, "Tensor Rank and Other Multipartite Entanglement Measures of Graph States", arXiv:2209.06320, (2022).

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

The above citations are from Crossref's cited-by service (last updated successfully 2024-02-26 07:40:42) and SAO/NASA ADS (last updated successfully 2024-02-26 07:40:43). The list may be incomplete as not all publishers provide suitable and complete citation data.