Distributed Routing in a Quantum Internet

This example protocol (1) implements the task of Entanglement Routing. They develop routing protocols considering different types of path discovery algorithm 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 start 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.

Tags: Multi Party, Specific Task.

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 have local state information of the other nodes states.

Outline

In (1) they develop 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. They consider 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 that in principle allows the rapid creation of entanglement between distant nodes using the already pre-generated entanglement pairs and a on-demand model, where entanglement production does not commence before a request is made. Their distributed routing algorithm is studied considering three different path discovery algorithms: Modified Greedy Routing, Local Best Effort Routing and NoN Local Best Effort Routing. All of these strategies are simulated on the ring, grid and recursively generated network topology.

Notation

• Quantum network with topology described by two graphs:
• A physical graph $G_{ph}=(V,E_{ph})$
  • $V$ represent quantum repeater nodes that can hold a small number of qubits.
  • $E_{ph}$ correspond to physical communication channels between nodes.
• A virtual graph ${\mathcal {G}}=(V,{\mathcal {E}})$
  • ${\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 neighbour 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 link between the nodes $i$ and $j$.

Protocol Description

• All of the three routing algorithms are used as a subroutine ($\mathbf {PathDisc}$) of Algorithm 1.
• The entire routing procedure between any two nodes can be subdivided into following three phases:

1. Path discovery phase.
2. Entanglement reservation phase.
3. Entanglement distribution phase.

Algorithm 1 - Distributed Routing Algorithm $(s,e,{\mathcal {G}},D,cap)$

1. $round=\lceil {\frac {D_{s,e}}{cap}}\rceil$
2. $i=1$
3. while $i\leq round$ do
   1. $CommPath_{s,e}=\mathbf {PathDisc} (s,e,{\mathcal {G}},D_{s,e})$
   2. $CommPath_{s,e}=\{s=u_{0},u_{1},...,u_{d-1}=e\}$
   3. if in $CommPath_{s,e}$ some of the neighbour nodes do not have enough entangled links then
      1. Generate all the missing links
   4. else
      1. $j=1$
      2. while $j\leq d-2$ do
         1. $EntSwap(u_{0},u_{j},j_{j+1})$
         2. j = j + 1
      3. dem = dem - cap
      4. i = i + 1

• During the path discovery phase ($\mathbf {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:
  • (1) Select the path via $v$ and generate sufficient amount of links between $u,v$ - see Algorithm 2 - Modified Greedy
  • (2) Try to select another neighbour with whom it already shares enough amount of entangled links - see Algorithm 3 - Local Best Effort
  • (3) (2) + Assume that the quantum repeater nodes have information about its neighbours as well as the neighbours of the neighbours in the virtual graph - see Algorithm 4 - NoN Local Best Effort.

Properties

• Various simulations of these protocols are presented in (1) comparing the classical greedy routing algorithm and algorithms 2, 3 and 4 considering the continuous and on-demand model of the network with multiple sources of destinations 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.

Further Information

• Schoute et al. (2016) 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 destination pair in a network. Multi-path routing algorithms are useful for sharing entangled links between a source destination pair. However, this type of approach is not scalable for a larger network with multiple demands.

References

1. Chakraborty et al. (2019)
2. Gyongyosi and Imre (2018)
3. Schoute et al. (2016)

Contributed by Lucas Arenstein during the QOSF Mentorship Program

Mentor: Shraddha Singh