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.
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.
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 (SD) 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. Then we consider the common scenario with multiple S-D pairs and design a greedy-based algorithm considering resource allocation and rerouting process for multiple routing requests. To verify the effectiveness and superiority of the proposed algorithms, extensive simulations are conducted, and the simulation results show that the proposed algorithms not only can provide fidelity-guarantee 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.
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.
The mechanism of transferring and routing information in quantum and classical network are basically different. The basic idea and working principle of quantum networks is based on a unique feature of quantum mechanics known as entanglement. Since entanglement generation rate is a key factor for quantum networks it can be considered as a route metric. In this paper, we propose two different protocols for local entanglement routing in a quantum ring network. In the first protocol, local link entanglement rate is considered as a route metric. However, the routing decision in the second protocol is made based on finding the shortest path between source and destination. It is shown that though local link entanglement rate is decisive criterion for routing in the first algorithm, the second algorithm can reach higher end-to-end entanglement rate.
A fully-quantum network implies the creation of quantum entanglement between a given source node and some other destination node, with a number of quantum repeaters in between. This paper tackles the problem of quantum entanglement distribution by solving the routing problem over an infrastructure based on quantum repeaters and with a finite number of pairs of entangled qubits available in each link. The network model considers that link purification is available such that a nested purification protocol can be applied at each link to generate entangled qubits with higher fidelity than the original ones. A low-complexity multi-objective routing algorithm to find the shortest path between any two given nodes is proposed and assessed for random networks, using a fairly general path extension mechanism that can fit a large family of particular technological requirements. Different types of quantum protocols require different levels of fidelity for the entangled qubit pairs. For that reason, the proposed algorithm identifies the shortest path between two nodes that assures an end-to-end fidelity above a specified threshold. The minimum requirements for the end-to-end entanglement fidelity depend on the whole extension of the paths, and cannot be looked at as a local property of each link. Moreover, one needs to keep track not only of the shortest path, but also of longer paths holding more entangled qubits than the shorter paths in order to satisfy the fidelity criterion. Thus, standard single parameter shortest-path algorithms do not necessarily converge to the optimal solution. The problem of finding the best path in a network subject to multiple criteria (known as multi-objective routing) is, in general, an NP-hard problem due to the rapid growth of the number of stored paths. This work proposes a metric that identifies and discards paths that are objectively worse than others. By doing so, the time complexity of the proposed algorithm scales near-to-linearly with respect to the number of nodes in the network, showing that the shortest-path problem in quantum networks can be solved with a complexity very close to the one of the classical counterparts. That is analytically proved for the case where all the links of a path have the same fidelity (homogeneous model). The algorithm is also adapted to a particular type of path extension, where different links along a path can be purified to different degrees, asserting its flexibility and near-to-linearity even when heterogeneous fidelities along the sections of a path are considered.
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 networks are envisioned to enable reliable distribution and manipulation of quantum information across distances, forming the foundation of a future quantum internet. The fair and efficient allocation of communication resources in such networks has been addressed through the quantum network utility maximization (QNUM) framework, which optimizes network utility under the assumption of predetermined routes for competing user demands. In this work, we relax this assumption and aim to identify optimal routes that correspond to the maximum achievable network utility. Specifically, we formulate the single-path utility-based entanglement routing problem as a Mixed-Integer Convex Program (MICP). The formulation is exact when negativity is chosen as the entanglement measure for utility quantification or the network supports sufficiently high entanglement generation rates across demands. For other entanglement measures considered, the formulation approximates the problem with over 99.99% accuracy on evaluated real-world examples. To improve computational tractability, we propose a randomized rounding-based heuristic and an upper bound via the relaxation of the MICP. Furthermore, based on min-congestion routing, we introduce an alternative randomized heuristic and upper bound. This heuristic is computationally faster, while both the heuristic and the upper bound often outperform their counterparts on considered real-world networks. Our work provides the framework for extending classical flow-based and quality of service-aware routing concepts to quantum networks.