Editing Routing Entanglement in the Quantum Internet (section)

==Protocol Description==
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->

* All of the three protocols below assume that time is slotted and each memory can hold a qubit perfectly for <math>T \geq 1</math> time slot before the stored qubit completely decoheres.
* Each time slot <math>t</math>, <math>t=1,2,... </math> is divided into 2 phases:
* '''External Phase:'''
** Each of the <math>S(e)</math> pairs of memories across and edge <math>e</math> attempts to establish an EPR pair.
*:- An entanglement attempt across any one of the <math>S(e)</math> parallel links across edge <math>e</math> succeeds with probability <math>p_0(e) \sim \eta(e)</math>, where <math>\eta(e) \sim e^{-\alpha L_e}</math> <!--is the transmissivity of a lossy optical channel of length <math>L(e)</math>.-->
*:- The probability that one or more ebits are established across an edge <math>e</math> is <math>p(e)=1-(1-p_0)^{S(e)}</math>.
*:- Assuming <math>S(e)=S,</math> give us <math>p(e)=p,</math> <math>\forall e \in E</math>.
** Using two-way classical communication over an edge <!--<math>e(u, v)</math>-->, neighboring repeater nodes <!--<math>u, v</math>--> learn which of the S(e) (if any) succeeded in the external phase, in a given time slot.

* '''Internal Phase:'''
** BSMs are attempted locally at each repeater node between pairs of qubit memories based on the success and failure of the neighboring links in the external phase.
*:- These BSM attempts are called internal links, i.e., links between memories internal to a repeater node.
*:- Each of these internal-link attempts succeed with probability <math>q</math>.

At the end of one time-slot a along a path comprising of <math>k</math> edges (and thus <math>(k-1)</math> repeater nodes) one ebit is successfully shared between the end points of the path with probability <math>p^k q^{k-1}</math>.

The maximum number of ebits that can be shared between node <math>a</math> and node <math>b</math> after one time-slot is <math>min\{d(a), d(b)\}</math>, assuming <math>S</math> is the same over all edges.

The protocols described below focus on finding the optimal strategy for each repeater node in order to decide which locally held qubits to attempt BSMs during the internal phase of a
time slot. Based on the outcomes of the external phase and considering global or local link-state knowledge and <math>K</math>.

===Multipath Routing of a Single Entanglement Flow===
'''Input:''' <math>K=1</math>, Source-Destination pair <math>(A_1, B_1)</math>.

'''Output:''' Quantum network with ebits shared between the end points of <math>(A_1, B_1)</math>.

====Protocol for Entanglement Routing with Global Link-state Information====
After the External Phase
# <math>m = 1</math>
# <math>G_m</math> = Subgraph induced by the successful external links and the repeater nodes after the external phase.
# While (True):
## <math>S_m</math> = shortest path in <math>G_m</math> connecting <math>A_1</math> with <math>B_1</math>. 
## If <math>S_m</math> is empty: Break While Loop.
## Else:
### Set <math>L_m</math> as the length of <math>S_m</math>.
### Try connecting all internal links along the nodes of <math>S_m</math> <br />//successfully generating an ebit between <math>A_1</math> and <math>B_1</math> with probability <math>q^{L_m - 1}</math>
## <math>G_{m+1}</math> = <math>G_m -</math> all external and internal links of <math>S_m</math>.
## <math>m = m + 1.</math> 

====Protocol for Entanglement Routing with Local Link-state Information====

Knowledge of success and failure of the External Phase is communicated only to the two repeater nodes connected by the link.
Repeater nodes need to decide on which pair(s) of memories BSMs should be attempted (which internal links to attempt), based only on information about the states of external links adjacent to them.

After the External Phase
# For every repeater except <math>A_1</math> and <math>B_1</math>: <br /> Let <math>u</math> be the node of this iteration.
## If less than one of the neighboring external links is successful: <br />Then no internal links are attempted since this repeater node can not be part of a path from <math>A_1</math> to <math>B_1</math>.
## Else If two or more neighboring external links are successful: <br />Then let <math>v</math> be the node linked to <math>u</math> with the smallest <math>d_{A_1}</math> and <math>w</math> be the node linked to <math>u</math> with the smallest <math>d_{B_1}</math>. <br /> Attempt a BSM on node <math>u</math> on the memories connected to <math>v</math> and <math>w</math>.
### Else If four neighboring external links are successful: <br /> Then attempt a BSM on node <math>u</math> on the remaining memories disconsidering the two memories from the previous step. 

===Protocol for Simultaneous Entanglement Flows with Link-state Information===
'''Input:''' <math>K=2</math>, Source-Destination pairs <math>(A_1, B_1)</math> and <math>(A_2, B_2)</math>.

'''Output:''' Quantum network with ebits shared between the end points of <math>(A_1, B_1)</math> and <math>(A_2, B_2)</math>.

This situation motivates the '''Multi-ﬂow Spatial-division''' rule which divides the the network between two spatial regions corresponding to the two flows.

* When the shortest path connecting the two source-destination pairs '''do not''' cross the network is divided between two spatial regions corresponding to the two ﬂows.
** For each one of this regions we apply the Protocol for Entanglement Routing with Local Link-state Information.

* When the shortest path connecting the two source-destination pairs '''do''' cross the network is divided between two spatial regions corresponding to the two ﬂows.
** Considering the square-grid topology the two spatial regions are divided by two crossing lines with an angle <math>\theta</math> between them (forming a hourglass shape).
** For each one of this regions we apply the Protocol for Entanglement Routing with Local Link-state Information.