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:2205.15501 · IEEE Conference on Computer Communications (INFOCOM)

Multi-Entanglement Routing Design over Quantum Networks

Yiming Zeng, Jiarui Zhang, Ji yin Liu, Zhenhua Liu, Yuanyuan Yang

Published May 2, 2022• 64 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/infocom48880.2022.9796810

Related papers

Entanglement Routing Design Over Quantum Networks

Yiming Zeng, Jiarui Zhang, Ji yin Liu +2 more

Quantum networks have emerged as a future platform for quantum information exchange and applications, with promising capabilities far beyond 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 problems. We propose efficient entanglement routing algorithms for these two optimization problems and analyze their time complexity and performance bounds. Evaluation results highlight that our approach outperforms existing solutions in both the number of quantum-user pairs served and network throughput.

IEEE/ACM Transactions on Networking•Jun 19, 2023•37 citations

Multi-User Entanglement Routing Design over Quantum Internets

Yiming Zeng, Jiarui Zhang, Xiaojun Shang +3 more

Quantum Internet has potential capabilities far beyond the traditional Internet and is thus a promising future platform for communication and computation. Entanglement is a cornerstone of quantum mechanics and forms the basis of numerous quantum applications in the quantum Internet. While existing studies primarily focus on two-user entanglement, a plethora of applications necessitates the leap to multi-user entanglement. This paper tackles the fundamental problem of multi-user entanglement routing in the quantum Internet, aiming to entangle multiple quantum users with a high entanglement rate. We abstract the problem as a novel graph routing problem, which is not readily addressed by existing graph problem solutions due to the unique characteristics of the quantum Internet. To address this problem, we first consider a sufficient condition ensuring a feasible solution's existence and design an algorithm with the optimal solution. Given the NP-Completeness and NP- Hardness of determining a feasible solution's existence and deriving an optimal solution in general cases, respectively, we propose two heuristic algorithms to offer efficient solutions, which are shown, via extensive simulations, to outperform the existing algorithms in terms of entanglement rates.

IEEE International Conference on Distributed Computing Systems (ICDCS)•Jul 23, 2024•6 citations

Analysis on a Performance and Fairness Tradeoff in Entanglement Routing for Quantum Networks

Shu Ichinoseki, Yuki Koizumi, Junji Takemasa +1 more

Quantum networks offer the capability of transferring quantum information among remote nodes leveraging the phenomenon of quantum entanglement. A key challenge is entanglement routing, which routes quantum entanglement efficiently in a quantum network to satisfy specific objectives. We focus on an interesting hypothesis that arises from the probabilistic nature of quantum entanglement: There is a tradeoff between accommodating a higher number of quantum entanglements (performance) and serving a broader range of node pairs (fairness). To confirm this hypothesis, we formulate entanglement routing as a multi-objective optimization problem. Our numerical analysis reveals that the solutions of the model form a Pareto frontier, thereby validating the hypothesis. Furthermore, we compare the performance of existing algorithms against this Pareto frontier to understand how the algorithms balance performance and fairness. Our findings contribute to designing entanglement routing algorithms.

IEEE/IFIP Network Operations and Management Symposium (NOMS)•May 6, 2024•0 citations

Modeling and Designing Routing Protocols in Quantum Networks

Shouqian Shi, Chen Qian

Quantum networks enable a number of important applications such as quantum key distribution. The basic function of a quantum network is to enable long-distance quantum entanglement between two remote communication parties. This work focuses on the entanglement routing problem, whose objective is to build long-distance entanglements for the concurrent source-destination pairs through multiple hops. Different from existing works that analyzes the traditional routing techniques on special network topologies, we present a comprehensive entanglement routing model that reflects the differences between quantum networks and classical networks and new entanglement routing algorithms that utilize the unique properties of quantum networks. Evaluation results show that the proposed algorithm Q-CAST increases the number of successful long-distance entanglements by a big margin compared to other methods. The model and simulator developed by this work may encourage more network researchers to study the entanglement routing problem.

arXiv:1909.09329•Sep 20, 2019•11 citations

Concurrent Entanglement Routing for Quantum Networks: Model and Designs

Shouqian Shi, Xiaoxue Zhang, Chen Qian

Quantum entanglement enables important computing applications such as quantum key distribution. Based on quantum entanglement, quantum networks are built to provide long-distance secret sharing between two remote communication parties. Establishing a multi-hop quantum entanglement exhibits a high failure rate, and existing quantum networks rely on trusted repeater nodes to transmit quantum bits. However, when the scale of a quantum network increases, it requires end-to-end multi-hop quantum entanglements in order to deliver secret bits without letting the repeaters know the secret bits. This work focuses on the entanglement routing problem, whose objective is to build long-distance entanglements via untrusted repeaters for concurrent source-destination pairs through multiple hops. Different from existing work that analyzes the traditional routing techniques on special network topologies, we present a comprehensive entanglement routing model that reflects the differences between quantum networks and classical networks as well as a new entanglement routing algorithm that utilizes the unique properties of quantum networks. Evaluation results show that the proposed algorithm Q-CAST increases the number of successful long-distance entanglements by a big margin compared to other methods. The model and simulator developed by this work may encourage more network researchers to study the entanglement routing problem.

IEEE/ACM Transactions on Networking•Jan 5, 2024•71 citations

Effective routing design for remote entanglement generation on quantum networks

Changhao Li, Tianyi Li, Yi-Xiang Liu +1 more

Abstract Quantum network is a promising platform for many ground-breaking applications that lie beyond the capability of its classical counterparts. Efficient entanglement generation on quantum networks with relatively limited resources such as quantum memories is essential to fully realize the network’s capabilities, the solution to which calls for delicate network design and is currently at the primitive stage. In this study we propose an effective routing scheme to enable automatic responses for multiple requests of entanglement generation between source-terminal stations on a quantum lattice network with finite edge capacities. Multiple connection paths are exploited for each connection request while entanglement fidelity is ensured for each path by performing entanglement purification. The routing scheme is highly modularized with a flexible nature, embedding quantum operations within the algorithmic workflow, whose performance is evaluated from multiple perspectives. In particular, three algorithms are proposed and compared for the scheduling of capacity allocation on the edges of quantum network. Embodying the ideas of proportional share and progressive filling that have been well-studied in classical routing problems, we design another scheduling algorithm, the propagatory update method, which in certain aspects overrides the two algorithms based on classical heuristics in scheduling performances. The general solution scheme paves the road for effective design of efficient routing and flow control protocols on applicational quantum networks.

arXiv:2001.02204•npj Quantum Information•Jan 27, 2021•133 citations
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.
Quantum networks have emerged as a future platform for quantum information exchange and applications, with promising capabilities far beyond 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 problems. We propose efficient entanglement routing algorithms for these two optimization problems and analyze their time complexity and performance bounds. Evaluation results highlight that our approach outperforms existing solutions in both the number of quantum-user pairs served and network throughput.
Quantum Internet has potential capabilities far beyond the traditional Internet and is thus a promising future platform for communication and computation. Entanglement is a cornerstone of quantum mechanics and forms the basis of numerous quantum applications in the quantum Internet. While existing studies primarily focus on two-user entanglement, a plethora of applications necessitates the leap to multi-user entanglement. This paper tackles the fundamental problem of multi-user entanglement routing in the quantum Internet, aiming to entangle multiple quantum users with a high entanglement rate. We abstract the problem as a novel graph routing problem, which is not readily addressed by existing graph problem solutions due to the unique characteristics of the quantum Internet. To address this problem, we first consider a sufficient condition ensuring a feasible solution's existence and design an algorithm with the optimal solution. Given the NP-Completeness and NP- Hardness of determining a feasible solution's existence and deriving an optimal solution in general cases, respectively, we propose two heuristic algorithms to offer efficient solutions, which are shown, via extensive simulations, to outperform the existing algorithms in terms of entanglement rates.
Quantum networks offer the capability of transferring quantum information among remote nodes leveraging the phenomenon of quantum entanglement. A key challenge is entanglement routing, which routes quantum entanglement efficiently in a quantum network to satisfy specific objectives. We focus on an interesting hypothesis that arises from the probabilistic nature of quantum entanglement: There is a tradeoff between accommodating a higher number of quantum entanglements (performance) and serving a broader range of node pairs (fairness). To confirm this hypothesis, we formulate entanglement routing as a multi-objective optimization problem. Our numerical analysis reveals that the solutions of the model form a Pareto frontier, thereby validating the hypothesis. Furthermore, we compare the performance of existing algorithms against this Pareto frontier to understand how the algorithms balance performance and fairness. Our findings contribute to designing entanglement routing algorithms.
Quantum networks enable a number of important applications such as quantum key distribution. The basic function of a quantum network is to enable long-distance quantum entanglement between two remote communication parties. This work focuses on the entanglement routing problem, whose objective is to build long-distance entanglements for the concurrent source-destination pairs through multiple hops. Different from existing works that analyzes the traditional routing techniques on special network topologies, we present a comprehensive entanglement routing model that reflects the differences between quantum networks and classical networks and new entanglement routing algorithms that utilize the unique properties of quantum networks. Evaluation results show that the proposed algorithm Q-CAST increases the number of successful long-distance entanglements by a big margin compared to other methods. The model and simulator developed by this work may encourage more network researchers to study the entanglement routing problem.
Quantum entanglement enables important computing applications such as quantum key distribution. Based on quantum entanglement, quantum networks are built to provide long-distance secret sharing between two remote communication parties. Establishing a multi-hop quantum entanglement exhibits a high failure rate, and existing quantum networks rely on trusted repeater nodes to transmit quantum bits. However, when the scale of a quantum network increases, it requires end-to-end multi-hop quantum entanglements in order to deliver secret bits without letting the repeaters know the secret bits. This work focuses on the entanglement routing problem, whose objective is to build long-distance entanglements via untrusted repeaters for concurrent source-destination pairs through multiple hops. Different from existing work that analyzes the traditional routing techniques on special network topologies, we present a comprehensive entanglement routing model that reflects the differences between quantum networks and classical networks as well as a new entanglement routing algorithm that utilizes the unique properties of quantum networks. Evaluation results show that the proposed algorithm Q-CAST increases the number of successful long-distance entanglements by a big margin compared to other methods. The model and simulator developed by this work may encourage more network researchers to study the entanglement routing problem.
Abstract Quantum network is a promising platform for many ground-breaking applications that lie beyond the capability of its classical counterparts. Efficient entanglement generation on quantum networks with relatively limited resources such as quantum memories is essential to fully realize the network’s capabilities, the solution to which calls for delicate network design and is currently at the primitive stage. In this study we propose an effective routing scheme to enable automatic responses for multiple requests of entanglement generation between source-terminal stations on a quantum lattice network with finite edge capacities. Multiple connection paths are exploited for each connection request while entanglement fidelity is ensured for each path by performing entanglement purification. The routing scheme is highly modularized with a flexible nature, embedding quantum operations within the algorithmic workflow, whose performance is evaluated from multiple perspectives. In particular, three algorithms are proposed and compared for the scheduling of capacity allocation on the edges of quantum network. Embodying the ideas of proportional share and progressive filling that have been well-studied in classical routing problems, we design another scheduling algorithm, the propagatory update method, which in certain aspects overrides the two algorithms based on classical heuristics in scheduling performances. The general solution scheme paves the road for effective design of efficient routing and flow control protocols on applicational quantum networks.