Multipartite Entanglement Distribution in Quantum Networks using Subgraph Complementations
Summarize this article with:
AbstractQuantum networks are important for quantum communication, enabling tasks such as quantum teleportation, quantum key distribution, quantum sensing, and quantum error correction, often utilizing graph states, a specific class of multipartite entangled states that can be represented by graphs. We propose a novel approach for distributing graph states across a quantum network. We show that the distribution of graph states can be characterized by a system of subgraph complementations, which we also relate to the minimum rank of the underlying graph and the degree of entanglement quantified by the Schmidt-rank of the quantum state. We analyze resource usage for our algorithm and show that it improves on the number of qubits, bits for classical communication, and EPR pairs utilized, as compared to prior work. In fact, the number of local operations and resource consumption for our approach scales linearly in the number of vertices. This produces a quadratic improvement in completion time for several classes of graph states represented by dense graphs, which translates into an exponential improvement by allowing parallelization of gate operations. This leads to improved fidelities in the presence of noisy operations, as we show through simulation in the presence of noisy operations. We classify common classes of graph states, along with their optimal distribution time using subgraph complementations. We find a sequence of subgraph complementation operations to distribute an arbitrary graph state which we conjecture is close to the optimal sequence, and establish upper bounds on distribution time along with providing approximate greedy algorithms.Featured image: Subgraph complementation operation on four verticesPopular summaryHow can we efficiently share quantum entanglement across multiple parties in a quantum network? We introduce a new method for distributing graph states—the fundamental resource in quantum networks—using a process called subgraph complementation. This approach directly links the number of operations to distribute the graph state to the degree of entanglement quantified by its minimum rank, while using fewer resources than previous methods. We also show this leads to improved fidelities of the graph state in the presence of noisy operations.► BibTeX data@article{Sen2025multipartite, doi = {10.22331/q-2025-11-17-1911}, url = {https://doi.org/10.22331/q-2025-11-17-1911}, title = {Multipartite {E}ntanglement {D}istribution in {Q}uantum {N}etworks using {S}ubgraph {C}omplementations}, author = {Sen, Aniruddha and Goodenough, Kenneth and Towsley, Don}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {9}, pages = {1911}, month = nov, year = {2025} }► References [1] Vladimir E Alekseev and Vadim V Lozin. On orthogonal representations of graphs. Discrete Mathematics, 226 (1-3): 359–363, 2001. 10.1016/S0012-365X(00)00168-0. URL https://doi.org/10.1016/S0012-365X(00)00168-0. https://doi.org/10.1016/S0012-365X(00)00168-0 [2] Guus Avis, Filip Rozpędek, and Stephanie Wehner. Analysis of multipartite entanglement distribution using a central quantum-network node. Physical Review A, 107 (1), 2023. 10.1103/physreva.107.012609. URL https://doi.org/10.1103/physreva.107.012609. https://doi.org/10.1103/physreva.107.012609 [3] Koji Azuma, Kiyoshi Tamaki, and Hoi-Kwong Lo. All-photonic quantum repeaters. Nature communications, 6 (1): 6787, 2015. 10.1038/ncomms7787. URL https://doi.org/10.1038/ncomms7787. https://doi.org/10.1038/ncomms7787 [4] Dan Browne, Elham Kashefi, and Simon Perdrix. Computational depth complexity of measurement-based quantum computation. In Theory of Quantum Computation, Communication, and Cryptography: 5th Conference, TQC 2010, Revised Selected Papers 5, pages 35–46, 2011. 10.1007/978-3-642-18073-6_4. URL https://doi.org/10.1007/978-3-642-18073-6_4. https://doi.org/10.1007/978-3-642-18073-6_4 [5] Calum Buchanan, Christopher Purcell, and Puck Rombach. Subgraph complementation and minimum rank. Electron. J. Comb., 29, 2021. 10.37236/10383. URL https://doi.org/10.37236/10383. https://doi.org/10.37236/10383 [6] Luís Bugalho, Bruno C Coutinho, Francisco A Monteiro, and Yasser Omar. Distributing multipartite entanglement over noisy quantum networks. quantum, 7: 920, 2023. 10.22331/q-2023-02-09-920. URL https://doi.org/10.22331/q-2023-02-09-920. https://doi.org/10.22331/q-2023-02-09-920 [7] Adán Cabello, Lars Eirik Danielsen, Antonio J. López-Tarrida, and José R. Portillo. Optimal preparation of graph states. Physical Review A, 83 (4), 2011. 10.1103/physreva.83.042314. URL https://doi.org/10.1103/physreva.83.042314. https://doi.org/10.1103/physreva.83.042314 [8] J. I. Cirac, A. K. Ekert, S. F. Huelga, and C. Macchiavello. Distributed quantum computation over noisy channels. Phys. Rev. A, 59: 4249–4254, Jun 1999. 10.1103/PhysRevA.59.4249. URL https://doi.org/10.1103/PhysRevA.59.4249. https://doi.org/10.1103/PhysRevA.59.4249 [9] Diogo Cruz, Romain Fournier, Fabien Gremion, Alix Jeannerot, Kenichi Komagata, Tara Tosic, Jarla Thiesbrummel, Chun Lam Chan, Nicolas Macris, Marc-André Dupertuis, et al. Efficient quantum algorithms for ghz and w states, and implementation on the ibm quantum computer.
Advanced Quantum Technologies, 2 (5-6): 1900015, 2019. 10.1002/qute.201900015. URL https://doi.org/10.1002/qute.201900015. https://doi.org/10.1002/qute.201900015 [10] Marti Cuquet and John Calsamiglia. Growth of graph states in quantum networks. Physical Review A—Atomic, Molecular, and Optical Physics, 86 (4): 042304, 2012. 10.1103/PhysRevA.86.042304. URL https://doi.org/10.1103/PhysRevA.86.042304. https://doi.org/10.1103/PhysRevA.86.042304 [11] Axel Dahlberg and Stephanie Wehner. Transforming graph states using single-qubit operations. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 376 (2123): 20170325, 2018. 10.1098/rsta.2017.0325. URL https://doi.org/10.1098/rsta.2017.0325. https://doi.org/10.1098/rsta.2017.0325 [12] Alex Fischer and Don Towsley. Distributing graph states across quantum networks. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 324–333. IEEE, 2021. 10.1109/QCE52317.2021.00049. URL https://doi.org/10.1109/QCE52317.2021.00049. https://doi.org/10.1109/QCE52317.2021.00049 [13] Robert B Griffiths. Graph states and graph codes. arXiv preprint arXiv:0712.1979. 10.1103/PhysRevA.78.042303. URL https://doi.org/10.1103/PhysRevA.78.042303. https://doi.org/10.1103/PhysRevA.78.042303 arXiv:0712.1979 [14] Marc Hein, Jens Eisert, and Hans J Briegel. Multiparty entanglement in graph states. Physical Review A, 69 (6): 062311, 2004. 10.1103/PhysRevA.69.062311. URL https://doi.org/10.1103/PhysRevA.69.062311. https://doi.org/10.1103/PhysRevA.69.062311 [15] Paul Hilaire, Edwin Barnes, Sophia E. Economou, and Frédéric Grosshans. Error-correcting entanglement swapping using a practical logical photon encoding. Phys. Rev. A, 104: 052623, Nov 2021. 10.1103/PhysRevA.104.052623. URL https://doi.org/10.1103/PhysRevA.104.052623. https://doi.org/10.1103/PhysRevA.104.052623 [16] Clément Meignant, Damian Markham, and Frédéric Grosshans. Distributing graph states over arbitrary quantum networks. Physical Review A, 100 (5), 2019. 10.1103/physreva.100.052333. URL https://doi.org/10.1103/physreva.100.052333. https://doi.org/10.1103/physreva.100.052333 [17] Huy-Tung Nguyen and Sang-il Oum. The average cut-rank of graphs. European Journal of Combinatorics, 90: 103183, 2020. 10.1016/j.ejc.2020.103183. URL https://doi.org/10.1016/j.ejc.2020.103183. https://doi.org/10.1016/j.ejc.2020.103183 [18] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010. 10.1017/CBO9780511976667. URL https://doi.org/10.1017/CBO9780511976667. https://doi.org/10.1017/CBO9780511976667 [19] Robert Raussendorf and Hans J Briegel. A one-way quantum computer. Physical review letters, 86 (22): 5188, 2001. 10.1103/PhysRevLett.86.5188. URL https://doi.org/10.1103/PhysRevLett.86.5188. https://doi.org/10.1103/PhysRevLett.86.5188 [20] Terry Rudolph. Why i am optimistic about the silicon-photonic route to quantum computing. APL photonics, 2 (3), 2017. 10.1063/1.4976737. URL https://doi.org/10.1063/1.4976737. https://doi.org/10.1063/1.4976737 [21] Nathan Shettell and Damian Markham. Graph states as a resource for quantum metrology. Phys. Rev. Lett., 124: 110502, Mar 2020. 10.1103/PhysRevLett.124.110502. URL https://doi.org/10.1103/PhysRevLett.124.110502. https://doi.org/10.1103/PhysRevLett.124.110502 [22] J Sperling and W Vogel. The schmidt number as a universal entanglement measure. Physica Scripta, 83 (4): 045002, 2011. 10.1088/0031-8949/83/04/045002. URL https://doi.org/10.1088/0031-8949/83/04/045002. https://doi.org/10.1088/0031-8949/83/04/045002 [23] Pei-Shun Yan, Lan Zhou, Wei Zhong, and Yu-Bo Sheng. Advances in quantum entanglement purification.
Science China Physics, Mechanics & Astronomy, 66 (5): 250301, 2023. 10.1007/s11433-022-2065-x. URL https://doi.org/10.1007/s11433-022-2065-x. https://doi.org/10.1007/s11433-022-2065-xCited byCould not fetch Crossref cited-by data during last attempt 2025-11-17 13:05:53: Could not fetch cited-by data for 10.22331/q-2025-11-17-1911 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2025-11-17 13:05:59: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractQuantum networks are important for quantum communication, enabling tasks such as quantum teleportation, quantum key distribution, quantum sensing, and quantum error correction, often utilizing graph states, a specific class of multipartite entangled states that can be represented by graphs. We propose a novel approach for distributing graph states across a quantum network. We show that the distribution of graph states can be characterized by a system of subgraph complementations, which we also relate to the minimum rank of the underlying graph and the degree of entanglement quantified by the Schmidt-rank of the quantum state. We analyze resource usage for our algorithm and show that it improves on the number of qubits, bits for classical communication, and EPR pairs utilized, as compared to prior work. In fact, the number of local operations and resource consumption for our approach scales linearly in the number of vertices. This produces a quadratic improvement in completion time for several classes of graph states represented by dense graphs, which translates into an exponential improvement by allowing parallelization of gate operations. This leads to improved fidelities in the presence of noisy operations, as we show through simulation in the presence of noisy operations. We classify common classes of graph states, along with their optimal distribution time using subgraph complementations. We find a sequence of subgraph complementation operations to distribute an arbitrary graph state which we conjecture is close to the optimal sequence, and establish upper bounds on distribution time along with providing approximate greedy algorithms.Featured image: Subgraph complementation operation on four verticesPopular summaryHow can we efficiently share quantum entanglement across multiple parties in a quantum network? We introduce a new method for distributing graph states—the fundamental resource in quantum networks—using a process called subgraph complementation. This approach directly links the number of operations to distribute the graph state to the degree of entanglement quantified by its minimum rank, while using fewer resources than previous methods. We also show this leads to improved fidelities of the graph state in the presence of noisy operations.► BibTeX data@article{Sen2025multipartite, doi = {10.22331/q-2025-11-17-1911}, url = {https://doi.org/10.22331/q-2025-11-17-1911}, title = {Multipartite {E}ntanglement {D}istribution in {Q}uantum {N}etworks using {S}ubgraph {C}omplementations}, author = {Sen, Aniruddha and Goodenough, Kenneth and Towsley, Don}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {9}, pages = {1911}, month = nov, year = {2025} }► References [1] Vladimir E Alekseev and Vadim V Lozin. On orthogonal representations of graphs. Discrete Mathematics, 226 (1-3): 359–363, 2001. 10.1016/S0012-365X(00)00168-0. URL https://doi.org/10.1016/S0012-365X(00)00168-0. https://doi.org/10.1016/S0012-365X(00)00168-0 [2] Guus Avis, Filip Rozpędek, and Stephanie Wehner. Analysis of multipartite entanglement distribution using a central quantum-network node. Physical Review A, 107 (1), 2023. 10.1103/physreva.107.012609. URL https://doi.org/10.1103/physreva.107.012609. https://doi.org/10.1103/physreva.107.012609 [3] Koji Azuma, Kiyoshi Tamaki, and Hoi-Kwong Lo. All-photonic quantum repeaters. Nature communications, 6 (1): 6787, 2015. 10.1038/ncomms7787. URL https://doi.org/10.1038/ncomms7787. https://doi.org/10.1038/ncomms7787 [4] Dan Browne, Elham Kashefi, and Simon Perdrix. Computational depth complexity of measurement-based quantum computation. In Theory of Quantum Computation, Communication, and Cryptography: 5th Conference, TQC 2010, Revised Selected Papers 5, pages 35–46, 2011. 10.1007/978-3-642-18073-6_4. URL https://doi.org/10.1007/978-3-642-18073-6_4. https://doi.org/10.1007/978-3-642-18073-6_4 [5] Calum Buchanan, Christopher Purcell, and Puck Rombach. Subgraph complementation and minimum rank. Electron. J. Comb., 29, 2021. 10.37236/10383. URL https://doi.org/10.37236/10383. https://doi.org/10.37236/10383 [6] Luís Bugalho, Bruno C Coutinho, Francisco A Monteiro, and Yasser Omar. Distributing multipartite entanglement over noisy quantum networks. quantum, 7: 920, 2023. 10.22331/q-2023-02-09-920. URL https://doi.org/10.22331/q-2023-02-09-920. https://doi.org/10.22331/q-2023-02-09-920 [7] Adán Cabello, Lars Eirik Danielsen, Antonio J. López-Tarrida, and José R. Portillo. Optimal preparation of graph states. Physical Review A, 83 (4), 2011. 10.1103/physreva.83.042314. URL https://doi.org/10.1103/physreva.83.042314. https://doi.org/10.1103/physreva.83.042314 [8] J. I. Cirac, A. K. Ekert, S. F. Huelga, and C. Macchiavello. Distributed quantum computation over noisy channels. Phys. Rev. A, 59: 4249–4254, Jun 1999. 10.1103/PhysRevA.59.4249. URL https://doi.org/10.1103/PhysRevA.59.4249. https://doi.org/10.1103/PhysRevA.59.4249 [9] Diogo Cruz, Romain Fournier, Fabien Gremion, Alix Jeannerot, Kenichi Komagata, Tara Tosic, Jarla Thiesbrummel, Chun Lam Chan, Nicolas Macris, Marc-André Dupertuis, et al. Efficient quantum algorithms for ghz and w states, and implementation on the ibm quantum computer.
Advanced Quantum Technologies, 2 (5-6): 1900015, 2019. 10.1002/qute.201900015. URL https://doi.org/10.1002/qute.201900015. https://doi.org/10.1002/qute.201900015 [10] Marti Cuquet and John Calsamiglia. Growth of graph states in quantum networks. Physical Review A—Atomic, Molecular, and Optical Physics, 86 (4): 042304, 2012. 10.1103/PhysRevA.86.042304. URL https://doi.org/10.1103/PhysRevA.86.042304. https://doi.org/10.1103/PhysRevA.86.042304 [11] Axel Dahlberg and Stephanie Wehner. Transforming graph states using single-qubit operations. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 376 (2123): 20170325, 2018. 10.1098/rsta.2017.0325. URL https://doi.org/10.1098/rsta.2017.0325. https://doi.org/10.1098/rsta.2017.0325 [12] Alex Fischer and Don Towsley. Distributing graph states across quantum networks. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 324–333. IEEE, 2021. 10.1109/QCE52317.2021.00049. URL https://doi.org/10.1109/QCE52317.2021.00049. https://doi.org/10.1109/QCE52317.2021.00049 [13] Robert B Griffiths. Graph states and graph codes. arXiv preprint arXiv:0712.1979. 10.1103/PhysRevA.78.042303. URL https://doi.org/10.1103/PhysRevA.78.042303. https://doi.org/10.1103/PhysRevA.78.042303 arXiv:0712.1979 [14] Marc Hein, Jens Eisert, and Hans J Briegel. Multiparty entanglement in graph states. Physical Review A, 69 (6): 062311, 2004. 10.1103/PhysRevA.69.062311. URL https://doi.org/10.1103/PhysRevA.69.062311. https://doi.org/10.1103/PhysRevA.69.062311 [15] Paul Hilaire, Edwin Barnes, Sophia E. Economou, and Frédéric Grosshans. Error-correcting entanglement swapping using a practical logical photon encoding. Phys. Rev. A, 104: 052623, Nov 2021. 10.1103/PhysRevA.104.052623. URL https://doi.org/10.1103/PhysRevA.104.052623. https://doi.org/10.1103/PhysRevA.104.052623 [16] Clément Meignant, Damian Markham, and Frédéric Grosshans. Distributing graph states over arbitrary quantum networks. Physical Review A, 100 (5), 2019. 10.1103/physreva.100.052333. URL https://doi.org/10.1103/physreva.100.052333. https://doi.org/10.1103/physreva.100.052333 [17] Huy-Tung Nguyen and Sang-il Oum. The average cut-rank of graphs. European Journal of Combinatorics, 90: 103183, 2020. 10.1016/j.ejc.2020.103183. URL https://doi.org/10.1016/j.ejc.2020.103183. https://doi.org/10.1016/j.ejc.2020.103183 [18] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010. 10.1017/CBO9780511976667. URL https://doi.org/10.1017/CBO9780511976667. https://doi.org/10.1017/CBO9780511976667 [19] Robert Raussendorf and Hans J Briegel. A one-way quantum computer. Physical review letters, 86 (22): 5188, 2001. 10.1103/PhysRevLett.86.5188. URL https://doi.org/10.1103/PhysRevLett.86.5188. https://doi.org/10.1103/PhysRevLett.86.5188 [20] Terry Rudolph. Why i am optimistic about the silicon-photonic route to quantum computing. APL photonics, 2 (3), 2017. 10.1063/1.4976737. URL https://doi.org/10.1063/1.4976737. https://doi.org/10.1063/1.4976737 [21] Nathan Shettell and Damian Markham. Graph states as a resource for quantum metrology. Phys. Rev. Lett., 124: 110502, Mar 2020. 10.1103/PhysRevLett.124.110502. URL https://doi.org/10.1103/PhysRevLett.124.110502. https://doi.org/10.1103/PhysRevLett.124.110502 [22] J Sperling and W Vogel. The schmidt number as a universal entanglement measure. Physica Scripta, 83 (4): 045002, 2011. 10.1088/0031-8949/83/04/045002. URL https://doi.org/10.1088/0031-8949/83/04/045002. https://doi.org/10.1088/0031-8949/83/04/045002 [23] Pei-Shun Yan, Lan Zhou, Wei Zhong, and Yu-Bo Sheng. Advances in quantum entanglement purification.
Science China Physics, Mechanics & Astronomy, 66 (5): 250301, 2023. 10.1007/s11433-022-2065-x. URL https://doi.org/10.1007/s11433-022-2065-x. https://doi.org/10.1007/s11433-022-2065-xCited byCould not fetch Crossref cited-by data during last attempt 2025-11-17 13:05:53: Could not fetch cited-by data for 10.22331/q-2025-11-17-1911 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2025-11-17 13:05:59: No response from ADS or unable to decode the received json data when getting the list of citing works.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.