Quantum repeater networks are a fundamental of any future quantum internet and long-distance quantum communications. The entangled quantum nodes can communicate through several different levels of entanglement, leading to a heterogeneous, multilevel network structure. The level of entanglement between the quantum nodes determines the hop distance and the probability of the existence of an entangled link in the network. Here, we define a decentralized routing for entangled quantum networks. The proposed method allows an efficient routing to find the shortest paths in entangled quantum networks by using only local knowledge of the quantum nodes. We give bounds on the maximum value of the total number of entangled links of a path. The proposed scheme can be directly applied in practical quantum communications and quantum networking scenarios.
Quantum repeater networks are a fundamental of any future quantum internet and long-distance quantum communications. The entangled quantum nodes can communicate through several different levels of entanglement, leading to a heterogeneous, multilevel network structure. The level of entanglement between the quantum nodes determines the hop distance and the probability of the existence of an entangled link in the network. Here, we define a decentralized routing for entangled quantum networks. The proposed method allows an efficient routing to find the shortest paths in entangled quantum networks by using only local knowledge of the quantum nodes. We give bounds on the maximum value of the total number of entangled links of a path. The proposed scheme can be directly applied in practical quantum communications and quantum networking scenarios.
A quantum repeater is the heart of a quantum internet that enables end-to-end communication over long distances using the quantum entanglement feature. Although this characteristic gives quantum networks tremendous power in terms of speed and security, it puts quantum networks, especially the quantum internet, in front of challenges, like transforming a short-distance quantum link into a long-distance link, in addition to entanglement routing for finding the best path within a quantum network. So, this research aims to propose a hybrid quantum routing protocol (HQRP) based on routing metrics of the classical networks like hops count, as well as metrics of the quantum network represented by the possibility of entanglement between end nodes in the network. As a result, a mathematical model was built to determine the optimal path among many paths within the quantum network, and it was implemented on our quantum network simulator. Finally, we concluded that the proposed algorithm gives the optimal path based on the highest entanglement probability and lowest number of hop count.
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.
We define the entanglement-gradient routing scheme for quantum repeater networks. The routing framework fuses the fundamentals of swarm intelligence and quantum Shannon theory. Swarm intelligence provides nature-inspired solutions for problem solving. Motivated by models of social insect behavior, the routing is performed using parallel threads to determine the shortest path via the entanglement gradient coefficient, which describes the feasibility of the entangled links and paths of the network. The routing metrics are derived from the characteristics of entanglement transmission and relevant measures of entanglement distribution in quantum networks. The method allows a moderate complexity decentralized routing in quantum repeater networks. The results can be applied in experimental quantum networking, future quantum Internet, and long-distance quantum communications.
With the emergence of the Quantum Internet, the need for advanced quantum networking techniques has significantly risen. Various models of quantum repeaters have been presented, each delineating a unique strategy to ensure quantum communication over long distances. We focus on repeaters that employ entanglement generation and swapping. This revolves around establishing remote end-to-end entanglement through repeaters, a concept we denote as the “quantum-native” repeaters (also called “first-generation” repeaters in some literature). The challenges in routing with quantum-native repeaters arise from probabilistic entanglement generation and restricted coherence time. Current approaches use synchronized time slots to search for entanglement-swapping paths, resulting in inefficiencies. Here, we propose a new set of asynchronous routing protocols for quantum networks by incorporating the idea of maintaining a dynamic topology in a distributed manner, which has been extensively studied in classical routing for lossy networks, such as using a destination-oriented directed acyclic graph or a spanning tree. The protocols update the entanglement-link topology asynchronously, identify optimal entanglement-swapping paths, and preserve unused direct-link entanglements. Our results indicate that asynchronous protocols achieve a larger upper bound with an appropriate setting and significantly higher entanglement rate than existing synchronous approaches, and the rate increases with coherence time, suggesting that it will have a much more profound impact on quantum networks as technology advances.
In quantum repeater networks, the varying stability of entangled quantum links makes dynamic topology resilience an emerging issue. Here we define an efficient topology adaption method for quantum repeater networks. The model assumes the random failures of entangled links and several parallel demands from legal users. The shortest path defines a set of entangled links for which the probability of stability is above a critical threshold. The scheme is utilized in a base-graph of the overlay quantum network to provide an efficient shortest path selection for the demands of all users of the network. We study the problem of entanglement assignment in a quantum repeater network, prove its computational complexity, and show an optimization procedure. The results are particularly convenient for future quantum networking, quantum-internet, and experimental long-distance quantum communications.
A quantum network promises to enable long distance quantum communication, and assemble small quantum devices into a large quantum computing cluster. Each network node can thereby be seen as a small few qubit quantum computer. Qubits can be sent over direct physical links connecting nearby quantum nodes, or by means of teleportation over pre-established entanglement amongst distant network nodes. Such pre-shared entanglement effectively forms a shortcut - a virtual quantum link - which can be used exactly once. Here, we present an abstraction of a quantum network that allows ideas from computer science to be applied to the problem of routing qubits, and manage entanglement in the network. Specifically, we consider a scenario in which each quantum network node can create EPR pairs with its immediate neighbours over a physical connection, and perform entanglement swapping operations in order to create long distance virtual quantum links. We proceed to discuss the features unique to quantum networks, which call for the development of new routing techniques. As an example, we present two simple hierarchical routing schemes for a quantum network of N nodes for a ring and sphere topology. For these topologies we present efficient routing algorithms requiring O(log N) qubits to be stored at each network node, O(polylog N) time and space to perform routing decisions, and O(log N) timesteps to replenish the virtual quantum links in a model of entanglement generation.