Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2211.06690 · Physical Review A

Multiparty entanglement routing in quantum networks

Vaisakh Mannalath, Anirban Pathak

Published Dec 19, 2023• 34 citations
arXivHTMLPDF

Abstract

Distributing entanglement among multiple users is a fundamental problem in quantum networks, requiring an efficient solution. In this work, a protocol is proposed for extracting maximally entangled ($|{\text{GHZ}}_{n}\ensuremath{\rangle}$) states for any number of parties in a quantum network. It is based on the graph-state formalism and requires minimal assumptions on the network state. The protocol only requires local measurements at the network nodes and just a single-qubit memory per user. Existing protocols on bipartite entanglement routing are also improved for specific nearest-neighbor network architectures. To this end, the concept of majorization is utilized to establish a hierarchy among different paths in a network based on their efficacy. This approach utilizes the symmetry of the underlying graph state to obtain better-performing algorithms.

DOI
10.1103/physreva.108.062614

Related papers

Improved Routing of Multiparty Entanglement over Quantum Networks

Nirupam Basak, Goutam Paul

The effective routing of entanglement over a quantum network is a fundamental problem in quantum communication. The distribution and reshaping of multipartite entanglement over a quantum network requires scalable protocols that adapt to the underlying topology. Graph states provide a convenient framework for this challenging task, as they encode global entanglement in a structured way that can be locally manipulated to produce a variety of target states, without requiring additional long-distance quantum operations. In this article, we propose graph-state-based routing protocols for sharing GHZ states, achieving larger sizes than those achieved in the existing works for given network topologies. For this improvement, we consider tree structures connecting the users participating in the final GHZ states, as opposed to the linear configurations used in the earlier works. In particular, for grid networks, we show special constructions of such trees that achieve larger GHZ states than the prior works. Moreover, if the user nodes along which the entanglement is to be routed are pre-specified, a strategy is proposed to accomplish this routing.

arXiv:2409.14694•ACM Transactions on Quantum Computing•Apr 22, 2026•3 citations

Multipartite Entanglement Routing Design in Quantum Networks

Imran Ahmed, Yudai Ogata, Eiji Oki

Quantum networks enable secure communication and distributed quantum computation using entanglement, quantum teleportation, and the no-cloning theorem. Future quantum networks will support multiparty applications such as multiparty quantum key distribution and quantum secret sharing, which require simultaneous entanglement distribution among multiple users. Therefore, efficient routing that accounts for quantum network constraints is crucial for practical multiparty quantum communications. Although bipartite entanglement routing has been studied extensively, multipartite entanglement routing with probabilistic quantum link generation and fusion operations remains inadequately addressed. This paper proposes a routing model for multipartite entanglement distribution that explicitly incorporates the probabilistic nature of quantum operations and maximizes the probability of successfully distributing a Greenberger-Horne-Zeilinger (GHZ) state to all requesting users under practical quantum network constraints. We formulate this model as a mixed-integer linear programming (MILP) problem. We prove that finding the optimal Steiner entanglement tree under the proposed model is NP-hard. For large-scale scenarios where MILP becomes computationally intractable, we develop a heuristic approach. Numerical results demonstrate that the proposed model achieves a higher entanglement tree success probability and greater robustness than baseline methods across diverse network conditions, including scenarios with stringent quantum memory constraints and large terminal sets.

IEEE Transactions on Network and Service Management•Jan 1, 2026•0 citations

A Heuristic for Entanglement Routing in Quantum Networks

Wei-Hsun Huang, Dung H. P. Nguyen, Ting-Xiu Kuo +3 more

Due to the fact that quantum networks can provide higher security in communications, many related issues have been presented and addressed recently. One of the most important issues is to study the routing in quantum networks with multiple source-destination pairs while maximizing the total end-to-end entanglement rate. In previous studies, the shortest paths are typically selected as the entanglement paths for a source-destination pair to increase the total end-to-end entanglement rate. However, this approach is only efficient once the network resources are sufficient. Moreover, source-destination pairs only require a specific entanglement rate rather than the shortest paths. Therefore, in this paper, we suppose that each source-destination pair requires an upper bound of the entanglement rate. Under this assumption, a novel problem is proposed to construct entanglement paths for a set of multiple source-destination pairs such that the total end-to-end entanglement rate is maximized. We then propose a greedy algorithm to solve the problem. Finally, the simulation is conducted to evaluate the performance of the proposed algorithm.

International Conference on Applied System Innovation•Apr 21, 2023•0 citations

Asynchronous Routing for Multipartite Entanglement in Quantum Networks

Chenliang Tian, Zebo Yang, Raj Jain +6 more

In quantum networks, one way to communicate is to distribute entanglements through swapping at intermediate nodes. Most existing work primarily aims to create efficient two-party end-to-end entanglement over long distances. However, some scenarios also require remote multipartite entanglement for applications such as quantum secret sharing and multi-party computation. Our previous study improved end-to-end entanglement rates using an asynchronous, tree-based routing scheme that relies solely on local knowledge of entanglement links, conserving unused entanglement and avoiding synchronous operations. This article extends this approach to multipartite entanglements, particularly the three-party Greenberger-Horne-Zeilinger (GHZ) states. It shows that our asynchronous protocol outperforms traditional synchronous methods in entanglement rates, especially as coherence times increase. This approach can also be extended to four-party and larger multipartite GHZ states, highlighting the effectiveness and adaptability of asynchronous routing for multipartite scenarios across various network topologies.

quant-pharXiv:2603.27551•IEEE Annual Computing and Communication Workshop and Conference (CCWC)•Mar 31, 2026•2 citations

Quantum network routing and local complementation

F. Hahn, Anna Pappa, J. Eisert

Abstract Quantum communication between distant parties is based on suitable instances of shared entanglement. For efficiency reasons, in an anticipated quantum network beyond point-to-point communication, it is preferable that many parties can communicate simultaneously over the underlying infrastructure; however, bottlenecks in the network may cause delays. Sharing of multi-partite entangled states between parties offers a solution, allowing for parallel quantum communication. Specifically for the two-pair problem, the butterfly network provides the first instance of such an advantage in a bottleneck scenario. In this paper, we propose a more general method for establishing EPR pairs in arbitrary networks. The main difference from standard repeater network approaches is that we use a graph state instead of maximally entangled pairs to achieve long-distance simultaneous communication. We demonstrate how graph-theoretic tools, and specifically local complementation, help decrease the number of required measurements compared to usual methods applied in repeater schemes. We examine other examples of network architectures, where deploying local complementation techniques provides an advantage. We finally consider the problem of extracting graph states for quantum communication via local Clifford operations and Pauli measurements, and discuss that while the general problem is known to be NP-complete, interestingly, for specific classes of structured resources, polynomial time algorithms can be identified.

arXiv:1805.04559•npj Quantum Information•Sep 6, 2019•145 citations

Multi-Entanglement Routing Design over Quantum Networks

Yiming Zeng, Jiarui Zhang, Ji Liu +2 more

Quantum networks are considered as a promising future platform for quantum information exchange and quantum applications, which have capabilities far beyond the traditional communication networks. Remote quantum entanglement is an essential component of a quantum network. How to efficiently design a multi-routing entanglement protocol is a fundamental yet challenging problem. In this paper, we study a quantum entanglement routing problem to simultaneously maximize the number of quantum-user pairs and their expected throughput. Our approach is to formulate the problem as two sequential integer programming steps. We propose efficient entanglement routing algorithms for the two integer programming steps and analyze their time complexity and performance bounds. Results of evaluation highlight that our approach outperforms existing solutions in both served quantum-user pairs numbers and the network expected throughput.

arXiv:2205.15501•IEEE Conference on Computer Communications (INFOCOM)•May 2, 2022•68 citations
Distributing entanglement among multiple users is a fundamental problem in quantum networks, requiring an efficient solution. In this work, a protocol is proposed for extracting maximally entangled (∣GHZn\ensuremath⟩|{\text{GHZ}}_{n}\ensuremath{\rangle}∣GHZn​\ensuremath⟩) states for any number of parties in a quantum network. It is based on the graph-state formalism and requires minimal assumptions on the network state. The protocol only requires local measurements at the network nodes and just a single-qubit memory per user. Existing protocols on bipartite entanglement routing are also improved for specific nearest-neighbor network architectures. To this end, the concept of majorization is utilized to establish a hierarchy among different paths in a network based on their efficacy. This approach utilizes the symmetry of the underlying graph state to obtain better-performing algorithms.
The effective routing of entanglement over a quantum network is a fundamental problem in quantum communication. The distribution and reshaping of multipartite entanglement over a quantum network requires scalable protocols that adapt to the underlying topology. Graph states provide a convenient framework for this challenging task, as they encode global entanglement in a structured way that can be locally manipulated to produce a variety of target states, without requiring additional long-distance quantum operations. In this article, we propose graph-state-based routing protocols for sharing GHZ states, achieving larger sizes than those achieved in the existing works for given network topologies. For this improvement, we consider tree structures connecting the users participating in the final GHZ states, as opposed to the linear configurations used in the earlier works. In particular, for grid networks, we show special constructions of such trees that achieve larger GHZ states than the prior works. Moreover, if the user nodes along which the entanglement is to be routed are pre-specified, a strategy is proposed to accomplish this routing.
Quantum networks enable secure communication and distributed quantum computation using entanglement, quantum teleportation, and the no-cloning theorem. Future quantum networks will support multiparty applications such as multiparty quantum key distribution and quantum secret sharing, which require simultaneous entanglement distribution among multiple users. Therefore, efficient routing that accounts for quantum network constraints is crucial for practical multiparty quantum communications. Although bipartite entanglement routing has been studied extensively, multipartite entanglement routing with probabilistic quantum link generation and fusion operations remains inadequately addressed. This paper proposes a routing model for multipartite entanglement distribution that explicitly incorporates the probabilistic nature of quantum operations and maximizes the probability of successfully distributing a Greenberger-Horne-Zeilinger (GHZ) state to all requesting users under practical quantum network constraints. We formulate this model as a mixed-integer linear programming (MILP) problem. We prove that finding the optimal Steiner entanglement tree under the proposed model is NP-hard. For large-scale scenarios where MILP becomes computationally intractable, we develop a heuristic approach. Numerical results demonstrate that the proposed model achieves a higher entanglement tree success probability and greater robustness than baseline methods across diverse network conditions, including scenarios with stringent quantum memory constraints and large terminal sets.
Due to the fact that quantum networks can provide higher security in communications, many related issues have been presented and addressed recently. One of the most important issues is to study the routing in quantum networks with multiple source-destination pairs while maximizing the total end-to-end entanglement rate. In previous studies, the shortest paths are typically selected as the entanglement paths for a source-destination pair to increase the total end-to-end entanglement rate. However, this approach is only efficient once the network resources are sufficient. Moreover, source-destination pairs only require a specific entanglement rate rather than the shortest paths. Therefore, in this paper, we suppose that each source-destination pair requires an upper bound of the entanglement rate. Under this assumption, a novel problem is proposed to construct entanglement paths for a set of multiple source-destination pairs such that the total end-to-end entanglement rate is maximized. We then propose a greedy algorithm to solve the problem. Finally, the simulation is conducted to evaluate the performance of the proposed algorithm.
In quantum networks, one way to communicate is to distribute entanglements through swapping at intermediate nodes. Most existing work primarily aims to create efficient two-party end-to-end entanglement over long distances. However, some scenarios also require remote multipartite entanglement for applications such as quantum secret sharing and multi-party computation. Our previous study improved end-to-end entanglement rates using an asynchronous, tree-based routing scheme that relies solely on local knowledge of entanglement links, conserving unused entanglement and avoiding synchronous operations. This article extends this approach to multipartite entanglements, particularly the three-party Greenberger-Horne-Zeilinger (GHZ) states. It shows that our asynchronous protocol outperforms traditional synchronous methods in entanglement rates, especially as coherence times increase. This approach can also be extended to four-party and larger multipartite GHZ states, highlighting the effectiveness and adaptability of asynchronous routing for multipartite scenarios across various network topologies.
Abstract Quantum communication between distant parties is based on suitable instances of shared entanglement. For efficiency reasons, in an anticipated quantum network beyond point-to-point communication, it is preferable that many parties can communicate simultaneously over the underlying infrastructure; however, bottlenecks in the network may cause delays. Sharing of multi-partite entangled states between parties offers a solution, allowing for parallel quantum communication. Specifically for the two-pair problem, the butterfly network provides the first instance of such an advantage in a bottleneck scenario. In this paper, we propose a more general method for establishing EPR pairs in arbitrary networks. The main difference from standard repeater network approaches is that we use a graph state instead of maximally entangled pairs to achieve long-distance simultaneous communication. We demonstrate how graph-theoretic tools, and specifically local complementation, help decrease the number of required measurements compared to usual methods applied in repeater schemes. We examine other examples of network architectures, where deploying local complementation techniques provides an advantage. We finally consider the problem of extracting graph states for quantum communication via local Clifford operations and Pauli measurements, and discuss that while the general problem is known to be NP-complete, interestingly, for specific classes of structured resources, polynomial time algorithms can be identified.
Quantum networks are considered as a promising future platform for quantum information exchange and quantum applications, which have capabilities far beyond the traditional communication networks. Remote quantum entanglement is an essential component of a quantum network. How to efficiently design a multi-routing entanglement protocol is a fundamental yet challenging problem. In this paper, we study a quantum entanglement routing problem to simultaneously maximize the number of quantum-user pairs and their expected throughput. Our approach is to formulate the problem as two sequential integer programming steps. We propose efficient entanglement routing algorithms for the two integer programming steps and analyze their time complexity and performance bounds. Results of evaluation highlight that our approach outperforms existing solutions in both served quantum-user pairs numbers and the network expected throughput.