Revision History for: Distributed Routing in a Quantum Internet
- 2025-06-24 at 21:45 by JuliaM
implements Entanglement Routing
Introduction
This protocol [1] implements the functionality of Entanglement Routing. They develop routing protocols considering different types of path discovery algorithms, considering a continuous model in which entanglement between a subset of the nodes is produced continuously in the background and an on-demand model where entanglement production starts when a request is made. Their protocols work on any network topology but are analyzed in the ring, grid and recursively generated network topology. Their quantum repeater nodes have local state information of the other nodes’ states.
Outline
This protocol develops routing algorithms with the goal of minimizing the latency of the network to serve a request to create entanglement between two distant nodes in the network. It considers two models for the operation of the quantum network:
- A continuous model, in which entanglement between a subset of the nodes is produced continuously in the background, which in principle allows the rapid creation of entanglement between distant nodes using the already pre-generated entanglement pairs and
- An on-demand model, where entanglement production does not commence before a request is made.
The distributed routing algorithm is studied considering three different path discovery algorithms:
- Modified Greedy Routing
- Local Best Effort Routing
- NoN Local Best Effort Routing.
All of these strategies are simulated on the ring, grid and recursively generated network topology.
Assumptions
- Each quantum repeater node is equipped with:
- Quantum memories that can store a small number of qubits for some predefined time.
- Entanglement sources.
- Ability to perform Entanglement Swapping between any pair of qubits of the network
- Classical computing resources and communication interface.
- Each quantum repeater node is aware of the overall network topology and has local state information of the other nodes’ states.
Requirements
Network Stage: Entanglement generation
Notation
- Quantum network with topology described by two graphs:
- A physical graph $G_{ph} = (V, E_{ph})$, where $V$ represent quantum repeater nodes that can hold a small number of qubits, and $E_{ph}$ corresponds to physical communication channels between nodes.
- A virtual graph $\\\mathcal{G} = (V, \\\mathcal{E})$, where $\\\mathcal{E}$ represent virtual links, nodes that are not physically connected but share entanglement.
- $D$ is a $|V| \\\times |V|$ matrix representing the demands. $D_{i,j}$ denotes the number of entangled links the source node $i \\\in V$ wants to share with destination node $j \\\in V$ at a specific point in time.
- $cap$ denotes the maximum number of entangled links any two neighbouring nodes $u$ and $v$ can share simultaneously.
- The average latency (AL) is defined as:
$$AL = \\\frac{1}{|D|} \\\sum_{i,j} T_{A,i,j}$$
where:
$|D|$ denotes the number of non-zero entries in $D$.
$T_{A,i,j}$ denotes the latency that a routing algorithm $\\\mathcal{A}$ takes to distribute $D_{i,j}$ entangled links between the nodes $i$ and $j$.
Properties
- Various simulations of these protocols are presented in[1] comparing the classical greedy routing algorithm [2] and algorithms 2, 3 and 4, considering the continuous and on-demand model of the network with multiple source-destination pairs in the Ring and Grid topology.
- The main differences between the approaches in 2 and 3, and this paper is that in this model they put an upper bound on the distance (relative to the physical graph) of a pre-shared entangled link and put an upper bound on the storage time of the entangled link in a quantum memory making the model more realistic.
Technical Description
All three routing algorithms are used as a subroutine ($\\\mathtt{PathDisc}$) of Algorithm 1.
The entire routing procedure between any two nodes can be subdivided into the following three phases:- Path discovery phase.
- Entanglement reservation phase.
- Entanglement distribution phase.
Algorithm 1: Distributed Routing Algorithm $(s,e,{\\\mathcal{G}},D,cap)$
- $round = \\\lceil \\\frac{D_{s,e}}{cap} \\\rceil$, $i=1$
while $i \\\leq round$ do:- $CommPath_{s,e} = \\\mathtt{PathDisc}(s,e,{\\\mathcal{G}},D_{s,e})$
- $CommPath_{s,e} = \\\{s = u_0, u_1, …, u_{d-1} = e \\\}$
- if: in $CommPath_{s,e}$ some of the neighbour nodes do not have enough entangled links then:
- Generate all the missing links
- else
- $j=1$
- while $j \\\leq d-2$ do:
- $EntSwap(u_0, u_j, j_{j+1})$
- $j = j + 1$
- $dem = dem – cap$
- $i = i + 1$
During the path discovery phase ($\\\mathtt{PathDisc}$) each node decides the next hop on the basis of the physical graph topology and the information it has about the shared entangled links with its neighbours.
In this phase, given a demand $D_{v,e}$, if $v$ is an optimal neighbour of $u$ to reach a destination node $e$, then the routing algorithm has three options:
- Select the path via $v$ and generate a sufficient number of links between $u, v$ – see Algorithm 2 – Modified Greedy in [1].
- Try to select another neighbour with whom it already shares enough amount of entangled links – see Algorithm 3 – Local Best Effort in [1].
- Assume that the quantum repeater nodes have information about their neighbours as well as the neighbours of the neighbours in the virtual graph – see Algorithm 4 – NoN Local Best Effort in [1].
Experimental Implementations
No content has been added to this section, yet!
Further Information
- Schoute et al. (2016)[3] introduce and formalize some of the concepts presented in this work.
- In “Routing Entanglement in the Quantum Internet”, Pant et al. proposed a greedy multi-path routing algorithm for distributing entanglement between a source and destination pair in a network. Multi-path routing algorithms are useful for sharing entangled links between a source and destination pair. However, this type of approach is not scalable for a larger network with multiple demands.
References
- Chakraborty, Kaushik, Filip Rozpedek, Axel Dahlberg, and Stephanie Wehner. “Distributed routing in a quantum internet.” arXiv preprint arXiv:1907.11630 (2019).
- Kleinberg, Jon. “The small-world phenomenon: An algorithmic perspective.” In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp. 163-170. 2000.
- Srivastava, Anubhav, Devendra Mishra, Madhuri Annavazzala, Antony Franklin, Nixon Patel, and MV Panduranga Rao. “Short-cuts on quantum network simulators.” In 2021 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS), pp. 372-377. IEEE, 2021.
- 2025-05-16 at 13:58 by Mina Doosti
implements Entanglement Routing
Introduction
This protocol [1] implements the functionality of Entanglement Routing. They develop routing protocols considering different types of path discovery algorithms, considering a continuous model in which entanglement between a subset of the nodes is produced continuously in the background and an on-demand model where entanglement production starts when a request is made. Their protocols work on any network topology but are analyzed in the ring, grid and recursively generated network topology. Their quantum repeater nodes have local state information of the other nodes’ states.
Outline
This protocol develops routing algorithms with the goal of minimizing the latency of the network to serve a request to create entanglement between two distant nodes in the network. It considers two models for the operation of the quantum network:
- A continuous model, in which entanglement between a subset of the nodes is produced continuously in the background, which in principle allows the rapid creation of entanglement between distant nodes using the already pre-generated entanglement pairs and
- An on-demand model, where entanglement production does not commence before a request is made.
The distributed routing algorithm is studied considering three different path discovery algorithms:
- Modified Greedy Routing
- Local Best Effort Routing
- NoN Local Best Effort Routing.
All of these strategies are simulated on the ring, grid and recursively generated network topology.
Assumptions
- Each quantum repeater node is equipped with:
- Quantum memories that can store a small number of qubits for some predefined time.
- Entanglement sources.
- Ability to perform Entanglement Swapping between any pair of qubits of the network
- Classical computing resources and communication interface.
- Each quantum repeater node is aware of the overall network topology and has local state information of the other nodes’ states.
Requirements
Network Stage: Entanglement generation
Notation
- Quantum network with topology described by two graphs:
- A physical graph $G_{ph} = (V, E_{ph})$, where $V$ represent quantum repeater nodes that can hold a small number of qubits, and $E_{ph}$ corresponds to physical communication channels between nodes.
- A virtual graph $mathcal{G} = (V, mathcal{E})$, where $mathcal{E}$ represent virtual links, nodes that are not physically connected but share entanglement.
- $D$ is a $|V| times |V|$ matrix representing the demands. $D_{i,j}$ denotes the number of entangled links the source node $i in V$ wants to share with destination node $j in V$ at a specific point in time.
- $cap$ denotes the maximum number of entangled links any two neighbouring nodes $u$ and $v$ can share simultaneously.
- The average latency (AL) is defined as:
$$AL = frac{1}{|D|} sum_{i,j} T_{A,i,j}$$
where:
$|D|$ denotes the number of non-zero entries in $D$.
$T_{A,i,j}$ denotes the latency that a routing algorithm $mathcal{A}$ takes to distribute $D_{i,j}$ entangled links between the nodes $i$ and $j$.
Properties
- Various simulations of these protocols are presented in[1] comparing the classical greedy routing algorithm [2] and algorithms 2, 3 and 4, considering the continuous and on-demand model of the network with multiple source-destination pairs in the Ring and Grid topology.
- The main differences between the approaches in 2 and 3, and this paper is that in this model they put an upper bound on the distance (relative to the physical graph) of a pre-shared entangled link and put an upper bound on the storage time of the entangled link in a quantum memory making the model more realistic.
Technical Description
All three routing algorithms are used as a subroutine ($mathtt{PathDisc}$) of Algorithm 1.
The entire routing procedure between any two nodes can be subdivided into the following three phases:- Path discovery phase.
- Entanglement reservation phase.
- Entanglement distribution phase.
Algorithm 1: Distributed Routing Algorithm $(s,e,{mathcal{G}},D,cap)$
- $round = lceil frac{D_{s,e}}{cap} rceil$, $i=1$
while $i leq round$ do:- $CommPath_{s,e} = mathtt{PathDisc}(s,e,{mathcal{G}},D_{s,e})$
- $CommPath_{s,e} = {s = u_0, u_1, …, u_{d-1} = e }$
- if: in $CommPath_{s,e}$ some of the neighbour nodes do not have enough entangled links then:
- Generate all the missing links
- else
- $j=1$
- while $j leq d-2$ do:
- $EntSwap(u_0, u_j, j_{j+1})$
- $j = j + 1$
- $dem = dem – cap$
- $i = i + 1$
During the path discovery phase ($mathtt{PathDisc}$) each node decides the next hop on the basis of the physical graph topology and the information it has about the shared entangled links with its neighbours.
In this phase, given a demand $D_{v,e}$, if $v$ is an optimal neighbour of $u$ to reach a destination node $e$, then the routing algorithm has three options:
- Select the path via $v$ and generate a sufficient number of links between $u, v$ – see Algorithm 2 – Modified Greedy in [1].
- Try to select another neighbour with whom it already shares enough amount of entangled links – see Algorithm 3 – Local Best Effort in [1].
- Assume that the quantum repeater nodes have information about their neighbours as well as the neighbours of the neighbours in the virtual graph – see Algorithm 4 – NoN Local Best Effort in [1].
Experimental Implementations
No content has been added to this section, yet!
Further Information
- Schoute et al. (2016)[3] introduce and formalize some of the concepts presented in this work.
- In “Routing Entanglement in the Quantum Internet”, Pant et al. proposed a greedy multi-path routing algorithm for distributing entanglement between a source and destination pair in a network. Multi-path routing algorithms are useful for sharing entangled links between a source and destination pair. However, this type of approach is not scalable for a larger network with multiple demands.
References
- Chakraborty, Kaushik, Filip Rozpedek, Axel Dahlberg, and Stephanie Wehner. “Distributed routing in a quantum internet.” arXiv preprint arXiv:1907.11630 (2019).
- Kleinberg, Jon. “The small-world phenomenon: An algorithmic perspective.” In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp. 163-170. 2000.
- Srivastava, Anubhav, Devendra Mishra, Madhuri Annavazzala, Antony Franklin, Nixon Patel, and MV Panduranga Rao. “Short-cuts on quantum network simulators.” In 2021 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS), pp. 372-377. IEEE, 2021.