The core technology to construct large-scale quantum networks is to efficiently distribute remote entanglement among quantum nodes. Entanglement routing deals with the problem of discovering and selecting paths to perform the multi-hop entanglement swapping between two distant nodes. In order to succeed in end-to-end entanglement creation for a given path, entanglement distribution of all direct quantum links and Bell state measurement of all intermediate nodes along the path should be successful. Existing studies have addressed the entanglement routing problem based on path discovery algorithms considering the above characteristics and selecting the optimal path from the individual performance perspective of each path. In this article, we newly define the entanglement routing problem considering the joint-utilization between multiple paths to maximize the network resource efficiency, and present an optimal link-set configuration algorithm, named RELiC, as a solution for this. The performance of the proposed entanglement routing protocol is evaluated in small- and large-scale quantum networks through mathematical analysis and simulation study.
The core technology to construct large-scale quantum networks is to efficiently distribute remote entanglement among quantum nodes. Entanglement routing deals with the problem of discovering and selecting paths to perform the multi-hop entanglement swapping between two distant nodes. In order to succeed in end-to-end entanglement creation for a given path, entanglement distribution of all direct quantum links and Bell state measurement of all intermediate nodes along the path should be successful. Existing studies have addressed the entanglement routing problem based on path discovery algorithms considering the above characteristics and selecting the optimal path from the individual performance perspective of each path. In this article, we newly define the entanglement routing problem considering the joint-utilization between multiple paths to maximize the network resource efficiency, and present an optimal link-set configuration algorithm, named RELiC, as a solution for this. The performance of the proposed entanglement routing protocol is evaluated in small- and large-scale quantum networks through mathematical analysis and simulation study.
How to efficiently distribute entanglement over large-scale quantum networks is still an open problem that greatly depends on the technology considered. In this work, we consider quantum networks where each link is characterized by a trade-off between the entanglement generation rate and fidelity. For such networks, we look at the two following problems: the one of finding the best path to connect any two given nodes, and the problem of finding the best starting node in order to connect three nodes in the network multipartite entanglement routing. Two entanglement distribution models are considered: one where entangled qubits are distributed one at a time, and a flow model where a large number of entangled qubits are distributed simultaneously. The paper proposes of a quite general methodology that uses continuous fidelity curves (i.e., entanglement generation fidelity vs. rate) as the main routing metric. Combined with multi-objective path-finding algorithms, the fidelity curves describing each link allow finding a set of paths that maximize both the end-to-end fidelity and the entanglement generation rate. For the link models and networks considered, it is proven that the algorithm always converges to the optimal solution. It is also shown through simulation that the execution time grows polynomially with the number of network nodes (growing with a power between 1 and 1.4, depending on the network)
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 fundamental technology for the construction of large-scale quantum networks lies in the efficient distribution of remote entanglement among quantum nodes. Entanglement routing tackles the challenge of path selection between two distant end nodes and realizes entanglement distribution through multi-hop entanglement swapping. Given the inherent probability of swapping, entanglement distribution flow always presents inevitable losses. The existing routing works adopt a parallel swapping mode, which only considers the final end-to-end distribution loss effect. This lag of failure detection and complete independence between swapping reduce distribution efficiency. We observe that the sequential swapping mode can improve this defect, but it is not thorough. Thus, in this paper, we explore the entanglement flow loss effect in the sequential entanglement swapping (Loss-SES) process in order to perceive failures earlier and save network resources. Subsequently, we introduce a novel metric to quantify path performance, namely the expected entanglement throughput (EET). Building upon EET, we propose the entanglement routing algorithm MaxEET adapted to the Loss-SES process to maximize EET. For efficient deployment, in the single-request scenario, we determine the optimal routing initiation direction by introducing a bidirectional routing mechanism. In the multi-request scenario, we design a greedy and contention-free iterative routing algorithm to exhaust resources. Based on extensive simulations, the results show the superiority of our proposed Loss-SES mode compared to other modes in terms of throughput, fairness, and utilization.
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.
Quantum network can provide end-to-end entanglements through quantum operations, supporting various quantum applications such as quantum key distribution and distributed quantum computing. However, many previous proposals for quantum networks assumed the division of quantum network into time slots and batch processing of network communication tasks, performing poorly in dynamic network scenarios and not fully utilizing network resources. This work focuses on the routing problem in entanglement quantum networks, aiming to provide more efficient end-to-end entanglement establishment for upper-layer applications. We propose an on-demand routing algorithm that dynamically adjusts the optimal path based on the current network conditions. Specifically, we consider the benefits of path width for quantum networks and propose an algorithm for finding the shortest wide path. Using this algorithm, each node establishes its own routing table. Additionally, to dynamically avoid network hotspots, we introduce the concept of traffic to reflect the busyness of nodes. Finally, using a dynamic cost calculation method as the routing metric, we select the optimal path for the current request. To evaluate the performance of the proposed quantum routing algorithm, we conducted simulation experiments on SimQN quantum simulation platform. The results show that our approach improves network throughput by 14 percent compared to existing solutions.
Entanglement routing in near-term quantum networks consists of choosing the optimal sequence of short-range entanglements to combine through swapping operations to establish end-to-end entanglement between two distant nodes. Similar to traditional routing technologies, a quantum routing protocol uses network information to choose the best paths to satisfy a set of end-to-end entanglement requests. However, in addition to network state information, a quantum routing protocol must also take into account the requested entanglement fidelity, the probabilistic nature of swapping operations, and the short lifetime of entangled states. In this work, we formulate a practical entanglement routing problem and analyze and categorize the main approaches to address it, drawing comparisons to, and inspiration from, classical network routing strategies where applicable. We classify and discuss the studied quantum routing schemes into reactive, proactive, and hybrid routing.