Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1610.05238

Shortcuts to quantum network routing

Eddie Schoute, Laura Mančinska, Tanvirul Islam, Iordanis Kerenidis, Stephanie Wehner

Published Oct 17, 2016• 95 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1610.05238

Related papers

Quantum network routing via link prediction

Antal Száva

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.

•Jan 1, 2019•0 citations

Distributed Routing in a Quantum Internet

Kaushik Chakraborty, Filip Rozpędek, Axel Dahlberg +1 more

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.

arXiv:1907.11630•Bulletin of the American Physical Society•Jul 26, 2019•101 citations

Concurrent Entanglement Routing for Quantum Networks

Shouqian Shi, Chen Qian

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.

ACM SIGCOMM Conference (SIGCOMM)•Jul 30, 2020•193 citations

Concurrent Entanglement Routing for Quantum Networks: Model and Designs

Shouqian Shi, Xiaoxue Zhang, Chen Qian

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.

IEEE/ACM Transactions on Networking•Jan 5, 2024•71 citations

Decentralized base-graph routing for the quantum internet

László Gyöngyösi, Sándor Imre

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.

arXiv:1801.02020•Physical Review A•Aug 10, 2018•91 citations

Swapping-Based Entanglement Routing Design for Congestion Mitigation in Quantum Networks

Zhonghui Li, Jian Li, Kaiping Xue +5 more

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.

IEEE Transactions on Network and Service Management•May 12, 2023•32 citations
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.
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.
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.
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 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.
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.