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.
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.
Quantum networks facilitate communication among quantum devices, playing a crucial role in enabling applications beyond the reach of classical networks. However, creating a quantum network that supports reliable long-distance entanglement distribution remains a significant challenge. Unlike classical networks, connections in quantum networks are established through entanglement generation. Effective communication between quantum devices requires a routing strategy that efficiently manages the establishment of entanglement. In addition to fidelity, the quality of communication is also determined by the capacity of the generated entanglement. Therefore, we proposed a capacity allocation scheduling scheme based on a metaheuristic approach, namely a Genetic Algorithm (GA), to ensure efficient capacity allocation for multiple communication paths within each communication request. Simulations were conducted in four different scenarios, and the results were compared to an existing capacity allocation scheduling algorithm, Progressive Filling (PF), to verify the effectiveness of the proposed scheme. The average capacity utilisation, U and weighted throughput, F results indicate that PF outperforms GA in a scenario with four communication requests, while GA performs better in scenarios involving six, eight, and ten communication requests. Specifically, the improvement in average capacity utilisation ranges from 8% to 46%, and the improvement in weighted throughput ranges from 24% to 94%. These results suggest that GA can serve as a valuable reference for designing optimal routing and capacity allocation schemes in more complex networks with multiple communication requests.
Entanglement routing establishes remote entanglement connection between two arbitrary nodes, which is one of the most important functions in quantum networks. The existing routing mechanisms mainly improve the robustness and throughput facing the failure of entanglement generations, which, however, rarely include the considerations on the most important metric to evaluate the quality of connection, entanglement fidelity. To solve this problem, we propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (S-D) pairs in quantum networks. In our proposal, we first consider the single S-D pair scenario and design an iterative routing algorithm, Q-PATH, to find the optimal purification decisions along the routing path with minimum entangled pair cost. Further, a low-complexity routing algorithm using an extended Dijkstra algorithm, Q-LEAP, is designed to reduce the computational complexity by using a simple but effective purification decision method. Finally, we consider the common scenario with multiple S-D pairs and design a greedy-based algorithm considering resource allocation and re-routing process for multiple routing requests. Simulation results show that the proposed algorithms not only can provide fidelity-guaranteed routing solutions, but also has superior performance in terms of throughput, fidelity of end-to-end entanglement connection, and resource utilization ratio, compared with the existing routing scheme.
Scheduling in quantum networks involves strategically allocating quantum resources to maximize entanglement distribution efficiency and overall performance. Unlike classical networks, quantum systems lack conventional buffering mechanisms, making traditional scheduling paradigms less effective. Existing quantum network algorithms predominantly focus on routing algorithms to identify optimal entanglement paths, often neglecting timeslot scheduling for mitigating resource contention and transmission latency, particularly under multi-user environments. To address these challenges, we propose a routing algorithm tightly integrated with priority-based dynamic scheduling. The algorithm not only discovers efficient entanglement paths but also optimizes resource utilization for concurrent requests. Simulation results confirm that this approach conserves quantum resources, reduces latency, and substantially boosts network performance, providing a robust solution for multi-user quantum environments.
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.
Quantum networks are gaining momentum in finding applications in a wide range of domains. However, little research has investigated the potential of a quantum network framework to enable highly reliable communications. The goal of this work is to investigate and design the multiple-entanglement routing framework, namely k-entangled routing. In particular, the k-entangled routing will enable k paths connecting all demands (source-destination pairs) in the network. To design the k-entangled routing, we propose two algorithms that are called Sequential Multi-path Scheduling Algorithm and Min-Cut-based Multi-path Scheduling Algorithm. In addition, we evaluate the performance of the proposed algorithms and models through a realistic quantum network simulator, NetSquid, that models the stochastic processes underlying quantum communications. The results show that the proposed algorithms (SMPSA and MCSA) largely enhance the network's traffic flexibility. The proposed paradigms would lay the foundation for further research on the area of entanglement routing.
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.