Transforming graph states to Bell-pairs is NP-Complete

Axel Dahlberg; Jonas Helsen; Stephanie Wehner

doi:10.22331/q-2020-10-22-348

Transforming graph states to Bell-pairs is NP-Complete

Axel Dahlberg, Jonas Helsen, and Stephanie Wehner

QuTech - TU Delft, Lorentzweg 1, 2628CJ Delft, The Netherlands

Published:	2020-10-22, volume 4, page 348
Eprint:	arXiv:1907.08019v2
Doi:	https://doi.org/10.22331/q-2020-10-22-348
Citation:	Quantum 4, 348 (2020).

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

Abstract

Critical to the construction of large scale quantum networks, i.e. a quantum internet, is the development of fast algorithms for managing entanglement present in the network. One fundamental building block for a quantum internet is the distribution of Bell pairs between distant nodes in the network. Here we focus on the problem of transforming multipartite entangled states into the tensor product of bipartite Bell pairs between specific nodes using only a certain class of local operations and classical communication. In particular we study the problem of deciding whether a given graph state, and in general a stabilizer state, can be transformed into a set of Bell pairs on specific vertices using only single-qubit Clifford operations, single-qubit Pauli measurements and classical communication. We prove that this problem is ${\mathbb{NP}}$-Complete.

► BibTeX data

@article{Dahlberg2020transforminggraph,
  doi = {10.22331/q-2020-10-22-348},
  url = {https://doi.org/10.22331/q-2020-10-22-348},
  title = {Transforming graph states to {B}ell-pairs is {NP}-{C}omplete},
  author = {Dahlberg, Axel and Helsen, Jonas and Wehner, Stephanie},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {348},
  month = oct,
  year = {2020}
}

► References

[1] Stephanie Wehner, David Elkouss, and Ronald Hanson. Quantum internet: A vision for the road ahead. Science, 362 (6412): eaam9288, Oct 2018. ISSN 0036-8075. 10.1126/science.aam9288. URL http://www.sciencemag.org/lookup/doi/10.1126/ science.aam9288.
https://doi.org/10.1126/science.aam9288
http://www.sciencemag.org/lookup/doi/10.1126/%20%20science.aam9288

[2] Mihir Pant, Hari Krovi, Don Towsley, Leandros Tassiulas, Liang Jiang, Prithwish Basu, Dirk Englund, and Saikat Guha. Routing entanglement in the quantum internet. npj Quantum Information, 5 (1): 25, 2019a. 10.1038/s41534-019-0139-x.
https://doi.org/10.1038/s41534-019-0139-x

[3] Mihir Pant, Don Towsley, Dirk Englund, and Saikat Guha. Percolation thresholds for photonic quantum computing. Nature Communications, 10 (1): 1070, 2019b. ISSN 2041-1723. 10.1038/s41467-019-08948-x.
https://doi.org/10.1038/s41467-019-08948-x

[4] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 10th anniversary edition edition, 2010. ISBN 9780511976667. 10.1017/CBO9780511976667. URL http://ebooks.cambridge.org/ref/id/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667
http://ebooks.cambridge.org/ref/id/CBO9780511976667

[5] Takaaki Matsuo, Takahiko Satoh, Shota Nagayama, and Rodney Van Meter. Analysis of measurement-based quantum network coding over repeater networks under noisy conditions. Physical Review A, 97: 13, 10 2017. 10.1103/PhysRevA.97.062328.
https://doi.org/10.1103/PhysRevA.97.062328

[6] N. Kalb, A. A. Reiserer, P. C. Humphreys, J. J. W. Bakermans, S. J. Kamerling, N. H. Nickerson, S. C. Benjamin, D. J. Twitchen, M. Markham, and R. Hanson. Entanglement distillation between solid-state quantum network nodes. Science, 356 (6341): 928–932, jun 2017. ISSN 0036-8075. 10.1126/science.aan0070. URL http://www.sciencemag.org/lookup/doi/10.1126/ science.aan0070.
https://doi.org/10.1126/science.aan0070
http://www.sciencemag.org/lookup/doi/10.1126/%20%20science.aan0070

[7] H. Bombin and M. A. Martin-Delgado. Exact topological quantum order in $d=3$ and beyond: Branyons and brane-net condensates. Phys. Rev. B, 75: 075103, Feb 2007. 10.1103/PhysRevB.75.075103. URL https://link.aps.org/doi/10.1103/PhysRevB.75.075103.
https://doi.org/10.1103/PhysRevB.75.075103

[8] Héctor Bombín. Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes. New Journal of Physics, 17 (8): 083002, aug 2015. 10.1088/1367-2630/17/8/083002. URL https://doi.org/10.1088.
https://doi.org/10.1088/1367-2630/17/8/083002

[9] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M Van den Nest, H. J. Briegel, M. Van den Nest, and H. J. Briegel. Entanglement in Graph States and its Applications. Quantum Computers, Algorithms and Chaos, pages 1–99, 2006. ISSN 1050-2947. 10.3254/978-1-61499-018-5-115. URL http://arxiv.org/abs/quant-ph/0602096.
https://doi.org/10.3254/978-1-61499-018-5-115
arXiv:quant-ph/0602096

[10] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. Graphical description of the action of local clifford transformations on graph states. Physical Review A, 69 (2): 022316, 2004. 10.1103/PhysRevA.69.022316.
https://doi.org/10.1103/PhysRevA.69.022316

[11] Axel Dahlberg and Stephanie Wehner. Transforming graph states using single-qubit operations. Phil. Trans. R. Soc. A 376, One contribution of 15 to a discussion meeting issue 'Foundations of quantum mechanics and their impact on contemporary society', 2018. 10.1098/rsta.2017.0325.
https://doi.org/10.1098/rsta.2017.0325

[12] Axel Dahlberg, Jonas Helsen, and Stephanie Wehner. How to transform graph states using single-qubit operations: computational complexity and algorithms. Quantum Science and Technology, 5 (4): 045016, sep 2020. 10.1088/2058-9565/aba763.
https://doi.org/10.1088/2058-9565/aba763

[13] F. Hahn, A. Pappa, and J. Eisert. Quantum network routing and local complementation. npj Quantum Information, 5 (1): 76, Sep 2019. ISSN 2056-6387. 10.1038/s41534-019-0191-6.
https://doi.org/10.1038/s41534-019-0191-6

[14] Axel Dahlberg, Jonas Helsen, and Stephanie Wehner. The complexity of the vertex-minor problem. arXiv preprint arXiv:1906.05689, 2019.
arXiv:1906.05689

[15] Hans J. Briegel and Robert Raussendorf. Persistent entanglement in arrays of interacting particles. Phys. Rev. Lett., 86: 910–913, Jan 2001. 10.1103/PhysRevLett.86.910. URL https://link.aps.org/doi/10.1103/PhysRevLett.86.910.
https://doi.org/10.1103/PhysRevLett.86.910

[16] Robert Raussendorf and Hans J. Briegel. A one-way quantum computer. Phys. Rev. Lett., 86: 5188–5191, May 2001. 10.1103/PhysRevLett.86.5188. URL https://link.aps.org/doi/10.1103/PhysRevLett.86.5188.
https://doi.org/10.1103/PhysRevLett.86.5188

[17] André Bouchet. An efficient algorithm to recognize locally equivalent graphs. Combinatorica, 11 (4): 315–329, 1991. ISSN 0209-9683. 10.1007/BF01275668. URL http://link.springer.com/10.1007/BF01275668.
https://doi.org/10.1007/BF01275668

[18] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. Efficient algorithm to recognize the local Clifford equivalence of graph states. Physical Review A, 70 (3): 034302, 2004. ISSN 1050-2947. 10.1103/PhysRevA.70.034302. URL https://link.aps.org/doi/10.1103/PhysRevA.70.034302.
https://doi.org/10.1103/PhysRevA.70.034302

[19] Sang Il Oum. Rank-width and vertex-minors. Journal of Combinatorial Theory. Series B, 95 (1): 79–100, 2005. ISSN 00958956. 10.1016/j.jctb.2005.03.003.
https://doi.org/10.1016/j.jctb.2005.03.003

[20] Bruno Courcelle and Sang il Oum. Vertex-minors, monadic second-order logic, and a conjecture by Seese. Journal of Combinatorial Theory. Series B, 97 (1): 91–126, 2007. ISSN 00958956. 10.1016/j.jctb.2006.04.003.
https://doi.org/10.1016/j.jctb.2006.04.003

[21] Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic: A Language Theoretic Approach. Cambridge University Press, New York, NY, USA, 1st edition, 2011. 10.1017/CBO9780511977619.
https://doi.org/10.1017/CBO9780511977619

[22] M. Van den Nest, W. Dür, G. Vidal, and H. J. Briegel. Classical simulation versus universality in measurement-based quantum computation. Physical Review A, 75 (1): 012337, 2007. ISSN 1050-2947. 10.1103/PhysRevA.75.012337. URL https://link.aps.org/doi/10.1103/PhysRevA.75.012337.
https://doi.org/10.1103/PhysRevA.75.012337

[23] Alexander Langer, Felix Reidl, Peter Rossmanith, and Somnath Sikdar. Practical algorithms for mso model-checking on tree-decomposable graphs. Comput. Sci. Rev., 13 (C): 39–74, November 2014. ISSN 1574-0137. 10.1016/j.cosrev.2014.08.001. URL http://dx.doi.org/10.1016/j.cosrev.2014.08.001.
https://doi.org/10.1016/j.cosrev.2014.08.001

[24] Bernardo Martin, Angel Sanchez, Cesar Beltran-Royo, and Abraham Duarte. Solving the edge-disjoint paths problem using a two-stage method. International Transactions in Operational Research, 27 (1): 435–457, 2020. 10.1111/itor.12544. URL https://onlinelibrary.wiley.com/doi/abs/10.1111/itor.12544.
https://doi.org/10.1111/itor.12544

[25] André Bouchet. Graphic presentations of isotropic systems. Journal of Combinatorial Theory, Series B, 45 (1): 58–76, 1988. ISSN 10960902. 10.1016/0095-8956(88)90055-X.
https://doi.org/10.1016/0095-8956(88)90055-X

[26] Anton Kotzig. Quelques remarques sur les transformations $\kappa$. In seminaire Paris, 1977.

[27] André Bouchet. Caracterisation des symboles croises de genre nul. Comptes Rendus de l'Académie des Sciences, 274: 724–727, 1972.

[28] André Bouchet. Circle Graph Obstructions. Journal of Combinatorial Theory, Series B, 60 (1): 107–144, 1994. 10.1006/jctb.1994.1008.
https://doi.org/10.1006/jctb.1994.1008

[29] Martin Charles Golumbic. Algorithmic graph theory and perfect graphs. North-Holland Publishing Co., 2nd edition, 2004. ISBN 978-0444515308. 10.1016/C2013-0-10739-8.
https://doi.org/10.1016/C2013-0-10739-8

[30] Norman Biggs, E Keith Lloyd, and Robin J Wilson. Graph Theory, 1736-1936. Oxford University Press, 1976. ISBN 9780198539162.

[31] Jens Vygen. Np-completeness of some edge-disjoint paths problems. Discrete Applied Mathematics, 61 (1): 83–90, 1995. 10.1016/0166-218X(93)E0177-Z.
https://doi.org/10.1016/0166-218X(93)E0177-Z

[32] M. Fleury. Deux problemes de Geometrie de sitation. Journal de mathematiques elementaires, 2nd (2): 257–261, 1883.

[33] Shimon Even. Graph Algorithms. Cambridge University Press, 2 edition, 2011. 10.1017/CBO9781139015165.
https://doi.org/10.1017/CBO9781139015165

Cited by

[1] Christopher Vairogs, Samihr Hermes, and Felix Leditzky, "Localizing multipartite entanglement with local and global measurements", Quantum 10, 2007 (2026).

[2] Jakob Kaltoft Søndergaard, René Bødker Christensen, and Petar Popovski, 2025 International Conference on Quantum Communications, Networking, and Computing (QCNC) 91 (2025) ISBN:979-8-3315-3159-1.

[3] Jorge Miguel-Ramiro and Wolfgang Dür, "Graph state fission", Physical Review A 111 5, 052624 (2025).

[4] Jakob Kaltoft Søndergaard, René Bødker Christensen, and Petar Popovski, 2026 International Conference on Quantum Communications, Networking, and Computing (QCNC) 403 (2026) ISBN:979-8-3315-6110-9.

[5] Si-Yi Chen, Angela Sara Cacciapuoti, and Marcello Caleffi, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 1160 (2025) ISBN:979-8-3315-5736-2.

[6] Axel Dahlberg, Jonas Helsen, and Stephanie Wehner, "Counting single-qubit Clifford equivalent graph states is #P-complete", Journal of Mathematical Physics 61 2, 022202 (2020).

[7] Iulian Ioan Bîrlică, Alin Bogdan Popa, Bogdan Călin Ciobanu, Florin Pop, and Pantelimon George Popescu, "Entanglement in the trees: Optimal entanglement distribution in binary tree quantum network topologies", Future Generation Computer Systems 184, 108597 (2026).

[8] Xie Tao, Sun Jiazheng, Zhao Xiangqiang, Yu Chongchong, and Feng Wenbin, 2024 43rd Chinese Control Conference (CCC) 7948 (2024) ISBN:978-9-8875-8158-1.

[9] F. Hahn, A. Dahlberg, J. Eisert, and A. Pappa, "Limitations of nearest-neighbor quantum networks", Physical Review A 106 1, L010401 (2022).

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

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

[12] Jorge Miguel-Ramiro, Jessica Illiano, Francesco Mazza, Alexander Pirker, Julia Freund, Angela Sara Cacciapuoti, Marcello Caleffi, and Wolfgang Dür, "QPing: A Quantum Ping Primitive for Quantum Networks", IEEE Journal on Selected Areas in Communications 44, 4997 (2026).

[13] Jorge Miguel-Ramiro, Alexander Pirker, and Wolfgang Dür, "Optimized Quantum Networks", Quantum 7, 919 (2023).

[14] Hjalmar Rall and Mark Tame, "Demonstration of teleportation across a quantum network code", Physical Review A 110 2, 022602 (2024).

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

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

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

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

[19] Koki Shiraishi, Hayata Yamasaki, and Mio Murao, "Efficient local operations and classical communication extraction of quantum information encoded in stabilizer codes", Physical Review A 110 5, 052617 (2024).

[20] J. de Jong, F. Hahn, N. Tcholtchev, M. Hauswirth, and A. Pappa, "Extracting GHZ states from linear cluster states", Physical Review Research 6 1, 013330 (2024).

[21] Konrad Szymański, Lina Vandré, and Otfried Gühne, "Useful entanglement can be extracted from noisy graph states", Quantum 10, 1977 (2026).

[22] Soumik Ghosh, Abhinav Deshpande, Dominik Hangleiter, Alexey V. Gorshkov, and Bill Fefferman, "Complexity Phase Transitions Generated by Entanglement", Physical Review Letters 131 3, 030601 (2023).

[23] Si-Yi Chen, Angela Sara Cacciapuoti, and Marcello Caleffi, "On the Efficient Extraction of Entangled Resources", IEEE Transactions on Communications 74, 3517 (2026).

[24] Yuki Takeuchi, "Catalytic Transformation from Computationally Universal to Strictly Universal Measurement-Based Quantum Computation", Physical Review Letters 133 5, 050601 (2024).

[25] Maria Flors Mor-Ruiz and Wolfgang Dür, "Influence of Noise in Entanglement-Based Quantum Networks", IEEE Journal on Selected Areas in Communications 42 7, 1793 (2024).

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

[27] Yuan Li, Hao Zhang, Chen Zhang, Tao Huang, and F. Richard Yu, "A Survey of Quantum Internet Protocols From a Layered Perspective", IEEE Communications Surveys & Tutorials 26 3, 1606 (2024).

[28] Vaisakh Mannalath and Anirban Pathak, "Entanglement Routing and Bottlenecks in Grid Networks", Annalen der Physik 537 5, 2400316 (2025).

[29] Christopher Vairogs, Akanksha Chablani, Leo Lee, Hanyang Sha, Abigail Vaughan-Lee, and Jacob L. Beckey, "Localizing entanglement in high-dimensional states", arXiv:2510.08501, (2025).

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

[31] Maxime Cautrès, Nathan Claudet, Mehdi Mhalla, Simon Perdrix, Valentin Savin, and Stéphan Thomassé, "Vertex-minor universal graphs for generating entangled quantum subsystems", arXiv:2402.06260, (2024).

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

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 22:04:07) and SAO/NASA ADS (last updated successfully 2026-08-10 22:04:14). 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.