We develop new routing algorithms for a quantum network with noisy quantum devices such that each can store a small number of qubits. We thereby consider two models for the operation of such a network. The first is a continuous model, in which entanglement between a subset of the nodes is produced continuously in the background. This can in principle allows the rapid creation of entanglement between more distant nodes using the already pre-generated entanglement pairs in the network. The second is an on-demand model, where entanglement production does not commence before a request is made. Our objective is to find protocols, that minimise the latency of the network to serve a request to create entanglement between two distant nodes in the network. We propose three routing algorithms and analytically show that as expected when there is only a single request in the network, then employing them on the continuous model yields a lower latency than on the on-demand one. We study the performance of the routing algorithms in a ring, grid, and recursively generated network topologies. We also give an analytical upper bound on the number of entanglement swap operations the nodes need to perform for routing entangled links between a source and a destination yielding a lower bound on the end to end fidelity of the shared entangled state. We proceed to study the case of multiple concurrent requests and show that in some of the scenarios the on-demand model can outperform the continuous one. Using numerical simulations on ring and grid networks we also study the behaviour of the latency of all the routing algorithms. We observe that the proposed routing algorithms behave far better than the existing classical greedy routing algorithm. The simulations also help to understand the advantages and disadvantages of different types of continuous models for different types of demands.
We develop new routing algorithms for a quantum network with noisy quantum devices such that each can store a small number of qubits. We thereby consider two models for the operation of such a network. The first is a continuous model, in which entanglement between a subset of the nodes is produced continuously in the background. This can in principle allows the rapid creation of entanglement between more distant nodes using the already pre-generated entanglement pairs in the network. The second is an on-demand model, where entanglement production does not commence before a request is made. Our objective is to find protocols, that minimise the latency of the network to serve a request to create entanglement between two distant nodes in the network. We propose three routing algorithms and analytically show that as expected when there is only a single request in the network, then employing them on the continuous model yields a lower latency than on the on-demand one. We study the performance of the routing algorithms in a ring, grid, and recursively generated network topologies. We also give an analytical upper bound on the number of entanglement swap operations the nodes need to perform for routing entangled links between a source and a destination yielding a lower bound on the end to end fidelity of the shared entangled state. We proceed to study the case of multiple concurrent requests and show that in some of the scenarios the on-demand model can outperform the continuous one. Using numerical simulations on ring and grid networks we also study the behaviour of the latency of all the routing algorithms. We observe that the proposed routing algorithms behave far better than the existing classical greedy routing algorithm. The simulations also help to understand the advantages and disadvantages of different types of continuous models for different types of demands.
A network of devices capable of transmitting quantum information called a quantum network has promising applications with vast benefits. One of the most near term achievable application is the quantum key distribution. It could be used for sharing a secret key between two end-users through any insecure authenticated communication channel. Other than sharing a secret key, a quantum network can be used for connecting quantum computers. Quantum computers have the potential to solve computational problems that their classical counterparts would require significantly more time to do so. By connecting such devices, distributed computation problems such as leader election or distributed consensus between nodes can be solved securely. For such applications to be put into practice on a large scale, there are open practical questions still to be answered. In a quantum network, a data qubit containing quantum information is transmitted by an operation called quantum teleportation. For it, two nodes need to share entanglement. Quantum teleportation then ensures the safe transmission of a qubit by using the shared entanglement and the exchange of two classical bits. This operation, however, consumes entanglement between the nodes, changing the network topology with each served request. In quantum networks, certain nodes share entanglement between each other. Routing in quantum networks entails determining which of these shared entanglements are used to transmit quantum information. As this proves to be a difficult task, we study quantum networks and in particular consider the problem of routing entanglement in quantum networks. The average latency for routing entanglement in a quantum network has been studied so far using a distributed routing approach. Thus, we present numerical simulation results of centralised routing for the average latency of demands in two existing entanglement generation models. In the first, shared entanglement between nodes is created on-demand. In the second, certain nodes pre-share entanglement before the demand comes. Our results show the intuition that using a centralised routing approach in the on-demand model results in drastically more average latency than in the model with pre-shared entanglement. Since some nodes might not be informed about the change in topology, we study the effect of the propagation of information about the network topology to nodes in the network. Our observations based on simulation results show that the average latency is significantly higher if the information about the topology is not propagated well in the network. As propagating information to all nodes in a network would be a significant load for the network, we consider information propagation within a radius and still observe a considerable decrease in average latency. At last, we present a technique called link prediction which can be performed by any node without the need for information propagation and still achieve a considerable decrease in average latency. It can be effectively used to predict the change of topology in a quantum network by using knowledge about the network topology for a certain future point in time and previous knowledge about the network traffic.
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.
Quantum routing protocols seek to distribute entanglement across different nodes of a quantum network. A recently popular approach for quantum routing is to cut down the latency times for sharing entanglement by using virtual edges in addition to physical ones. While a physical edge is associated with the presence of a quantum channel, virtual edges correspond to pre-existing entanglement between some nodes which can be leveraged for entanglement swapping. Distributed routing protocols for quantum networks have been proposed and analyzed using this idea. These analyses have also been backed up by simulations. However, to the best of our knowledge, existing simulation approaches consider a static picture, where the demands for entangled pairs are presented upfront. In this paper, we study routing algorithms through time-driven simulations. Such an approach allows for the demands to emerge in real-time as the simulation proceeds, and therefore mimic realistic scenarios better. This also facilitates studying routing protocols in the presence of dynamic replenishment of entangled pairs, and exposes issues like occurrence of deadlocks in the context of limited quantum resources. As a demonstration of the approach, we show simulation results that analyze the performance of various physical and virtual graph topologies in terms of average latency time. Finally, we show the change in performance and network saturation in the presence of replenishment of entanglement resources.
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.
Quantum networks enable a number of important applications such as quantum key distribution. The basic function of a quantum network is to enable long-distance quantum entanglement between two remote communication parties. This work focuses on the entanglement routing problem, whose objective is to build long-distance entanglements for the concurrent source-destination pairs through multiple hops. Different from existing works 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 and new entanglement routing algorithms that utilize 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.