Editing Distributed Routing in a Quantum Internet

<!-- Intro: brief description of the protocol -->
This [https://arxiv.org/abs/1907.11630 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: related pages or category -->
'''Tags:'''  [[:Category: Multi Party Protocols|Multi Party]], [[:Category: Specific Task|Specific Task]].
==Assumptions==
<!-- It describes the setting in which the protocol will be successful. -->
* 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==
<!-- A non-mathematical detailed outline which provides a rough idea of the concerned protocol -->
In [https://arxiv.org/abs/1907.11630 (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==
<!--  Connects the non-mathematical outline with further sections. -->
* Quantum network with topology described by two graphs:
* A '''physical''' graph <math>G_{ph}=(V,E_{ph})</math>
** <math>V</math> represent quantum repeater nodes that can hold a small number of qubits.
** <math>E_{ph}</math> correspond to physical communication channels between nodes.
* A '''virtual''' graph <math>\mathcal{G}=(V,\mathcal{E})</math>
** <math>\mathcal{E}</math> represent ''virtual links'', nodes that are not physically connected but share entanglement.
* <math>D</math> is a <math>|V|\times|V|</math> matrix representing the demands
** <math>D_{i,j}</math> denotes the number of entangled links the source node <math>i \in V</math> wants to share with destination node <math>j \in V</math> at a specific point in time.
* <math>cap</math> denotes the maximum number of entangled links any two neighbour nodes <math>u</math> and <math>v</math> can share simultaneously.
* The ''average latency (AL)'' is defined as:
* <math>AL = \frac{1}{|D|} \sum_{i,j} T_{A,i,j}</math>, where
** <math>|D|</math>  denotes the number of non-zero entries in <math>D</math>
** <math>T_{A,i,j}</math> denotes the latency that a routing algorithm <math>\mathcal{A}</math> takes to distribute <math>D_{i,j}</math> entangled link between the nodes <math>i</math> and <math>j</math>.

<!--==Knowledge Graph==-->
<!-- Add this part if the protocol is already in the graph -->
<!--{{graph}}-->
==Protocol Description==
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->
* All of the three routing algorithms are used as a subroutine (<math>\mathbf{PathDisc}</math>) of '''Algorithm 1'''.
* The entire routing procedure between any two nodes can be subdivided into following three phases:
# Path discovery phase.
# Entanglement reservation phase.
# Entanglement distribution phase.

'''Algorithm 1''' - Distributed Routing Algorithm <math>(s, e, \mathcal{G}, D, cap)</math>
# <math>round = \lceil \frac{D_{s,e}}{cap} \rceil</math>
# <math>i = 1</math> 
# '''while''' <math> i \leq round</math> '''do'''
## <math>CommPath_{s,e} = \mathbf{PathDisc}(s, e, \mathcal{G}, D_{s,e})</math> 
## <math>CommPath_{s,e} = \{ s=u_0, u_1,...,u_{d-1} = e\}</math> 
## '''if''' in <math>CommPath_{s,e}</math> some of the neighbour nodes do not have enough entangled links '''then'''
### Generate all the missing links
## '''else'''
### <math>j=1</math> 
### '''while''' <math>j \leq d-2</math> '''do'''
#### <math>EntSwap(u_0,u_j,j_{j+1})</math> 
#### j = j + 1
### dem = dem - cap
### i = i + 1

* During the path discovery phase (<math>\mathbf{PathDisc}</math>) 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 <math>D_{v,e}</math> if <math>v</math> is an optimal neighbour of <math>u</math> to reach a destination node <math>e</math> then the routing algorithm has two options:
** (1) Select the path via <math>v</math> and generate sufficient amount of links between <math>u, v</math> - see '''Algorithm 2 - Modified Greedy'''
** (2) Vertex <math>u</math> try to select another neighbour with whom it already shares enough amount of entangled links - see '''Algorithm 3 - Local Best Effort'''

* Analyzing Algorithm 3 under the assumption that the quantum repeater nodes have information about its neighbours as well as the neighbours of the neighbours in the virtual graph is '''Algorithm 4 - NoN Local Best Effort'''.

==Properties==
<!-- important information on the protocol: parameters (threshold values), security claim, success probability... -->
* Various simulations of these protocols are presented in [https://arxiv.org/abs/1907.11630 (1)] comparing the [https://dl.acm.org/doi/abs/10.1145/335305.335325 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 [https://arxiv.org/abs/1801.02020 2] and [https://arxiv.org/abs/1610.05238 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==
<!-- theoretical and experimental papers including requirements, security proof (important), which protocol does it implement, benchmark values... -->
* [https://arxiv.org/abs/1610.05238 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==
# [https://arxiv.org/abs/1907.11630 Chakraborty et al. (2019)]
# [https://arxiv.org/abs/1801.02020 Gyongyosi and Imre (2018)]
# [https://arxiv.org/abs/1610.05238 Schoute et al. (2016)]

<div style='text-align: right;'>''contributed by Lucas Arenstein''</div>