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

Journal of Lightwave Technology

Fragmentation-Aware Entanglement Routing for Quantum Networks

Shengyu Zhang, Shouqian Shi, Chen Qian, Kwan Lawrence Yeung

Published Apr 28, 2021• 38 citations
Publisher

Abstract

New capabilities enabled by quantum networks, e.g. quantum key distribution, rely on the concurrent quantum entanglements via multiple untrusted repeaters between the source-destination pairs, which is known as quantum routing. Existing quantum routing algorithms pre-assign the free qubits to specific paths, in order to avoid resource contention in the process of entanglement swapping. Since not all pre-assigned qubits can be utilized, the resource fragmentation problem caused can limit the network throughout. In this paper, a new fragmentation-aware entanglement routing (FER) algorithm is proposed. With FER, the entangled qubits are shared by all the paths, and the resource contention problem is solved by a priority connection mechanism. Simulation results show that FER consistently outperforms existing algorithms under different network settings.

DOI
10.1109/jlt.2021.3070859

Related papers

Concurrent Entanglement Routing for Quantum Networks

Shouqian Shi, 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.

ACM SIGCOMM Conference (SIGCOMM)•Jul 30, 2020•193 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

Concurrent efficient entanglement routing for quantum wireless networks

Weicong Huang, Dong Jiang, Lijun Chen

Due to the unconditional security of quantum communication and flexible and economical implementation of wireless communication, quantum wireless networks (QWNs) have attracted wide attention. Different from fiber-based or satellite-based quantum communication, quantum wireless networks have the characteristics of high dynamics, limited node energy, and quantum resource competition. We have found that the existing quantum wireless network routing protocols suffer from path collision, high energy consumption, and low utilization of quantum resources. In this paper, a more practical and efficient entanglement routing protocol, which can find contention-free paths for concurrent source destination pairs, is proposed. Simulation results show that the proposed protocol can not only greatly improve the throughput and success rate of the network, but also significantly prolong the network lifetime. The research developed by this work may stimulate more investigations of entanglement routing problems in QWNs.

Physical Review A•Apr 27, 2022•5 citations

Swapping-Based Entanglement Routing Design for Congestion Mitigation in Quantum Networks

Zhonghui Li, Jian Li, Kaiping Xue +5 more

The quantum network is designed to connect numerous quantum nodes and support various ground-breaking quantum applications. Most of these applications require communicating parties to share entangled pairs. Therefore, entanglement routing, a technology distributing entangled pairs between distant quantum nodes, plays a vital role in realizing quantum networks’ capability. However, due to the limitation of quantum memory size and quantum decoherence, the entangled pairs shared by adjacent quantum nodes can hardly satisfy concurrent entanglement routing requests, thus leading to severe network congestion. In this paper, we propose a novel congestion mitigation (CM) scheme to tackle such bottleneck problems. The basic idea of CM is to “recycle” idle link-level entanglement resources from well-resourced links to bottleneck links utilizing a unique enabling technology of quantum networks, called entanglement swapping. CM can increase the capacity of each bottleneck link, thus overcoming resource limitations to improve resource utilization and network throughput. To complete our work, we also propose a swapping-based entanglement routing design, including path selection and resource allocation algorithms. Extensive simulations show that our design can significantly alleviate network congestion and improve the request service rate of quantum networks compared to the traditional entanglement routing designs.

IEEE Transactions on Network and Service Management•May 12, 2023•32 citations

Starvation-aware Entanglement Quantum Routing for Quantum Key Distribution

Shengyu Zhang, Kwan Lawrence Yeung

The conventional entanglement routing algorithms favor the shorter path to maximize the throughput, which leads to the starvation problem in Quantum Key Distribution (QKD). In this paper, we focus on solving the starvation problem in QKD. We design a starvation-aware entanglement routing algorithm, which gives higher priority to the QKD task facing the starvation problem. Specifically, we prioritize the QKD task with a longer Key Distribution Time (KDT). The entangled qubit pairs will first be assigned to the path with the highest priority. Simulation results show that our proposed starvation-aware entanglement routing algorithm can reduce the maximum KDT by up to ten times.

International Conference on Consumer Electronics•Jan 6, 2024•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
New capabilities enabled by quantum networks, e.g. quantum key distribution, rely on the concurrent quantum entanglements via multiple untrusted repeaters between the source-destination pairs, which is known as quantum routing. Existing quantum routing algorithms pre-assign the free qubits to specific paths, in order to avoid resource contention in the process of entanglement swapping. Since not all pre-assigned qubits can be utilized, the resource fragmentation problem caused can limit the network throughout. In this paper, a new fragmentation-aware entanglement routing (FER) algorithm is proposed. With FER, the entangled qubits are shared by all the paths, and the resource contention problem is solved by a priority connection mechanism. Simulation results show that FER consistently outperforms existing algorithms under different network settings.
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.
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.
Due to the unconditional security of quantum communication and flexible and economical implementation of wireless communication, quantum wireless networks (QWNs) have attracted wide attention. Different from fiber-based or satellite-based quantum communication, quantum wireless networks have the characteristics of high dynamics, limited node energy, and quantum resource competition. We have found that the existing quantum wireless network routing protocols suffer from path collision, high energy consumption, and low utilization of quantum resources. In this paper, a more practical and efficient entanglement routing protocol, which can find contention-free paths for concurrent source destination pairs, is proposed. Simulation results show that the proposed protocol can not only greatly improve the throughput and success rate of the network, but also significantly prolong the network lifetime. The research developed by this work may stimulate more investigations of entanglement routing problems in QWNs.
The quantum network is designed to connect numerous quantum nodes and support various ground-breaking quantum applications. Most of these applications require communicating parties to share entangled pairs. Therefore, entanglement routing, a technology distributing entangled pairs between distant quantum nodes, plays a vital role in realizing quantum networks’ capability. However, due to the limitation of quantum memory size and quantum decoherence, the entangled pairs shared by adjacent quantum nodes can hardly satisfy concurrent entanglement routing requests, thus leading to severe network congestion. In this paper, we propose a novel congestion mitigation (CM) scheme to tackle such bottleneck problems. The basic idea of CM is to “recycle” idle link-level entanglement resources from well-resourced links to bottleneck links utilizing a unique enabling technology of quantum networks, called entanglement swapping. CM can increase the capacity of each bottleneck link, thus overcoming resource limitations to improve resource utilization and network throughput. To complete our work, we also propose a swapping-based entanglement routing design, including path selection and resource allocation algorithms. Extensive simulations show that our design can significantly alleviate network congestion and improve the request service rate of quantum networks compared to the traditional entanglement routing designs.
The conventional entanglement routing algorithms favor the shorter path to maximize the throughput, which leads to the starvation problem in Quantum Key Distribution (QKD). In this paper, we focus on solving the starvation problem in QKD. We design a starvation-aware entanglement routing algorithm, which gives higher priority to the QKD task facing the starvation problem. Specifically, we prioritize the QKD task with a longer Key Distribution Time (KDT). The entangled qubit pairs will first be assigned to the path with the highest priority. Simulation results show that our proposed starvation-aware entanglement routing algorithm can reduce the maximum KDT by up to ten times.
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.