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.

AssumptionsEdit

  • 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.

OutlineEdit

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.

NotationEdit

  • Quantum network with topology described by two graphs:
  • A physical graph  
    •   represent quantum repeater nodes that can hold a small number of qubits.
    •   correspond to physical communication channels between nodes.
  • A virtual graph  
    •   represent virtual links, nodes that are not physically connected but share entanglement.
  •   is a   matrix representing the demands
    •   denotes the number of entangled links the source node   wants to share with destination node   at a specific point in time.
  •   denotes the maximum number of entangled links any two neighbour nodes   and   can share simultaneously.
  • The average latency (AL) is defined as:
  •  , where
    •   denotes the number of non-zero entries in  
    •   denotes the latency that a routing algorithm   takes to distribute   entangled link between the nodes   and  .

Protocol DescriptionEdit

  • All of the three routing algorithms are used as a subroutine ( ) 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  

  1.  
  2.  
  3. while   do
    1.  
    2.  
    3. if in   some of the neighbour nodes do not have enough entangled links then
      1. Generate all the missing links
    4. else
      1.  
      2. while   do
        1.  
        2. j = j + 1
      3. dem = dem - cap
      4. i = i + 1
  • During the path discovery phase ( ) 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   if   is an optimal neighbour of   to reach a destination node   then the routing algorithm has three options:
    • (1) Select the path via   and generate sufficient amount of links between   - 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.

PropertiesEdit

  • 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 InformationEdit

  • 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.

ReferencesEdit

  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