Distributed Routing in a Quantum Internet
Kaushik Chakraborty Filip Rozpedek Axel Dahlberg Stephanie Wehner
quant-ph cs.NI



[
    Christopher J. Moore
    December 30, 2023
========================





We develop new routing algorithms for a quantum network with noisy quantum devices such that each can store a small number of qubits.
We thereby consider two models for the operation of such a network. The first is a continuous model, in which entanglement between a subset of the nodes is produced continuously in the background. This can in principle allows the rapid creation of entanglement between more distant nodes using the already pre-generated entanglement pairs in the network.
The second is an on-demand model, where entanglement production does not commence before a request is made. 
Our objective is to find protocols, that minimise the latency of the network to serve a request to create entanglement between two distant nodes in the network. 
We propose three routing algorithms and analytically show that as expected when there is only a single request in the network, then employing them on the continuous model yields a lower latency than on the on-demand one. We study the performance of the routing algorithms in a ring, grid, and recursively generated network topologies. We also give an analytical upper bound on the number of entanglement swap operations the nodes need to perform for routing entangled links between a source and a destination yielding a lower bound on the end to end fidelity of the shared entangled state. We proceed to study the case of multiple concurrent requests and show that in some of the scenarios the on-demand model can outperform the continuous one.
Using numerical simulations on ring and grid networks we also study the behaviour of the latency of all the routing algorithms. We observe that the proposed routing algorithms behave far better than the existing classical greedy routing algorithm. The simulations also help to understand the advantages and disadvantages of different types of continuous models for different types of demands.










§ INTRODUCTION


The goal of a quantum internet <cit.> is to enable the transmission of quantum bits (qubits) between distant quantum devices to achieve the tasks that are impossible using classical communication. For example, with such a network we can implement cryptographic protocols like long-distance quantum key distribution (QKD) <cit.>, which enables secure communication. Apart from QKD, many other applications in the domain of distributed computing and multi-party cryptography <cit.> have already been identified at different stages of quantum network development <cit.>.

Like the classical internet, a quantum internet consists of the network components like physical communication links, and eventually routers  <cit.>. However, due to fundamental differences between classical and quantum bits, these components in a quantum network behave rather differently than their classical counterparts. For example, qubits cannot be copied, which rules out retransmission as a means to overcome qubit losses <cit.>. To nevertheless send qubits reliably, a standard method is to first produce quantum entanglement between a qubit held by the sender and a qubit held by the receiver. Once this entanglement has been produced, the qubit can then be sent using quantum teleportation <cit.>. This requires, in addition, the transmission of two classical bits per qubit from the sender to the receiver. Importantly, teleportation consumes the entanglement, meaning that it has to be re-established before the next qubit can be sent. When it comes to routing qubits in a network, one hence needs to consider routing entanglement <cit.>.

An important tool for establishing entanglement over long distances is the notion of entanglement swapping. If two nodes A and B are both connected to an intermediary node r, but not directly connected themselves by a physical quantum communication channel such as fiber, then A and B can nevertheless create entanglement between themselves with the help of r. First, A and B each individually create entanglement with r. This requires one qubit of quantum storage at A and B to hold their end of the entanglement, and two qubits of quantum storage at r. Node r then performs an entanglement swap <cit.>, destroying its own entanglement with A and B, but instead creating entanglement between A and B. This process can be understood as node r teleporting its qubit entangled with A onto node B using the entanglement that it shares with B. In turn, using this process iteratively, node r can with the assistance of A and B, also establish entanglement with nodes that are far away in the physical communication network. Any node r capable of storing qubits can thus simultaneously be entangled with as many nodes in the network as it can store qubits in its quantum memory. Such a node may function as an entanglement router by taking decisions for which of its neighbours it should perform an entanglement swap operation for sharing an entangled link between a source s and a destination e (see <cit.> for a longer introduction).

In the domain of quantum information we use the term quantum state to represent the state of a multi-qubit quantum system. A pure n-qubit quantum state |ψ_n⟩ can be mathematically described as a unit vector in a Hilbert space ℋ of dimension 2^n. The entangled target state |ψ^+⟩ = 1/√(2)(|00⟩_AB + |11⟩_AB)
is a pure quantum state of two qubits A and B. An n-qubit mixed state ρ_n on ℋ is a Hermitian operator with unit
trace. ρ_n is called as density matrix. A mixed state is a generalisation of a pure state that can model noisy quantum states, and the density matrix
representation ρ of a pure state |ψ⟩ is |ψ⟩⟨ψ|, where ⟨ψ|
is the transpose of the complex conjugate of |ψ⟩. In this
paper, we use the quantity, known as fidelity to measure the closeness
between two quantum states. The fidelity between a target pure state |ψ⟩ and a mixed state ρ is defined as F(ρ, |ψ⟩⟨ψ|) = ⟨ψ|ρ |ψ⟩. The mixed state ρ has a unit trace and |ψ⟩ is a unit vector, which implies 0 ≤ F(ρ, |ψ⟩⟨ψ|) ≤ 1. Moreover, F(ρ, |ψ⟩⟨ψ|) =1 if and only if ρ = |ψ⟩⟨ψ|. This implies that two states with high fidelity are close to each other. In this paper, we mostly consider the depolarising channels and for this type of channels, if a node r performs a noise free entanglement swap operation between two entangled links with fidelity F_1, F_2 then the fidelity of the resulting entangled state is at least F_1F_2 <cit.>. 


A quantum network may generate entanglement on the demand only when a request arrives, which we call the on-demand model. In this case, the routing problem reduces to routing entanglement on the physical communication graph (G_ = (V, E_)) corresponding to the fibres (or free-space links) connecting the quantum network nodes. This means that entanglement is produced by two nodes connected in G_ followed by entanglement swapping operations along a path in this graph [In this case the nodes discover a path from a source s to a destination e in G_ and use any entanglement distribution scheme (e.g. the schemes proposed in <cit.>) in a repeater chain for generating entanglement between s and e.]. Two such neighbour nodes in G_ are called physical neighbours of each other. However, we may also pre-establish entanglement between two nodes which do not share a physical connection, in anticipation of future requests. Such pre-shared entanglement forms a virtual link <cit.>. Two such nodes, who are not directly connected by a physical link but share an entangled link or a virtual link, are called virtual neighbours of each other. Here, we consider routing on the virtual graph given by pre-shared entanglement (= (V,  )). This virtual graph may have much lower diameter than the underlying physical one. Such virtual links are in spirit similar to forming an overlay network in peer-to-peer networks <cit.>, with the important distinction that the graph is highly dynamic: each virtual link can be used only once and it must be re-established before further use. This can be a very time-consuming process. What's more, due to short lifetimes of quantum memories the virtual graph is continuously changing as virtual links expire after some time even if they have not been used.

Of course, on both graphs, one can nevertheless apply classical algorithms to select a path from the sender to the receiver, along which entanglement swapping is performed to create an end to end link. The performances of the centralised shortest path routing algorithms <cit.> are highly dependent on the network topology. If the topology changes rapidly then keeping the routing tables up to date becomes challenging. This type of situation also occurs in classical delay-tolerant networks <cit.>. Usually, for this type of network, the distributed routing algorithms <cit.> always perform better than the centralised shortest path algorithm <cit.>. Hence, in this paper, we address the routing problem by modifying existing classical distributed routing algorithms. The main challenge for designing such algorithms is that the nodes need to decide which operation to perform (entanglement generation or entanglement swap) based on local information. Analysing those routing algorithms for multiple demands is also a challenging task. In this paper we use the mathematical tools from classical routing theory <cit.> for computing the latency of our proposed routing algorithms for single source and destination pairs. We use numerical simulations for analysing the performances in case of multiple source and destination pairs. 









 


§ RELATED WORK


In this paper, we focus on the classical decision making procedure for distributing entanglement in an arbitrary network. The underlying physical mechanism for distributing entanglement in a simple quantum network has a long literature. Distributing entanglement in a simple chain network has been studied before, see e.g., <cit.> (see <cit.> for a review). The authors of <cit.> studied the problem of entanglement distribution from a percolation theory point of view. In their model, first they considered a physical graph and from there they constructed the virtual graph by assuming that two physically connected nodes can have a weakly entangled link with a probability . Given such a virtual graph (which may be disconnected) they were interested in finding whether there exists a path in the virtual graph between any source and destination pair. Their proposed solutions are highly dependent on  and the connectivity of the virtual graph, however, they did not propose any specific routing algorithms in their paper that can find a path between the source and the destination. In <cit.> the researchers proposed solutions for distributing entanglement in a noisy network using the concept of quantum network coding. All of these approaches were based on the specific structure of the physical graphs and manipulation of multi-partite entangled states. However, with current day technologies, these solutions are very difficult to realise in practice.

On the other hand, the routing approaches in <cit.> are based on classical techniques and these are arguably more likely to be implemented with the near future quantum technology. In all of these approaches, first, the nodes discover a path from a source to a destination and then distribute the entangled links along the path. The difference between these approaches comes from the path selection algorithms. For example, in <cit.> Van Meter et al. defined a cost metric across each communication link and then used Dijkstra's algorithm <cit.> to find an optimal path between a source and a destination. In <cit.> Caleffi proposed a routing algorithm that tries to find an optimal path between a source and a destination based on a route metric called end-to-end entanglement rate. However, both of the path selection algorithms are centralised algorithms and work under the assumption that each node has information about the entire network. In <cit.> 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 approaches is not scalable for a larger network with multiple demands. 

In <cit.> the researchers were interested in finding routing algorithms in a virtual graph. In <cit.> Schoute et al. first showed that an efficient construction of the virtual graph can reduce the latency rapidly. In both <cit.> the researchers first defined a physical graph (mostly ring and grid topology) and classified the nodes into different levels according to their entanglement generation capabilities and then from that physical graph, they constructed a virtual graph, using the concept of a small-world network, proposed in <cit.>. Later they used a classical distributed greedy routing algorithm for routing. The main contribution of <cit.> was to adopt the techniques proposed in <cit.> for constructing the virtual graph in a decentralised fashion.

The main differences between the approaches in <cit.>, and this paper is that in our model we 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. This makes our model more realistic. Besides this, we show that due to the dynamic nature of the virtual graph topology, certain routing strategies for the classical network do not work efficiently for a high number of demands and we also propose two new routing algorithms that work better than the one used in the classical case. One can find more details about our contributions in the next sections.




§ SUMMARY OF OUR RESULTS


The main contributions in this paper can be subdivided into three parts. In the first part, we propose different types of continuous model networks based on the choice of virtual neighbours. The entangled links between two virtual neighbours can reduce the diameter of the virtual graph, and increase the connectivity of the network. Inspired by complex network theory, we propose the following ways of choosing virtual neighbours.


  * Deterministically chosen virtual neighbours, where each node, chooses its virtual neighbours using a fixed deterministic strategy depending on the topology. We call this type of virtual graph a deterministic virtual graph.

  * Randomly chosen virtual neighbours, where each node samples its virtual neighbours using a probability distribution, defined over the set of nodes. Here we study the following two such sampling distributions. We call this type of virtual graph as random virtual graph.
 

  * Virtual neighbours are chosen following the uniform distribution: In this type of network, each node chooses its virtual neighbour uniformly randomly among all the nodes which are at most d_ distance from it. In the literature of the random graph, this type of virtual neighbours can reduce the diameter of the virtual graph.

  * Virtual neighbours are chosen following the power law distribution: In this type of network,  each node chooses its virtual neighbour among all the nodes at a distance at most d_ following a power-law distribution. In the literature of small-world networks, it is well known that for certain kind of physical graph topologies, this type of virtual neighbours exponentially reduces the diameter of the virtual graph <cit.>. However, in small-world networks, there is no such concept of d_ and all the virtual links are permanent in nature. These make our construction different from the construction of <cit.>. These differences in the construction also have a significant impact on the design and analysis of the routing algorithms.  


For details explanation we refer to section <ref>.


In the second part, we present the design and analysis of the distributed routing algorithms. In section <ref> we propose the following two routing algorithms.


  * Modified greedy routing algorithm.

  * Local best effort routing algorithm.


The main structure of all of the proposed algorithms is similar and it is described in algorithm <ref>. Both of the algorithms can be used in the continuous and on-demand model on any topology and use only local information of the virtual network topology. After getting a demand or request, they discover a path from the source to the destination and reserve the required amount of entanglement across the path. All of the nodes wait until the path is discovered. The one disadvantage of this type of approach is that, if the memory storage time is not large enough, then all of the reserved links might decohere when the path has been discovered. In this paper, we assume that the memory storage time is much longer compared to the classical path discovery time. After the path discovery, if all of the links are available then the intermediate nodes along the path performs entanglement swap. It might happen that due to decoherence, some of the links along the path becomes unusable. In that case, the demand waits until all of the links are being generated. In algorithm <ref> only the path discovery procedure behaves differently in two different algorithms. 

Later in algorithm <ref> we propose another version of the local best effort algorithm, where we assume that each node has the information about the virtual graph up to two hops from itself. For the details of these algorithms, we refer to algorithm <ref> (modified greedy) and <ref> (local best effort), <ref> (NoN local best effort). In section <ref> we analytically show that for a single demand, continuous networks can reduce the latency rapidly compared to the on-demand network. In lemma <ref> we show that the number of entangled links any two nodes can share using the existing pre-shared entangled links in the continuous model is lower bounded by the minimum edge cut of the virtual graph. Later in section <ref> we focus our studies on more structured network topologies, like the ring, grid, and recursively generated networks. For the continuous model, we give an analytical upper bound on the number of entanglement swap operations that the nodes have to perform for sharing an entangled link between a source-destination pair. The bounds are given in table <ref>. Based on the results in table <ref>, in lemma <ref> we give a lower bound on the fidelity of the entangled state shared between any source and destination pair. This lower bound shows that for large d_ the end to end fidelity of the shared entangled state is inversely proportional to the diameter of the ring and grid network. Then we study the behaviour of the proposed routing algorithms and compare their performances with the existing classical routing algorithm for multiple source-destination pairs. Using numerical simulations, we observe the latency of the routing algorithms in the following scenarios as a function of the number of demands. Here we consider set of demands as a |V| × |V| matrix D, where (i,j)-th entry D_i,j denotes the number of entangled links the source node i ∈ V wants to share with destination node j ∈ V at a specific point in time. The summary of our main observations is given below.
 

  * The latency for classical greedy routing algorithm behaves similarly to the other proposed routing algorithms if the number of demands is small. However, the latency increases rapidly with a higher number of demands. We refer to figure <ref>, <ref>, <ref> for the plots regarding this simulation. This simulation shows the importance of designing new routing algorithms for a quantum internet.

  * All of the proposed routing algorithms perform much better in the continuous model compared to the on-demand one if the demand is low. I.e., D_i,j≪ cap where cap denotes the maximum number of entangled links any two neighbour nodes u and v can share simultaneously. We refer to figure <ref> for the plots regarding this simulation.

  * If each demand asks for more entangled links then in figure <ref> we observe that in a ring network the deterministic virtual graph performs better than the random ones when the total number of demands is very high. However, for the grid network, the situation is opposite. For more detail, regarding this observation, we refer to section <ref>.

  * Here we also study the performance of the routing algorithms for different continuous models when each of the demands has a high distance in the physical graph. In figure <ref> we observe that this simulation behaves similarly to the simulation of figure <ref>.

 


In the third part, we study our routing algorithms in a heterogeneous network, where the nodes can be classified into several groups based on their entanglement generation capacity. We use the concept of recursively generated graphs for studying such networks. The key idea behind this type of graphs is that first, we start with an initial graph G_0 and if any subgraph of G_0 has certain structure then we substitute each of the edges of that subgraph with another graph. We call this operation as edge substitution. Thus by repeating this procedure recursively we generate the final graph. In lemma <ref> we show that the diameter of such recursively generated physical graph increases exponentially with the number of recursive steps. Here, we also propose strategies to construct the corresponding virtual graph and for a single demand, we analytically compute the latency for distributing entangled link between any source-destination pair.
















§ NOTATIONS AND DEFINITIONS


In this paper we are interested in computing the latency of a demand. Let a routing algorithm 𝒜 takes T_𝒜,i,j time steps to distribute D_i,j number of entangled links between the source node i and destination node j. If |D| denotes the number of non-zero entries in D then with respect to a routing algorithm 𝒜 we define average latency (AL) as follows,

    AL = 1/|D|∑_i,jT_𝒜,i,j,

where T_𝒜,i,j denotes the latency to distribute D_i,j entangled link between the nodes i and j. In this paper, for a graph G, we use _G(u,v), _G, _G(u) to denote hop distance between two nodes u,v in G, diameter of G and set of neighbours of u respectively.  














  




§ MODEL




 §.§ Discrete Time Model


In this paper we consider a simplified discrete time model where each time step is equivalent to the communication time between two neighbouring nodes in the physical graph G_ = (V,E_). Here we assume that the distance between any two physical neighbour nodes u,v ∈ V is upper bounded by _, i.e., the maximum length of a physical communication link is d_. This implies in the discrete time model each time step is equivalent to _/c time units, where c is the speed of light in the communication channel. 










 §.§ Quantum Network


Each node in the quantum network has the following features.


  * Each node has a unique id, which carries the information about its location in the physical graph.


  * The nodes are capable of generating cap number of EPR pairs in parallel with each of its neighbours.

  * Each node is capable of storing the created entangled state. However, we assume that the storage is noisy and the fidelity of the stored entangled state decays with each time step. See Section <ref> for more details. 
If any entangled link is not being used for T_ time steps then the corresponding nodes won't use that link for entanglement swapping or for teleportation.

  * After T_ time steps each node throws away the stored entangled state and starts generating a new entangled state. 

  * In this paper we assume that T_≫_G_, i.e, the storage time for quantum memory is much higher than the classical communication time between any two nodes in the network.

  * Each node stores the information about the physical graph topology.

  * Each node stores the information (if available) about its both virtual neighbours (if any) and physical neighbours.

  * The distance between two virtual neighbours in G_ = (V,E_) is upper bounded by d_.





 §.§ Long-Distance Entanglement Creation



Long-distance entanglement creation is a well-studied subject <cit.>. For a detailed review, we refer to <cit.>. In this paper we are interested in a basic model. Due to the threshold time T_ the entanglement distribution time scales exponentially with the distance between the source destination pair. However, with this type of entanglement generation scheme we can guarantee on the end to end fidelity of the shared entangled links. It is important to note that this model is a trivial one. One can reduce this exponential scaling to a polynomial one by other techniques like entanglement distillation or quantum error correction <cit.>. The concepts of these techniques are beyond the scope of this paper. In this paper our main focus is on the decision making procedure for routing, not the physical means of entanglement generation. However, our routing algorithms are designed in such a manner, so that it can work with any entanglement generation procedure. Moreover, the conclusions we draw in this paper about the routing algorithms, remain same with respect to other entanglement generation procedures. 


The entanglement generation protocol between two nodes s,e with _G_(s,e)=d, we use in this paper, can be subdivided into two parts,


  * Elementary link creation, where the nodes in _G_(s,e), which are connected directly by a physical link, create entangled links between themselves. Usually, the created links are stored in a quantum memory.

  * The next one is called longer link creation where the intermediate nodes perform entanglement swap operation and share an entangled link between the end nodes.


In practice, photon loss in the optical fibre and other imperfections of the network components make the entanglement generation procedure a probabilistic but heralded one. This implies that the elementary link creation procedure can produce a signal which certifies the successful creation of the entangled link. In order to model this here, we assume that elementary link creation with probability P_0 ∈ [0,1] it can create an entangled link within a single time step. For an example of P_0, that takes into account the repeater technology based on NV center, we refer to <cit.>. 
In this paper, inspired from certain physical implementations <cit.>, we assume that entanglement swap operation is a deterministic one. We make the simplifying assumption that the time for this operation is negligible.
   
According to our simplified model, s,e can share an entangled state if and only if all the elementary links are being created within the time step T_. Of course, after the creation of the elementary entangled links the nodes need to communicate each other about it and it will cost some time steps. However, in the last section we assume that T_ is much larger than this classical communication time. So, for the simplicity, we remove the classical communication time from our calculation. This implies, probability of creating an entangled link between s,e within T_ time step is at least (1-(1-P_0)^T_)^d. As a consequence, the expected entanglement distribution time increases exponentially with d. As mentioned before this is a simplified model for entanglement generation but it is useful to guarantee the end to end fidelity of the shared entangled state. 










 §.§ Noisy Quantum Storage


The stored quantum state in quantum memory devices decoheres with time. Here we assume a simplified pessimistic model where the qubits decohere under the effect of symmetric depolarising noise with the parameter p. This type of quantum channel can be described as a completely positive trace preserving map ϵ: ℋ^⊗ 2→ℋ^⊗ 2. 


The noise operator for a two qubits state ρ_0,se = |ψ^+⟩_s,e⟨ψ^+|, shared between s,e, is denoted as ϵ and on this specific state (not in general) it acts as follows,





    ϵ(ρ_0,se) := p^2ρ_0,se + (1-p^2)_4/4,

where _4 is a 4× 4 identity matrix.





If at time step t-1 the stored state is ρ_t-1,se then at time step t the stored state would be ρ_t,se = ϵ(ρ_t-1,se). By solving this recursive relation on time steps t we get,


    ρ_t,se = p^2tρ_0,se + (1-p^2t)_4/4.


We can rewrite the above expression as ρ_t,se = (1/4+ 3/4p^2t)ρ_0,se + 3/4(1-p^2t)ρ^⊥_0,se, where ρ^⊥_0,se is orthogonal to ρ_0,se. This implies the fidelity of the stored state after t time steps is F(ρ_t,se,ρ_0,se) = 1/4+ 3/4p^2t.
  




  §.§.§ How to Choose T_

Entangled links with low fidelity make quantum communication very noisy. In order to protect the information from noise here we fix a threshold value, F_, for the fidelity. According to our model, each entangled link can be stored inside the quantum memory for T_ time. This implies ρ_T_,se should satisfy the following condition, 
    F(ρ_T_,se,ρ_0,se) > F_.
 By substituting the value of F(ρ_T_,se,ρ_0,se) from previous section we can get the following bound, up to time T_.




    T_   ≥1/2log plog[4F_/3-1/3].












 §.§ Continuous Network


In this model each of the nodes u in G_ = (V, E_) keeps the information about its |_G_(u)| physical neighbours and O(k) virtual neighbours. According to the model, for any long distance neighbour v of u, _G_(u,v)≤ d_. Each of the nodes establishes and maintains virtual entangled links with all of its neighbours using entanglement generation procedure discussed in section <ref>. After some fixed time interval (T_) the nodes again start to generate all of the links, irrespective of whether there is any demand or not. Borrowing ideas from classical complex network theory here we give more precise description of the following families of continuous network models. 





  * Deterministically chosen virtual neighbours: In the later sections we give a specific strategy for choosing virtual neighbours for ring, grid and recursively generated graph topologies. 

  * Randomly chosen virtual neighbours: 


  * virtual neighbours are chosen following a uniform distribution: In this network any node u choses another node v (_G_(u,v)>1) as a neighbour with probability , where


    (u,v) := 
    1/N_≤ d_(G_), _G_(u,v) ≤ d_
    
     0   Otherwise,





where N_≤ d_(G) denotes the number of nodes at a distance at most d_ from a node u.


  * virtual neighbours are chosen following a power-law distribution: In this network any node u choses another node v (such that _G_(u,v)>1) as a neighbour with probability , where


    (u,v) := 
    1/β_u1/^α_G(u,v), _G(u,v) ≤ d_
    
    0   Otherwise,

where β_u = ∑_v' ∈ V(u,v') and α > 0.






 §.§ On-demand Network


In this model, each node u in the physical graph G_ = (V,E_) has only |_G_(u)| neighbours. In the on-demand network there are no pre-shared entangled links and each node has information about the entire physical network topology. This implies that if a demand comes, then the source node can compute the shortest path from a source to a destination and starts generating entangled links between the source and destination along that path.  





§ ROUTING ALGORITHMS


In this section we propose three different kinds of distributed routing algorithms. The entire routing procedure between any two nodes in the quantum network can be subdivided into following three phases. 



  * Path discovery phase.

  * Entanglement reservation phase.

  * Entanglement distribution phase.


One can find the steps of the routing procedure in algorithm <ref>. Among the above three phases the first two phases all the routing decisions are made. In this paper in all of the routing algorithms we focus on different types of path discovery algorithms. Moreover, the algorithms reserve the entangled links while discovering the path. 
The reservation of the links is useful to prevent the utilisation of those links by other demands. After the path discovery and link reservation, if all of the entangled links are available along the path then, the intermediate nodes perform entanglement swap (in parallel) between the links. If there are not enough links available between two neighbours in the path, then the demand waits until all the missing links are being generate. If this missing link generation time is more than T_ then all of the reserved links along the path expires. In this case the demand waits until the all of the links along the path is being generated. 



In all of the routing algorithms, we assume that each node has the complete information about the physical network topology. However, due to the fragile nature of the entangled links, it is difficult to keep track of the current topology of the virtual graph. Here we assume that each node has all the information about the virtual links it shares with its neighbours. During the path discovery 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. Both of the algorithms try to minimise the average waiting time. Designing such algorithms becomes challenging when there are not enough entangled links available between two neighbours u,v. At that moment, for a demand, if v is an optimal neighbour of u to reach a destination node e then the routing algorithm has two options, (i) select the path via v and generate sufficient amount of links between u,v, (ii) u try to select another neighbour with whom it already shares enough amount of entangled links. 

The classical greedy routing algorithm <cit.> always chooses the first option. Here we point out that this is not always a good option for routing in a quantum internet. However, a slight modification of the greedy algorithm can give better performance. In algorithm <ref> we describe the modified version of the greedy routing algorithm in detail.

The path discovery algorithm in <ref> is a best effort algorithm, it chooses the second option. The aim of this algorithm is to utilise all the existing entangled links before generating a new one. In the next two sections, we give a detailed description of both of the algorithms.










 §.§ Modified Greedy Routing




In the classical network theory, greedy routing is well studied for discovering near optimal paths using only local information <cit.>. On the basis of the information of its neighbours, each node decides the next hop of a demand. Here, each node tries to jump to as close as possible to the destination node. The virtual neighbours are very useful for making such jumps. One big disadvantage of using the classical greedy routing algorithm for entanglement distribution is that while discovering the path, it doesn't take into account whether there exist enough entangled links available between two virtual neighbours. If the links are not present then the request or demand has to wait until all of the missing links are being generated. This might increase the latency. For example, for a demand, u is the last node discovered in the path and v is a neighbour of u which is the closest to the destination e. If there is not enough entangled links available between u,v and if _G_(u,v) ≥_G_(u,e) then it is not a good idea for u to put v in the path. In this paper we use a slightly modified version of the algorithm proposed in <cit.> so that it can handle this type of problem. In our modified Algorithm <ref> a node u puts the virtual neighbour v in the path, which is the closest to e if at least one of the following two cases are satisfied (See step 5 of the algorithm <ref>). 


  * If the amount of available entangled links between them is greater than D_s,e. 

  * If _G_(u,e) = _G_(u,v) + _G_(v,e), where G_=(V,E_) is a physical graph, u is the current node and v is its virtual neighbour which is the closest to the destination e.


If none of these two conditions were satisfied then u chooses its physical neighbour, closest to e as next hop. The details of the algorithm are described in algorithm <ref>.













 §.§ Local Best Effort Routing



The local best effort routing algorithm is a distributed algorithm where each node tries to jump as close as possible to the destination node, using existing entangled links. Unlike the greedy algorithm in this one, a node u first prepares a set of neighbours with whom it shares more than D_s,e amount of entangled links. Then from that set, u chooses the next hop v such that v is closest to e and _G_(u,e) < _G_(v,e) (See step 4 of the algorithm <ref>). If no such neighbour exists, then it chooses its physical neighbour which is the closest to the destination (See step 6 of the algorithm <ref>). Algorithm <ref> describes the procedure in more detail.












 §.§ NoN Local Best Effort Routing


In this section we are interested in studying the behaviour of the local best effort algorithm when the nodes have information about its neighbours as well as the neighbours of the neighbours in the virtual graph. In the literature of classical complex networks, this type of algorithm is known as NoN routing algorithm. In <cit.>, it has been showen that this type of algorithm gives better advantage for routing in certain kind of physical graphs. For example in ring (C_n) and grid network (Grid_n × n) if virtual neighbours are chosen following a power law distribution then classical NoN routing algorithm can discover a path with expected length log_2 n/log_2 log_2 n <cit.>. Here we adopt the idea of classical NoN routing algorithm into the local best effort algorithm. As it is a local best effort algorithm, so during the path discovery, the current node u_ first prepares a set of neighbours U' with whom it shares more than D_s,e amount of entangled links (See step 5 of the algorithm <ref>). Then from that set, the algorithm finds a node u' such that it has a neighbour u which is the closest (compare to the neighbours of the nodes in U') to the destination e and the available entangled links between u,u' is more than D_s,e. If no such u exists then the algorithm just chooses u from the physical neighbours of u' (See steps 6 to 12 of the algorithm <ref>). If the set U' is empty, then the algorithm chooses the next hop among its physical neighbours (See the steps 14 to 20 of the algorithm <ref>). For more details, we refer to Algorithm <ref>.










§ PROPERTIES OF THE ROUTING ALGORITHMS IN GENERAL NETWORK


The performance analysis of the distributed routing algorithms in a general virtual graph is a challenging task. However, due to the greedy nature of the routing algorithms in next lemma we can give an upper bound on the latency of a demand for all of the proposed routing algorithms. 



For any physical graph G_, and a demand matrix D with |D|=1, for any source and destination pair s,e, with D_s,e=1, for both modified greedy and local best effort algorithms the expected waiting times are upper bounded by,

    O(P^-_G_)    On-demand model
       O(d__G_)    Continuous model,

where P = (1-(1-P_0)^T_), i.e, the probability of creating an entangled link between two neighbour nodes (in G) within T_ time step. 



In G, the maximum distance d between any source and destination pair is _G_, i.e., d≤ diam_G_. In the on-demand model, as there is no pre-shared entanglement so the proof directly follows from the fact that expected time to generate a d-distance entangled link is (1-(1-P_0)^T_)^d.

In the continuous model, each node shares the entangled links with its neighbours. As |D|=1 and D_s,e=1, so for the demand s first discovers a path to e and reserve an entangled link along that path. Then entanglement swapping is used along that path to distribute the entanglement. As the nodes do not need to perform any entanglement generation during the routing, and entanglement swap operation is deterministic, the worst case latency would be the time to discover the path from s to e and the time to inform all the nodes for performing the entanglement swap operation. In both of the routing algorithms if a node u puts its neighbour v in the path then _G_(v,e) < _G_(u,e). This implies at each step of the path discovery phase the distance from the current node to the destination node is reduced by at least one. As the maximum length of any virtual link is d_, this implies the total latency is upper bounded by O(d__G). 


In the continuous model, the pre-shared entangled links are temporary in nature and one link can only be used for once. If D_s,e> cap then in this model it is better idea to find different edge-disjoint paths between s and e and use each path to distribute cap number of entangled links. In the next lemma we give an upper bound on D_s,e, such that the nodes do not need to wait for creating new entangled links.  


In the continuous network model, for any virtual graph , and for a demand matrix D with |D|=1, if _ denotes the minimal cut of the graph  then any two nodes s,e in  can distribute at least _.cap number of EPR pairs before regenerating any new entangled link.



In a virtual graph, an entangled link can only be used once for teleporting one qubit. In the continuous model we start with a connected virtual graph  and for sharing an entangled link between a source-destination pair s,e we have to use one entangled link along for each edge along the path from s to e. This implies s,e can use the existing links for routing until the graph becomes disconnected. By Menger's Theorem this is equal to the minimal cut of an undirected graph.


 The fragile nature of the entangled links affects the network topology. Due to this feature, if |D|>1 then the topology of the network changes rapidly and sometimes it might become disconnected. This triggers an interesting question regarding the performance of the routing algorithms. The next section focuses on this issue. 
 
 







§ ANALYSIS OF THE ROUTING ALGORITHMS ON RING AND GRID NETWORK TOPOLOGY





In this section we consider two physical graphs, a ring network C_n and a grid network Grid_n' × n'. For the ring network each node in the network has a unique id from {0,1, … , n-1}. For the grid network we assume that each node has node id u=(u_a,u_b), where u_a,u_b ∈{0,1, … , n'-1}. For the simplicity of our calculation we assume for the ring network, n=2^m for some positive integer m and d_ = 2^l for some positive integer l ≤ m. 

 In the next subsections we define how to choose the virtual neighbours in the continuous model and the on demand model.


 §.§ Continuous Model






  §.§.§ Virtual  with Deterministically Chosen entangled links


In this model, for the ring network, each node chooses its virtual neighbours with a deterministic strategy. If any node with node id x is of the form 2^iy, where i,y are non-negative integers and y is an odd number or 0, then that node has min(2i,2log_2 d_) virtual neighbours. Node id of those virtual neighbours are x+2 (mod n), x+2^2(mod n),… , x+2^min(i,log_2 d_)(mod n) and x+n-2 (mod n), x+n-2^2(mod n),… , x+n-2^min(i,log_2 d_)(mod n). One can also find this type of virtual network topology in <cit.>.  However, in <cit.> Schoute et al. constructed the network only for d_=_G_. In figure <ref> we give an example of such network.

Similarly, for grid network, each node with node id u=(u_a,u_b) of the form (2^ix,2^jy), where i,j are non-negative integers and x,y are positive odd numbers or zero, chooses 
k=min(2min(i,j),2log_2 d_) virtual neighbours. The node id of those virtual neighbours are (u_a+2 (mod n+1),u_b), (u_a+2^2(mod n+1),u_b),… , (u_a+2^k(mod n+1),u_b) and (u_a,u_b+2 (mod n+1), (u_a,u_b+2^2(mod n+1)),… , (u_a,u_b+2^k(mod n+1)). In figure <ref> we give an example of such network.










  §.§.§ Randomly Chosen virtual neighbours


In this model, for both of the network topologies, each node u ∈ V has k = log_2 d_ virtual neighbours (other than the physical neighbours) and each of such neighbours v is chosen independently without replacement, following the distribution (u,v). For the ring network, if (u,v) follows power law distribution then the diameter of the virtual graph is optimal α=1. In this simulation we also assume α=1. For the grid network  the diameter of the virtual graph is optimal for α =2 <cit.>. In this paper we assume α = 2.









 §.§ On Demand Model


In the on-demand model, the nodes do not have any virtual neighbours. So, for this model, we run our simulation with the physical graphs.




 §.§ Lower bound on the Fidelity for Single Source-Destination Pair

In this section, we assume that for all types of virtual graphs, all of the pre-shared links are available during the routing. 



In the continuous model with d_ > 2, if the virtual graphs are constructed from a physical network (G_) like a ring (C_n) or a grid (Grid_n × n) topology, if |D|=1 and for all i,j ∈ [0,n-1] and if D_i,j∈{0,1} then for any source destination pair s,e, the expected number of required entangled swap operations for sharing an entangled link between s,e is as given in table <ref>.


Proof Sketch :
For the deterministic virtual graphs, the required number of swap operations, presented in table <ref>, remain same for all of the routing algorithms and the proofs directly follow from the adaptation of the proofs given in <cit.>. 


 
Here we give the idea about the proof techniques for the random virtual graphs. Please check appendix <ref> for a detailed proof.

In all of the proofs, first we divide all of the nodes in the graph into m'=2_G_(s,e)/d_ sets, Z_0,Z_1, … , Z_m'-1, such that for all 0≤ i ≤ m'-1, 
    Z_i = {u : |u-e| ≤ |s-e| - id_/2}.
 In the path discovery phase, all of the algorithms start from the node s ∈ Z_0 and then continue to visit other nodes Z_1, Z_2,.., Z_m'-1. Any node in the set Z_m'-1 is at most d_/2 distance away from the destination e. In the proof we show that all of the algorithms discover a path from a node u ∈ Z_i to another node v ∈ Z_i+1 (where 0 ≤ i ≤ m'-2) using constant number of hops, i.e, u can share an entangled link with v using a constant number of entanglement swap operations. This proves that after O(m') number of swaps s can share an entangled link with a node u such that _G_(u,e) ≤d_/2. As _G_(s,e) ≤_G_ = O(n) for both C_n and Grid_n × n, this implies m' = O(n/d_).

Next, we give upper bounds on the number of required entanglement swap operations for sharing an entangled link between a node u∈ Z_m'-1 to the destination e. 



For this, we partition all of the nodes in Z_m'-1 into m sets, X_0 ⊃ X_1 ⊃…⊃ X_m-1. For local best effort and modified greedy algorithm, for all 0≤ i ≤ m-1, 

    X_i    = {u : |u-e| ≤d_/2^i}

For NoN local best effort algorithm, for all 0≤ i ≤ m-1,

    X_i     = {u : |u-e| ≤d_/(log_2 d_)^i}.




  * For the power-law virtual graphs, we show that, for all of the routing algorithms, a node u' ∈ X_i reaches to another node v' ∈ X_i+1 (where 0 ≤ i ≤ m-2) using constant number of hops, i.e, u' can share an entangled link with v' using a constant number of entanglement swap operations. This implies any node u ∈ Z_m'-1 can share an entangled link with a node v' ∈ X_m-1 using O(m) number of entanglement swap operations. 


  * For the local best effort and the modified greedy routing algorithms, if we choose m = log_2 d_, then according to the partitions in equation <ref>, all the nodes v' ∈ X_m-1 are constant distance away from the destination e. This implies for both of the routing algorithms the total number of required entanglement swap is O(n/d_+ log_2d_).

  * For the NoN local best effort routing algorithm, if we choose m = log_2 d_/log_2 log_2 d_, then according to the partitions in equation <ref>, all of the nodes v' ∈ X_m-1 are constant distance away from the destination e. This implies for the NoN local best effort routing algorithms the total number of required entanglement swaps is O(n/d_+ log_2 d_/log_2 log_2 d_).
   

  * For the uniform virtual graphs, for the local best effort and the modified greedy routing algorithms we show that a node u' ∈ X_i reaches to another node v' ∈ X_i+1 (where 0 ≤ i ≤ m-2) using 2^i/log_2 d_ number of hops. If we choose m=O(log_2(d_/log_2 d_)) then we get ∑_i=0^m-12^i/log_2 d_ = O(d_/(log_2d_)^2). This implies that both of the routing algorithms require O(n/d_+ d_/(log_2d_)^2) entanglement swap operations for distributing entangled link between any source and destination pair.

  * For the uniform virtual graphs, for the NoN local best effort routing algorithm we show that a node u' ∈ X_i reaches to another node v' ∈ X_i+1 (where 0 ≤ i ≤ m-2) using (log_2 d_)^i number of hops. If we choose m=O(log_log_2 d_(d_/log_2 d_)) then then we get ∑_i=0^m-12^i/log_2 d_ = O(d_/(log_2d_)^2). This implies that NoN local best effort routing algorithm require O(n/d_+ d_/(log_2d_)^2) entanglement swap operations for distributing entangled link between any source and destination pair.






For a ring network C_n and a grid network Grid_n× n, in the continuous model, if |D|=1 and for some s,e ∈ [0,n-1], if D_s,e=1 then for both local best effort and modified greedy routing algorithms the expected fidelity of the shared entangled link between s,e is lower bounded by 

    Deterministic and Power Law Virtual Graphs
       F^O(n/d_ + log d_)
         Uniform Virtual Graphs
       F^O(n/d_ + d_/(log d_)^2),

 where each of the pre-shared link has fidelity F. 


The proof of this lemma directly follows from the upper bounds on the number of entanglement swap operation, given in table <ref> and the fact that the fidelity of the entangled state, generated after performing one entanglement swap operation between two links with fidelity F, is F^2. 

We can get the following corollary by replacing d_ by the diameter of C_n and Grid_n× n.


For a ring network C_n and a grid network Grid_n× n, in the continuous model with d_=⌈n/2⌉, if |D|=1 and for some s,e ∈ [0,n-1], if D_s,e=1 then for both local best effort and modified greedy routing algorithms the expected fidelity of the shared entangled link between s,e is lower bounded by 

    Deterministic and Power Law Virtual Graphs
       F^O( log n)
         Uniform Virtual Graphs
       F^O(n/(log n)^2),

 where each of the pre-shared link has fidelity F. 




 §.§ Performance of Greedy Routing Algorithm with Multiple Source-Destination Pairs on Ring Network



In this section, we study the performance of the greedy routing algorithm when we have multiple source-destination pairs. We evaluate the average entanglement distribution time for all of the models using MATLAB simulations. 



  §.§.§ Simulation Setup
 
For the simulation we choose C_32 and Grid_5 × 5 as the physical graphs. We assume that the _=10 km, this implies, each time step is equivalent to 10/c≈ 0.00006 seconds (c denotes the speed of light in the optical fiber). In this paper we assume the threshold fidelity F_ is 0.8 and p=0.9993. If we plug in all the values of these parameters in equation <ref> then we get T_≈ 1000 steps, which is equivalent to 0.06 seconds. Note that, the maximum classical communication time between any two nodes in both grid and ring network is of the order 10^-5 seconds, which is much less than T_. This makes the classical communication time negligible compare to the memory storage time. 

In present day practical implementations for basic heralded entanglement link generation the value of P_0 is more than of the order 10^-4 <cit.>. Here, for the analysis of worst case scenario we assume P_0 = 0.0003. If we plug in the values of all the parameters in the expression (1-(1-P_0)^T_), then we get the probability of generating an entangled link between two physical neighbour nodes within the time window T_ is at least 0.25.

On top of the physical graph, we construct the virtual graph using the techniques proposed in section <ref>. For each of the virtual graph, first we fix |D| and then randomly generate the demand matrix D. Once we generate the demand matrix, then for each value of D_i,j we compute the latency for entanglement distribution and update the topology of the virtual graph. For each value of |D| we take 10000 samples of D and compute the AL by taking the average over all the samples. In the simulation we also assume that D_i,j≤ cap. 

For routing in the continuous model, first the nodes discover a path from a source to a destination and reserve the entangled links along the path. If all of the required entangled links are available then the intermediate nodes just perform entanglement swap operation, otherwise the demand waits until all of the virtual links along the path are being generated. During the path discovery and entanglement reservation phase, we assume that there is no collision between two demands for reserving one link. One can easily overcome this assumption by adding some priority corresponding to each demand. The nodes distribute an entangled link between a source and a destination using the procedure proposed in section <ref>. For each demand we compute the waiting time, which is composed of path discovery time, time for generating missing entangled links and communication time for informing all the nodes in the path for performing entanglement swap operation.

For the randomly chosen virtual neighbour models, we first sample the neighbours and construct the corresponding virtual graph from the physical graphs. We take 100 such samples of virtual graphs and for each of such sample graphs, we compute the AL by taking the average over all the samples of |D| and virtual graphs. 
On the basis of this setup, in the next sections, we study the effect of different design parameters on the AL. 



  §.§.§ Discussions on the Simulation Results


We begin our discussion with the simulations of the figures <ref>, <ref>, <ref>. In all of the subfigures, we compare the proposed distributed routing algorithms. All of the figures basically show our intuition mentioned in section <ref>, regarding the inefficiency of the classical greedy routing algorithms. The witness of inefficiency is more evident for d_=4, as the penalty for an unwise decision of jumping increases with the distance. A closer observation of the figures also reveals another fact that local best effort performs better than the modified greedy algorithm when |D| is smaller and the situation changes for the favour of modified greedy algorithms with an increase of |D|. The intuitive reason behind it is that the local best effort algorithm tries to use the existing entangled links as much as possible before generating a new one. This gives an advantage over the modified greedy algorithm. However, for large |D| it quickly exhausts all of the pre-shared links and converges to the on-demand network model. 

Next, we focus on comparing the performance of both of the routing algorithms when the nodes pre-share four EPR pairs with each of its neighbours (see figure <ref>) and each demand can ask for at most two EPR pairs. Intuitively, for these type of demands, continuous network model takes the advantage of the pre-shared entangled links and it outperforms the on-demand one.


In figure <ref> we are interested in studying the behaviour of the routing algorithms when the nodes demand a high number (between two to four) of entangled links and each node pre-share four entangled links with each of its neighbours. For the ring network, in figure <ref>, <ref> we observe that for higher number of demands, deterministic virtual graphs are better compared to randomised one. However, figures <ref> and <ref> suggest that for the grid network it is wise to choose the virtual neighbours uniformly randomly. 

In the simulation corresponding to figure <ref> all of the source destination pairs have distance at least d_ and we observe that this scenario resembles with the simulations of figure <ref>, where each source and destination pair asks for a high number of entangled links. We refer to such demands as long-distance demands. The intuitive reason for this similar behaviour is that here the source and destination pairs are generated randomly and as the size of the set of long-distance source and destination pairs are much larger, so most of the demands in the simulation of figure <ref> are long distance demands. As the impact of the long-distance demands on latency is large compared to the short distance ones, so on average both of the simulations behave similarly. 

In all of the simulations we observe that for the grid network, the separation in AL between the on-demand and the continuous model is very high compare to the ring network. This can be explained by using the idea of lemma <ref>. Due to the higher connectivity among the nodes in the grid network it is easier to find edge disjoint paths for different demands. 




   
   
 
 
 In figure <ref> we compare the performance of the NoN local best effort algorithm with other routing algorithms. In figure <ref> we can observe that NoN algorithms do not give any advantage in deterministic ring network. In table <ref> we also have this kind of observation. However, for random virtual graphs, in figure <ref> and <ref> we observe that this algorithm performs better than the other two algorithms for smaller number of demands. If the number of demands increases then we observe the worst performance for NoN local best effort algorithm and the best (among the three proposed algorithms) performance for the modified greedy routing algorithm. The main reason behind this is that the rate of consuming existing the existing entangled link for NoN local best effort algorithm is higher than the other ones. Due to this feature, for NoN local best effort algorithm the continuous model converges to the on-demand model very fast, hence after certain number of demands it shows worse performance.    

 
   



 



















































§ ROUTING IN MORE GENERALISED GRAPHS





 §.§ Recursively Generated Graphs (RGG)

This section focuses on a further study of the proposed entanglement pre-sharing and routing models in more general graphs. The topology of a large real-life internet network is far more complex than a ring or grid and it always grows with time. However, in most of the cases, the global pattern of a complex system emerges from the patterns observed in smaller subsystems. These phenomena can also be observed in classical internet. The recursive graph is one of the best ways to model this kind of objects <cit.>. In general, recursive graphs are being constructed from a base graph G_0 and at each recursive step, the current graph G_t is being substituted by another graph G_t+1. The substitution rules remain the same for the entire evolution. Tensor product graphs are one example of such graphs <cit.>. In this paper, we study a model of the recursively generated graph, where a new graph is being generated by substituting the edges of the old graph. One can find an example of such graphs in <cit.>. Here, we use the term edge substitution to describe this operation. It is defined as follows,



Let G_0 = (V_0, E_0) and H = (V_H, E_H) be two graphs. The edge substitution of a graph G_0 with respect to H is an operation, where each edge (u,v) ∈ E_0 (where u,v ∈ V_0) is being substituted by another graph 
({u,w_uv},{(u,w_uv)}) ∪ G_uv∪ ({v,w'_uv},{(v,w'_uv)}), where w_uv,w'_uv∈ G_uv and G_uv = (V_uv, E_uv) is isomorphic to H and _G_uv(w_uv,w'_uv) = _H. If G_1 = (V_1, E_1) denotes the new substituted graph then,

    V_1    = V_0 ⋃_(u,v) ∈ E_0 V_uv
    
    E_1     = (E_0 ∖ (u,v)) ⋃_(u,v)∈ E_0[(u,w_uv) ∪ E_uv∪ (v,w'_uv)].
 
 



we construct the recursive graphs using following rules



  * The base graph G_0= (V_0,E_0) represents quantum internet graph with physical links.


  * Let at recursive step l the physical graph is G_l = (V_l,E_l).

  * Suppose  be a set of graphs. If any subgraph G̃_l ⊆ G_l is isomorphic to any graph in  then we perform edge substitution of G̃_l with respect to H = (V_H,E_H). Suppose G̃_l+1= (Ṽ_l+1,Ẽ_l+1) denotes the substituted graph.

  * At recursive step l+1, if the physical graph with physical links is G_l+1 = (V_l+1,E_l+1) then

    V_l+1   = V_l ⋃_G̃_l ⊆ G_l∖ G_l-1
    G̃_l ≅Ṽ_l+1.
    
    E_l+1   = (E_l∖ (⋃_G̃_l ⊆ G_l∖ G_l-1
    G̃_l ≅Ẽ_l)) ⋃_G̃_l ⊆ G_l∖ G_l-1
    G̃_l ≅Ẽ_l+1.









A RGG with respect to an initial graph G_0=(V_0,E_0), a set of graphs , a substitution graph H = (V_H,E_H) is called regular if G_0 = H is a regular graph and = {H}.








In this paper we focus on studying RRGG with G_0 = H = C_n and = {C_n}.




 §.§ Recursively Generated Virtual Graph



The main motivation of studying recursive graph is to understand the behaviour of a hierarchical topology for a quantum network. In this paper we are also interested in studying the quantum internet if the nodes from different levels of the hierarchy have different entanglement generation capabilities. We assume that for any RRGG G_l = (V_l,E_l) if any node v ∈ V_l'∖ V_l'-1, for some 0≤ l' ≤ l-1, then it can pre-share entangled link with any node within d_(_G_l-l'-1+2) distance from itself. The nodes v ∈ G_l∖ G_l-1 can create entangled links within d_ distance from itself.

The detailed construction of the virtual graph _l = (V_l,_l) is given below. 


  * Let G_0 = (V_0,E_0) be a physical graph, which is isomorphic to C_n. We construct the corresponding virtual graph _0 = (V_0,_0) using the same procedure, proposed in section <ref>.

  * Let G_l-1 = (V_l-1,E_l-1) denote the physical graph at (l-1)-th level of recursion.

  * At l-th level, if any subgraph G̃_l-1 of G_l-1 is isomorphic to C_n then for all of the edges of G̃_l-1 we perform edge substitution with respect to the graph _0. Let _l = (V_l,_l) denotes the substituted graph. 

  * This implies, if at l-th level the virtual graph is denoted by _l = (V_l,_l) then

    _l   = _l-1⋃_G̃_l-1⊆ G_l-1∖ G_l-2
    G̃_l-1≅_l.

 
 
Example : In figure <ref> and <ref> we give examples of the RRGG with G_0 = H = C_8 and ={C_8}. The graph corresponds to the figure <ref> denote the physical graph at the recursive step 0. From there we construct the deterministic virtual graph _0 with d_=2 using the techniques proposed in section <ref>. Later in figure <ref> we construct the physical graph by performing edge substitution corresponding to each of the edges in G_0. For a better understanding, in figure <ref> we colour the nodes at G_0 red. One can note that, as a result of the edge substitution, between two red nodes there is one C_8. The virtual graph _1 in figure <ref> is being constructed from _0 and G_1. In figure <ref> all of the edges of G_0 is being substituted by a graph isomorphic to _0. Here also we put red colour on the nodes from _0. Beside this, in _1, we keep the virtual links between the red nodes from _0. In figure <ref> we denote these links by green dotted lines.    





§ PROPERTIES OF THE RRGG

Here we discuss the properties of this type of network which are useful to get an upper bound on the latency for distributing an entangled link between a source and destination pair using all of the routing algorithms, described in the section <ref>.
In the previous section we assume that for any RRGG G_l = (V_l,E_l) if any node v ∈ V_l'∖ V_l'-1, for some 0≤ l' ≤ l-1, then it can pre-share entangled link with any node within d_(_G_l-l'-1+2) distance from itself. In the next lemma we show that our assumption holds for the proposed recursively generated virtual graphs. 



In the recursively generated virtual graph _l = (V_l,_l), generated from a RRGG G_l = (V_l,E_l), if for any two nodes u,v ∈ V_l, __l(u,v)=1 then,

    _G_l(u,v)    ≤ d_(_G_l-l'-1+2)  if 
       ∀ 1≤ l' ≤ l-1,  v ∈ V_l'∖ V_l'-1
    _G_l(u,v)    ≤ d_  if  v ∈ V_l∖ V_l-1.
 




 For the case l'=0 we have v ∈ V_l∖ V_l-1. All such nodes are being generated after the edge substitution operation with respect to _0. This implies that all the virtual neighbours of such nodes v are within d_ perimeter. 
 
In case of l' > 0 all the nodes v ∈ V_l-l'-1∖ V_l-l'-2 are being generated after the edge substitution operation with respect to _0. This implies, if any two nodes u,v ∈ V_l-l'-1∖ V_l-l'-2 have distance _G_l-l'-1(u,v), then after the edge substitution their distance would become _G_l-l'(u,v)=_G_l-l'-1(_G_0 +2) and _G_l(u,v)=_G_l-l'-1(_G_l-l'-1 +2). If two nodes u,v ∈ V_l-l'-1∖ V_l-l'-2 are neighbours in _l-l'-1 then _G_l-l'-1(u,v) ≤ d_. According to the construction, those two nodes would still be neighbours in _l. This implies their distances in G_l would be upper bounded by d_(_G_l-l'-1+2). 

 



According to lemma <ref>, in the continuous model, if a single source and destination pair would like to generate a single entangled link then the latency is the order of the the diameter of the physical graph. In the next lemma we are interested in computing the diameter of a RRGG at the l-th step of the recursion. 


For any RRGG G_l = (V_l,E_l) where l ≥ 1 and G_0 = (V_0,E_0) = C_n is the base graph and = {C_n}, 

    _G_l = _G_0(_G_l-1+2).



We prove this lemma using induction. For the base case, l=1 we construct G_1 by performing the edge substitution operations with respect to C_n on all the edges of G_0. Each of the edge substitution operations increase the distance between two neighbour nodes in G_0 by _G_0+2. For any two nodes u,v ∈ V_1 there are three following cases.



  * Case 1 : If u,v ∈ V_0 then _G_0(u,v) ≤_G_0. This implies, _G_1(u,v) ≤_G_0(_G_0+2). The equality holds if _G_0(u,v) = _G_0. 


  * Case 2 : If u,v ∈ V_1∖ V_0 then they are part of G_1∖ G_0. Suppose u has been generated after the edge substitution of (u',u”) ∈ E_0 and v has been generated after the edge substitution of (v',v”) ∈ E_0. Without any loss of generality we can assume that _G_0(u',v') = min{_G_0(u',v'), _G_0(u',v”), _G_0(u”,v'),_G_0(u”,v”)}. This implies, _G_0(u”,v”) = _G_0(u',v') + 2 and _G_0(u',v') ≤_G_0-2. Hence, _G_1(u,v) = _G_1(u,u') + _G_1(v,v') + _G_1(u',v') ≤ 2_G_0 + _G_0(u',v')(_G_0+2) ≤_G_0(_G_0+2).


  * Case 3 : If u ∈ V_0 and v ∈ V_1 ∖ V_0 then let v has been generated after the edge substitution of the edge (v',v”) ∈ E_0. Without any loss of generality we can assume that _G_0(u,v') = min{_G_0(u,v') , _G_0(u,v”)}. This implies _G_0(u,v”) = _G_0(u,v') + 1 and _G_0(u,v') ≤_G_0-1. Hence, _G_1(u,v) = _G_1(v,v') + _G_1(u,v') ≤_G_0 + _G_0(u,v')(_G_0+2) ≤_G_0(_G_0+2).


The base case of the inductive hypothesis is true. Suppose the inductive hypothesis is true for some l=l'. This implies _G_l' = _G_0(_G_l'-1+2). For l=l'+1, the graph is G_l'+1. It has been generated by performing the edge substitution operations on all of the edges of the subgraphs H_l'⊆ G_l' which are isomorphic to C_n. One can also construct G_l'+1 by replacing each edge of G_0 by a G_l'. For any two nodes in G_l'+1 we have following three cases.



  * Case 1 : If u,v ∈ V_l' then _G_l'(u,v) ≤_G_l'. This implies, _G_l'+1(u,v) ≤_G_0(_G_l'+2). The equality holds if _G_l'(u,v) = _G_l'. 


  * Case 2 : If u,v ∈ V_l'+1∖ V_l' then they are part of G_l'+1∖ G_l'. Suppose u has been generated after the edge substitution of (u',u”) ∈ E_l' and v has been generated after the edge substitution of (v',v”) ∈ E_l'. Without any loss of generality we can assume that _G_l'(u',v') = min{_G_l'(u',v'), _G_l'(u',v”), _G_l'(u”,v'),_G_l'(u”,v”)}. This implies, _G_l'(u”,v”) = _G_l'(u',v') + 2 and _G_l'(u',v') ≤_G_l'-2. Hence, _G_l'+1(u,v) = _G_l'+1(u,u') + _G_l'+1(v,v') + _G_l'+1(u',v') ≤ 2_G_0 + _G_l'(u',v')(_G_0+2) ≤_G_0(_G_l'+2).


  * Case 3 : If u ∈ V_l' and v ∈ V_l'+1∖ V_l' then let v has been generated after the edge substitution of the edge (v',v”) ∈ E_l'. Without any loss of generality we can assume that _G_l'(u,v') = min{_G_l'(u,v') , _G_l'(u,v”)}. This implies _G_l'(u,v”) = _G_l'(u,v') + 1 and _G_l'(u,v') ≤_G_l'-1. Hence, _G_l'+1(u,v) = _G_l'+1(v,v') + _G_l'+1(u,v') ≤_G_l' + _G_l'(u,v')(_G_l'+2) ≤_G_0(_G_l'+2).


This implies, if the inductive hypothesis is true for any l=l' ≥ 1 then it is also true for l=l'+1. From the principle of mathematical induction one concludes that _G_l = _G_0(_G_l-1+2) for any integer l ≥ 1.


By using the recursive relation in the above lemma we get the following upper bound on the latency for entanglement distribution in RRGG. 



In the continuous model, for a virtual graph _l = (V_l,_l) corresponding to any RRGG G_l = (V_l,E_l) with G_0 = (V_0,E_0) = C_n as base graph and = {C_n}, if |D|=1 and for all i,j ∈ V_l and if D_i,j∈{0,1} then for any source destination pair s,e, the latencies of the routing algorithms <ref>, <ref> and <ref> are upper bounded by,

    O((n/2)^l+1).











§ CONCLUSION AND OPEN PROBLEMS



In this paper, by combining ideas from complex network theory and quantum information theory, we propose a special kind of quantum network with pre-shared entangled links, which can reduce the latency of the network. As expected, we observe that the network with pre-shared entanglement is useful when the network has a small number of demands. If the network has a very high number of demands then the continuous model does not give many advantages compared to the on-demand model. Here we study the performance of our routing algorithms on some specific network topologies. We leave the investigation of the performance of the proposed entanglement pre-sharing strategies and routing algorithms in more generalised networks (Especially, the networks where the physical neighbour nodes are not deployed with equal distances) as future work. 

 For the continuous model, here we construct the virtual graph using the ideas from complex networks. This type of approaches reduce the diameter of the virtual graph and the routing algorithms require a lesser number of entanglement swap operations. This implies if each of the pre-shared links has very high fidelity then after the routing, the source and destination can share a very high fidelity entangled state. In table <ref> we give upper bounds on the number of required entanglement swap operations for a different type of virtual graphs. This upper bound depends on the threshold distance of d_. Usually, higher d_ helps to reduce the network latency but also decreases network throughput. It is always interesting to find a tradeoff between these two quantities. We leave this as future research. Other than this, in the continuous model, all of the proposed entanglement pre-sharing schemes are independent of the network traffic. One possible future research direction would be to use the tools from traffic engineering for predicting the behaviour of the network and study how one can choose the virtual neighbours according to the traffic. 
 
In this paper, we consider a very simple model for entanglement generation. For example, here we consider that due to the presence of noise in the quantum memory the fidelity of the stored state decays with time. As a result, one can store the state for a limited number of time steps (T_) steps. This limited storage time can increase the latency of the network in the continuous model. One can increase the value of T_ using the concept of entanglement distillation. Entanglement distillation process consumes two or more low fidelity entangled states and produces a new high fidelity entangled link. This might give some advantage in both reducing the latency and increasing the end to end fidelity at the expense of a higher setup cost. We leave the study of the advantages and disadvantages of entanglement distillation in the continuous model for future work.  

In our model, during the path discovery, first, we reserve the existing entangled links along the path. The nodes start performing the entanglement swap operations when the entire path has been established. This makes the routing algorithm stateful, i.e, each of the nodes needs to keep track of all of the paths which are passing through it. Besides this, it might increase the latency of the network, as the existing links might become useless while discovering the path. In our next approach, we would like to come up with a more dynamic version of the routing algorithm, where the nodes can perform the swap operation while discovering the path.


We also show that existing classical greedy routing algorithms are not capable of taking the full advantage of the pre-shared entangled links. In this paper we propose two new distributed routing algorithms and using numerical simulations on ring and grid topology we show that both of them perform better than the classical one. Simulations in figure <ref>, <ref>, <ref> and <ref> show that the routing algorithms which utilises the existing entangled links as much as possible, performs better for small number of demands. However, this way they might exhaust the pre-shared links and the network might converge to on-demand model very fast. For a high number of demands among the three routing algorithms modified greedy performs better than both local best effort and NoN local best effort algorithm. This observation is quite counterintuitive compared to the classical routing algorithms. The reason is that usually if the nodes have more information about the updated network topology, then the routing algorithm performs better than the case where the nodes have less information about updated network topology. It gives an insight for designing new routing algorithms. 


In this paper, we study the advantages and disadvantages of the three types of virtual networks. From the simulation results, we observe that in the ring network, if we use local best effort and modified greedy routing algorithms then deterministic virtual graphs have low latency compared to random virtual graphs. However, for the grid network, the uniform and power-law virtual graphs show better performance. On the other hand, if we consider the end to end fidelity of the shared state, then table <ref> suggests to use the power-law virtual graphs. 




 In the end, we propose another type of continuous model for a hierarchical network with a small diameter. Here, we show that all of the proposed routing algorithms can distribute an entangled link between a source and a destination using a very small number of entanglement swap operations. We leave the performance analysis of the routing algorithms on such networks for multiple source, destination pairs for future work.
 
 

§ ACKNOWLEDGEMENT

We would like to acknowledge S. Bauml, K. Goodenough, A. Szava for many stimulating discussions on routing in a quantum internet. We would also like to thank ERC starting grant, NWO VIDI grant and Quantum internet Alliance (QIA) for providing the financial supports.
IEEEtran




The entire appendix is focused on giving the detailed proof of theorem <ref>. Before going to the detailed proof, in the next appendix first we define some of the used notations again. One can find the more details about theorem <ref> and the outline of the proofs in appendix <ref>.



§ NOTATIONS


In this section, for the reader's convenience we define the some of used notations again.



  * G_ = (V,E_) : Physical graph, where V denotes the set of nodes and E_ denotes the set of edges in the physical graph.

  * C_n : Ring network with n nodes.

  *  : Virtual Graph.

  * _G_(u,v) : The hop distance between two nodes u,v in a physical graph G_. 

  * _G_ : The diameter of the physical graph G_. 

  * d_ : The maximum threshold distance (in the physical graph) between two virtual neighbour.

  * T_ : The threshold storage time. 

  * (u,v) : Probability that two nodes u,v are virtual neighbours of each other.


  * For the power-law virtual graphs,

    (u,v) := 
    1/β_u1/_C_n(u,v), _C_n(u,v) ≤ d_
    
    0   Otherwise,

where β_u = ∑_v' ∈ V 
 0< (u,v') ≤ d_1/_C_n(u,v).

  * For the uniform virtual graphs,

    (u,v) := 
    1/N_≤ d_(G_), _G_(u,v) ≤ d_
    
     0   Otherwise,

where N_≤ d_(G) denotes the number of nodes at a distance at most d_ from a node u.


  * s : Source node.

  * e : Destination node.

  * D : The demand matrix.

  * D_i,j : (i,j)-th entry of the demand matrix D. It signifies, how many EPR pairs the source i and the destination j wants to create.

  * |D| : The number of non zero entries in the demand matrix D.

  * PathDisc(s,e,,D_s,e) : The subroutine, used by all of the proposed routing algorithms (modified greedy (<ref>), local best effort (<ref>) and NoN local best effort (<ref>)) for discovering paths between a source and a destination pair. 

  * CommPath_s,e : The path, returned by the subroutine PathDisc(s,e,,D_s,e).




§ OVERVIEW


In the main paper, in theorem <ref> we give the upper bound on the number of required entanglement swap operations for distributing entanglement between any two nodes in a ring and a grid network. For the ease for the reader's reading we restate the theorem again.


Theorem 1: In the continuous model with d_ > 2, if the virtual graphs are constructed from a physical network (G_) like a ring (C_n) or a grid (Grid_n × n) topology, if |D|=1 and for all i,j ∈ [0,n-1] and if D_i,j∈{0,1} then for any source destination pair s,e, the expected number of required entangled swap operations for sharing an entangled link between s,e is as given in table <ref>.




In this paper, we only give the detailed proofs of the theorem <ref> for the ring network with n nodes (C_n). The same proof technique can be used for proving the theorem for the grid networks. Note that, in the table <ref> the number of required entanglement swap operations changes with the type of the virtual graphs. In this paper, we study deterministic, power-law and uniform virtual graphs. The structure of the proofs for all of these graphs is organised in the following manner.




  * In the first row of the table <ref> we have the upper bound on the number of swap operations for the deterministic virtual graphs. For these type of virtual graphs, the required number of swap operations, presented in the table <ref>, remains the same for all of the routing algorithms and the proofs directly follow from <cit.>. Hence, we do not include the proofs for such virtual graphs.


  * In the second row of the table <ref>, we have the upper bound on the number of swap operations for the power-law virtual graphs. One can find the detailed proofs of the bounds in the second row of the table <ref> in appendix <ref>. More precisely, using lemma <ref> and lemma <ref> we prove the upper bound on the number of entanglement swap operations that are required by the modified greedy and the local best effort routing algorithms for distributing entanglement in a power law virtual graph (The upper bound is O(n/d_ + log d_)). Similarly, using lemma <ref> and lemma <ref> we prove the upper bound on how many entanglement swap operations the NoN local best effort algorithm takes for distributing an entangled link between any two nodes in a power law virtual graph (The upper bound is O(n/d_ + log d_/loglog d_)). One can find lemma <ref> , <ref> and <ref> in appendix <ref>.



  * In the third row of the table <ref>, we have the upper bound on the number of swap operations for the uniform virtual graphs. One can find the detailed proofs of the bounds in the third row of the table <ref> in appendix <ref>. Note that, in the table <ref>, both of the upper bounds in the third row are the same. However, due to the different behaviour of the routing algorithms, we need to use different proof techniques. For the uniform virtual graphs, by combining the results from lemma <ref> and lemma <ref> we give the proof on the upper bound for the modified greedy and local best effort routing algorithm (The upper bound is O(n/d_ + d_/(log d_)^2)). One can get the proof of the upper bound on the entanglement swap operations for the NoN local best effort algorithm by combining the results from lemma <ref> and lemma <ref> (The upper bound is O(n/d_ + d_/(log d_)^2)).
 





 §.§ Detailed Outline of the Proofs

In the routing algorithm <ref>, the total number of required entanglement swap operations to share an entangled link between a source node s and a destination node e is the same as the size of the set CommPath_s,e (i.e., |CommPath_s,e|). In theorem <ref> we would like to give an upper bound on the following quantity, 


    max_s,e ∈ C_nE[|CommPath_s,e|].



Here, the maximum is taken over all possible source destination pairs (s,e) in C_n.

In algorithm <ref>, the subroutine PathDisc(s,e,,D_s,e) computes the routing path CommPath_s,e. In this paper we consider three different types of PathDisc(s,e,,D_s,e) subroutines (See algorithms <ref>, <ref> and <ref>) and each of them are greedy and distributed in nature. This implies, the path has been discovered in a hop by hop fashion. In this discovery process the current node u chooses one of its neighbours v as the next hop of the path if _C_n(u,e) > _C_n(v,e). In the physical graph C_n, for two nodes u,v, _C_n(u,v) = min(|u-v|, n-|u-v|). For simplicity we assume that min(|s-e|, n-|s-e|) = |s-e|. 

In order to give an upper bound on the equation <ref>, first we partition the set of all nodes in C_n into m' nonempty sets, Z^(s,e)_0, … , Z^(s,e)_(m'-1), where m' = ⌈2|s-e|/d_⌉. Here for all 0≤ i ≤ m'-1, 
    Z^(s,e)_i := {u : |u-e| ≤ |s-e| - id_/2}.
 As all of the PathDisc(s,e,,D_s,e) subroutines are greedy in nature, so they start by constructing the set CommPath_s,e from the source node s ∈ Z^(s,e)_0 and they discover the path through the nodes in the sets Z^(s,e)_1, … , Z^(s,e)_m'-1. Each node u ∈ Z^(s,e)_i is connected to a node in v ∈ Z^(s,e)_i+1 with probability (u,v). Here note that if the algorithms discover a node u∈ Z^(s,e)_m'-1 then |u-e| ≤d_/2. Let ^(s,e)_i denotes the number of nodes the path discovery algorithm visits to discover a node v in the set Z^(s,e)_i+1 from a node u in the set Z^(s,e)_i.


 







 





 
 According to the algorithms <ref>, <ref> and <ref> the total number of required entanglement swap is same as the length of the discovered path (|CommPath_s,e|). This implies,

    |CommPath_s,e| = ∑_i=0^m'-2^(s,e)_i + Y_s,e.

where Y_s,e denotes the length of the discovered path from a node u ∈^(s,e)_m'-2 to e. By taking expectation on both sides of equation <ref> we get,

    E[|CommPath_s,e|]    =   E[∑_i=0^m'-2^(s,e)_i + Y_s,e]
        = ∑_i=0^m'-2 E[^(s,e)_i] + E[Y_s,e],

In the theorem <ref> we prove the upper bound on the following quantity,


    max_s,e ∈ C_nE[|CommPath_s,e|]  =  max_s,e   [∑_i=0^m'-2 E[^(s,e)_i] + E[Y_s,e]]
    ≤max_s,e ∈ C_n[∑_i=0^m'-2 E[^(s,e)_i]]    +  max_s,eE[Y_s,e].
 

In the appendix <ref> we give the detailed proof of the upper bound on max_s,eE[|CommPath_s,e|] for the power-law network. The proof has been subdivided into two parts. In the first part we focus on giving an upper bound on ∑_i=0^m'-2 E[^(s,e)_i] (See lemma <ref>). The proof for this part is the same for all of the proposed PathDisc(s,e,,D_s,e) subroutines. However, in the second part, the proof of the upper bound on E[Y_s,e] changes with the PathDisc(s,e,,D_s,e) subroutines. We prove the upper bounds on E[Y_s,e] for algorithms <ref> and <ref> in lemma <ref>. We give the proof of the upper bound on E[Y_s,e] for algorithm <ref> in lemma <ref>.   



Similarly, appendix <ref> contains the detailed proof of the upper bound on max_s,eE[|CommPath_s,e|] for the uniform virtual graph. Lemma <ref> contains the proof of the upper bound on ∑_i=0^m'-2 E[^(s,e)_i]. The proof of the upper bound on E[Y_s,e] for the PathDisc(s,e,,D_s,e) subroutines <ref> and <ref> is given in lemma <ref>. For the proof of the upper bound on E[Y_s,e] for the path discovery algorithm <ref> we refer to lemma <ref>.















§ UPPER BOUND ON THE NUMBER OF ENTANGLEMENT SWAP OPERATIONS FOR POWER LAW VIRTUAL GRAPHS




In the continuous model, the maximum distance (distance in the physical graph) between two virtual neighbour nodes is d_. Due to this upper bound, in the worst case two nodes need to perform at least _G_/d_ swap operations for sharing an entangled state. In lemma <ref> we show that, in worst case (when the distance between a source s and a destination e is _G_), all of the proposed routing algorithms take O(n/d_) number of swap operations for distributing an entangled link between, a source s and a node u, such that _G_(u,e) ≤d_/2. Later, in lemma <ref> we show that, both local best effort and modified greedy routing algorithms take O(log_2 d_) number of swap operations to create an entangled state between u and the destination e. By combining the results of lemma <ref> and <ref> we prove the following upper bound.


    max_s,e ∈ C_nE[|CommPath_s,e|] ≤ O(n/d_ + log_2 d_)



In lemma <ref> we show that using the NoN greedy routing algorithm, the node u can share an entanglement link with e using O(log_2 d_/log_2 log_2 d_) number of swap operations. Using the results of lemma <ref> and <ref> we prove the following upper bound,


    max_s,e∈ C_nE[|CommPath_s,e|] ≤ O(n/d_ +log_2 d_/log_2 log_2 d_)







For the power-law virtual graphs, a node u choses another node v as virtual neighbour with probability (u,v). According to the definition of  (see equation <ref>) we have,


    (u,v) := 
    1/β_u1/_C_n(u,v), _C_n(u,v) ≤ d_
    
    0   Otherwise,

where β_u = ∑_v' ∈ V 
 0< (u,v') ≤ d_1/_C_n(u,v).

In the next lemma, we give an upper bound on β_u for the physical graph C_n.



In a power law virtual graph, which has been constructed from a physical graph C_n, if any two nodes u,v are virtual neighbours of each other with probability, (u,v), such that,


    (u,v) := 
    1/β_u1/_C_n(u,v), _C_n(u,v) ≤ d_
    
    0   Otherwise,

where β_u = ∑_v' ∈ V 
 0< (u,v') ≤ d_1/_C_n(u,v), then for any u, the value of β_u ≤ 4log_2 d_.




According to the definition of β_u we have,

    β_u    = ∑_v' ∈ V 
     0< (u,v') ≤ d_1/_C_n(u,v')
        = ∑_j=1^d_∑_v' ∈ V
    _C_n(u,v') = j1/j
       ≤∑_j=1^d_2/j
       As ∑_j=1^d_1/j≤log_2d_ +1 < 2log_2d_, this implies
    β_u    ≤ 4log_2d_.
 







For the power-law virtual graphs, constructed from the physical graph C_n, if |D|=1 and for all i,j ∈ [0,n-1] if D_i,j∈{0,1}, then for any source destination pair (s,e), all of the algorithms <ref>, <ref> and <ref> take O(n/d_) number of entanglement swap operations for distributing an entangled link between s and a node u such that _C_n(u,e) ≤d_/2. 








Proof Outline : For the proof of this lemma, we divide the set of nodes of C_n into m' nonempty sets, Z^(s,e)_0, … , Z^(s,e)_m'-1, where 

    m' := ⌈2|s-e|/d_⌉.

 Here for all 0≤ i ≤ m'-1, 
 
    Z^(s,e)_i := {w : |w-e| ≤ |s-e|-id_/2}.

  The greedy path discovery subroutines, start constructing the path from s ∈ Z^(s,e)_0. In this process if a node w ∈ Z^(s,e)_i, chooses v as a next hop in the path, then either v ∈ Z^(s,e)_i or v ∈ Z^(s,e)_i+1 (0 ≤ i ≤ m'-2). Note that all the nodes u ∈ Z^(s,e)_m'-1 are at most d_/2 distance away from the destination e. for all 0≤ i ≤ m'-2, ^(s,e)_i denotes the number of nodes the path discovery algorithms visit to discover a node in the set Z^(s,e)_i+1 from a node in the set Z^(s,e)_i, then in this lemma we would like to prove,  




    ∑_i=0^m'-2 E[^(s,e)_i] ≤ O(n/d_).


In the proof, first we show that each of E[^(s,e)_i] is upper bounded by a constant number, which is independent of n and d_. As a result, we get ∑_i=0^m'-2 E[^(s,e)_i] ≤ O(m'). Substituting the value of m' from equation <ref> we get ∑_i=0^m'-2 E[^(s,e)_i] ≤ O(m') = O(⌈2|s-e|/d_⌉). As, |s-e| ≤_C_n = ⌈n/2⌉. This implies, ∑_i=0^m'-2 E[^(s,e)_i] ≤ O(m') ≤ O(n/d_). The detailed proof is given below. 

   

We consider the situation where, for any 0≤ i ≤ m'-1 the path discovery algorithms discover the path from s to a node w ∈ Z^(s,e)_i. In the next step of the path discovery algorithm, w choses the next hop v from his neighbour nodes, such that _C_n(v,e)< _C_n(w,e). We are interested in computing the total number of required entanglement swap operations for creating an entangled link with a node v ∈ Z^(s,e)_i+1 from any node w ∈ Z^(s,e)_i. Let [w → Z^(s,e)_i+1] denotes the probability that w has at least one neighbour in the set Z^(s,e)_i+1. From the definition of  (see equation <ref>) we have,

    (w,v)     = 1/β_w_C_n(w,v)  if |w-v|≤ d_
       ≥1/β_wd_,  As |w-v|≤ d_
        = 0     Otherwise.


Let Z'^(s,e)_i+1⊆ Z^(s,e)_i+1 denotes the set of nodes v such that ∀ v ∈ Z'^(s,e)_i+1, |w-v| ≤ d_. Each of the nodes in Z'^(s,e)_i+1 choose w as a virtual neighbour with probability (w,v). This implies w has at least one virtual neighbour in Z^(s,e)_i+1 with probability |Z'^(s,e)_i+1|(w,v). In section <ref> we mention that in the virtual graph, w has at least log_2 d_ such virtual neighbours and each of them belongs to the set Z^(s,e)_i+1 with probability |Z'^(s,e)_i+1|(w,v). This implies,

    [w → Z^(s,e)_i+1]  ≥ 1- (1-|Z'^(s,e)_i+1|(w,v))^log_2 d_,

For all real x and r> 0, we have (1-x)^r ≤exp(-xr). In the above equation if we consider x = |Z'^(s,e)_i+1|(w,v) and r = log_2 d_, then we get, (1-|Z'^(s,e)_i+1|(w,v))^log_2 d_≤exp(-|Z'^(s,e)_i+1|(w,v)log_2 d_). Substituting this inequality in equation <ref> we get,

    [w → Z^(s,e)_i+1]   ≥ 1- exp(-|Z'^(s,e)_i+1|(w,v)log_2 d_).

Substituting the value of (w,v) we get,

    [w → Z^(s,e)_i+1]   ≥ 1- exp(-|Z'^(s,e)_i+1|log_2 d_/β_w d_).

Substituting the value of β_w from lemma <ref> we get,

    [w → Z^(s,e)_i+1]   ≥ 1- exp(-|Z'^(s,e)_i+1|log_2 d_/4d_log_2 d_)
    [w → Z^(s,e)_i+1]   ≥ 1- exp(-|Z'^(s,e)_i+1|/4d_).



Now we focus on giving a lower bound on |Z'^(s,e)_i+1|. For the lower bound, we consider the nodes in Z^(s,e)_i which are the furthest from the set Z'^(s,e)_i+1. According to the definition (see equation <ref>), all of the nodes in Z'^(s,e)_i are at most |s-e| - id_/2 distance away from the destination node e and all of the nodes in Z'^(s,e)_i+1 are at most |s-e| - (i+1)d_/2 away from the destination e. The maximum distance between a node ω∈ Z^(s,e)_i and the set Z'^(s,e)_i+1 is computed in the following equation, 


    max_ω∈ Z^(s,e)_imin_v' ∈ Z^(s,e)_i+1 |ω - v'|.

From the triangle inequality we have, for any three nodes ω, v', e, |ω - v'| ≥ |ω - e| - |v' - e|. This implies, 

    max_ω∈ Z^(s,e)_imin_v' ∈ Z^(s,e)_i+1 |ω - v'|    ≥max_ω∈ Z^(s,e)_imin_v' ∈ Z^(s,e)_i+1 |ω - e| - |v' - e|
        = max_ω∈ Z^(s,e)_i |ω - e| - min_v' ∈ Z^(s,e)_i+1   |v' - e|

As ω∈ Z^(s,e)_i this implies, |ω - e| ≥ |s-e| - id_/2. Similarly, as v' ∈ Z^(s,e)_i+1, this implies |v'-e| ≤ |s-e| - (i+1)d_/2. Substituting the values of |ω - e| and |v' - e| in equation <ref> we get, 

    max_ω∈ Z^(s,e)_imin_v' ∈ Z^(s,e)_i+1 |ω - v'|    ≥ |s-e| - id_/2 - |s-e| + (i+1)d_/2
       = d_/2.


The above derivation implies that in the worst case all of the nodes Z'^(s,e)_i+1 are at least d_/2 distance away from w. According to the definition of Z'^(s,e)_i+1, each of the nodes in this set are at most d_ distance away from the node w. This implies, the maximum distance between any two nodes in Z'^(s,e)_i+1 is at least d_/2. As, in C_n, there are at least d number of nodes within d distance from any node w. This implies, 


    |Z'^(s,e)_i+1| ≥d_/2.


Substituting the value of |Z'^(s,e)_i+1| in equation <ref> we get,

    [w → Z^(s,e)_i+1]    ≥   1- exp(-|Z'^(s,e)_i+1|/8d_)
       ≥ 1- exp( -1/8).



Here, ^(s,e)_i+1 denotes the number of required swap operations for distributing an entangled link between a node in Z^(s,e)_i+1 from a node in Z^(s,e)_i. From the equation <ref> we have that each of such node w ∈ Z^(s,e)_i is connected to a link v ∈  Z^(s,e)_i+1 with probability at least 1- exp( -1/8). This implies, each swap operation manages to create an entangled link with a node v ∈ Z^(s,e)_i+1 with probability at least 1- exp( -1/8). The phenomenon of this entanglement can be modelled as a sequence of independent trials, where each trial succeeds with probability at least 1- exp( -1/8). This implies, ^(s,e)_i+1 follows a geometric distribution with parameter 1- exp( -1/8). So, we have, for all 0≤ i ≤ m'-2, E[^(s,e)_i+1]≤(1- exp( 1/8))^-1 = O(1). This implies, 


    ∑_i=0^m'-2 E[^(s,e)_i]    ≤∑_i=0^m'-2 O(1) .

Substituting the value of m' from equation <ref> in the above equation we get,


    ∑_i=0^m'-2 E[^(s,e)_i]   ≤ O(⌈2|s-e|/d_⌉).

As in a ring network with n nodes (C_n) the maximum distance between any two nodes is at most n/2, this implies, for any s,e ∈ V, |s-e| ≤n/2. Substituting the upper bound on |s-e| in equation <ref> we get,

    ∑_i=0^m'-2 E[^(s,e)_i] ≤ O(n/d_).

This concludes the proof.

Substituting the upper bound on ∑_i=0^m'-2 E[^(s,e)_i] to equation <ref> we get,

    max_s,eE[|CommPath_s,e|] ≤ O(n/d_) + max_s,eE[Y_s,e].


Up to this part, the proofs are the same for all of the proposed algorithms. The analysis changes when we compute the upper bounds of E[Y_s,e]. 







 §.§ Proof of the upper bound on the swap operations for both local best effort and modified greedy algorithm


In equation <ref>, the term Y_s,e is related to the term max_s,eE[|CommPath_s,e|]. For a source destination pair (s,e), the term Y_s,e denotes how many more entanglement swap operations are required for creating an entangled link between s and e, given that s already has created an entangled link with a node u such that _C_n(u,e) ≤d_/2. In lemma <ref> we show that the modified greedy and the local best effort algorithm can share an entangled state between any two nodes u,e such that _C_n(u,e) ≤d_/2, using only O(log_2 d_) swap operations. This gives us the required bound for max_s,eE[Y_s,e] ≤ O(log_2 d_). The proof technique is just a simple adaptation of the proof given in <cit.>. For completeness, here we include the proof.



For the power-law virtual graphs, constructed from the physical graph C_n, if |D|=1 and for some u,e ∈ [0,n-1] if D_u,e = 1 and if _C_n(u,e) ≤d_/2 then the algorithms <ref>, <ref> take O(log_2 d_) number of entanglement swap operations for distributing an entangled link between u and e.







Let us consider a hierarchy of of m+1 nonempty sets, X^(u,e)_0 ⊃ X^(u,e)_1 ⊃ X^(u,e)_2 ⊃…⊃ X^(u,e)_m, where 

    m := log_2 d_,

and for all 0≤ i ≤ m, 
    X^(u,e)_i := {u' : |u'-e| ≤d_/2^i}.


Note that, all the nodes in X^(u,e)_m are at most one distance (in the physical graph) away from the destination node e. This implies, all of the nodes in X^(s,e)_m are physical neighbours of e.

In a ring network, C_n, one can verify that for all 0 ≤ i ≤ m,


    |X^(u,e)_i| ≥d_/2^i.




The algorithms start to discover a path from a node in u ∈ X^(u,e)_0 to a node in the set X^(u,e)_m through the nodes in the sets X^(u,e)_1, … , X^(u,e)_m-1. The algorithms stop when it discovers the path up to the destination node in X^(u,e)_m. Let the algorithm spends Y^(u,e)_i iterations in the set X^(u,e)_i. According to Algorithm <ref> and <ref> the length of the path is,

    ∑_i=0^m Y^(u,e)_i.












Here, first we show that for each 0 ≤ i ≤ m, E[Y^(u,e)_i] is upper bounded by a constant number. This gives us the proof that, ∑_i=0^m E[Y^(u,e)_i] ≤ O(m). Substituting the value of m from equation <ref> we have ∑_i=0^m E[Y^(u,e)_i] ≤ O(m) ≤ O(log_2 d_). The detailed proof is given below.

For any 0 ≤ i ≤ m-1, suppose the path discovery algorithm has discovered a path from u ∈ X^(u,e)_0 to a node u' such that u' ∈ X^(u,e)_i but u' ∉X^(u,e)_i+1. Let u' → X^(u,e)_i+1 denotes the event that u' has a virtual neighbour in the set X^(u,e)_i+1. In a similar way, by the notation u' ↛X^(u,e)_i+1 we denote the event that u' has no virtual neighbour in X^(u,e)_i+1. Let v ∈ X^(u,e)_i+1, then from equation <ref> we have (u',v) ≥1/β_v1/|u'-v|. From lemma <ref> we have, β_v ≤ 4log_2 d_. This implies 

    (u',v) ≥1/4log_2 d_1/|u'-v|.

As v∈ X^(u,e)_i+1 so |v-e| ≤d_/2^i+1. From the triangle inequality of the distance function we have,


    |u'-v|    ≤ |u'-e| + |v-e|,

As, u' ∈ X^(s,e)_i, this implies |u'-e| ≤d_/2^i. Similarly, as v∈  X'^(s,e)_i+1, this implies, |v-e| ≤d_/2^i. Substituting |u'-e| and |v-e| in the above equation we get,

    |u'-v|   ≤2d_/2^i.


By substituting the upper bound on of |u'-v| in the expression of (u',v) in equation <ref> we get,


    (u',v) ≥1/8log_2 d_2^i/d_.


In the power-law virtual graph, each of the nodes v ∈ X^(s,e)_i+1 is a virtual neighbour of u' with probability (u',v). So, the probability that u' has a virtual neighbour in X^(s,e)_i+1 is, 
    ∑_v ∈ X^(u,e)_i+1(u',v).

In the above expression, substituting the value of (u',v) from equation <ref> we get,


    ∑_v ∈ X^(u,e)_i+1(u',v)    ≥∑_v ∈ X^(u,e)_i+11/8log_2 d_2^i/d_
       ≥ |X^(u,e)_i+1|1/8log_2 d_2^i/d_.

Substituting |X^(u,e)_i+1| from equation <ref> we get,

    ∑_v ∈ X^(u,e)_i+1(u',v)    ≥d_/2^i+11/16log_2 d_2^i/d_
        = 1/16log_2 d_.


As u' has k=log_2 d_ such virtual neighbours and each of them is identical and independently distributed according to . This implies,  


    [u' ↛X^(u,e)_i+1]    ≤ (1 - |X^(u,e)_i+1|(u',v))^k

As for all real x and r>0 we have (1-x)^r ≤exp(-xr), this implies


    [u' ↛X^(u,e)_i+1]    ≤exp(-k|X_i+1|(u',v)).


Substituting the values of  and |X_i+1| from equation <ref> and  <ref> we get,


    [u' ↛X^(u,e)_i+1]    ≤exp(-k/16log_2 d_).

Substituting k = log_2 d_ we get,

    [u' ↛X^(u,e)_i+1]     ≤exp(-1/16)
    
    1- [u' ↛X^(u,e)_i+1]    ≥ 1- exp(-1/16)

As for any 0≤ x ≤ 1, 1-e^-x≥x/2, this implies,

    [u' → X^(u,e)_i+1]    ≥1/32.


If the algorithms discover the path to a node u' ∈ X^(u,e)_i, then with probability at least 1/32, the algorithms discover another node v ∈ X^(u,e)_i+1. This implies, each step of the algorithms manages to find a neighbour node v ∈ X^(s,e)_i+1 with probability at least 1/32. The phenomenon of this finding a node v∈ X^(s,e)_i+1 can be modelled as a sequence of independent trials, where each trial has two outcomes (success and failure) and each trial succeeds with probability at least 1/32. This implies, Y^(u,e)_i follows a geometric distribution with parameter 1/32. This implies,  


    E[Y^(u,e)_i] ≤ 32.


Substituting the value of E[Y^(u,e)_i] in Equation <ref> we get,


    ∑_i=0^m E[Y^(u,e)_i]    ≤∑_i=0^m 32
        = O(m)
    Substituting the value of     m  from equation <ref> we get 
    ∑_i=0^m E[Y^(u,e)_i]   ≤ O(log_2 d_).
 
This concludes the proof.


As the result of lemma <ref> holds for all possible source destination pair (u,e), such that _C_n(u,e) ≤d_/2, so we can use this result to get the following upper bound on max_s,eE[Y_s,e],


    E[Y_s,e] ≤ O(log_2 d_).


Substituting the upper bound on max_s,eE[Y_s,e] in equation <ref> we get,

    max_s,e ∈ C_nE[|CommPath_s,e|] ≤ O(n/d_ + log_2 d_)


This concludes the proof of the upper bound on the total number of required entanglement swap operations for local best effort and modified greedy routing algorithms. For the ease of the reader's understanding, we restate the part of theorem <ref>. 




Power-law Part of Theorem <ref>: 
In the continuous model, for a power-law virtual graph, constructed from the physical graph C_n, if |D|=1 and for all i,j ∈ [0,n-1] if D_i,j∈{0,1} then for sharing an entangled link between any source destination pair s,e, the expected number of required entangled swap operations by the Local best effort and the modified greedy routing algorithms (max_s,eE[|CommPath_s,e|]), is upper bounded by

    O(n/d_+ log_2 d_).






 §.§ Proof of the upper bound on the swap operations for NoN local best effort algorithm


Using a simple adaptation of the proof given in <cit.> one can show E[Y_s,e] ≤ O(log_2 d_/log_2 log_2 d_). For completeness, here we include the proof.



For the power-law virtual graphs, constructed from the physical graph C_n, if |D|=1 and for some u,e ∈ [0,n-1] if D_u,e = 1 and if _C_n(u,e) ≤d_/2 then the algorithm <ref> take O(log_2 d_/log_2 log_2 d_) number of entanglement swap operations for distributing an entangled link between u and e.






Let us consider a hierarchy of m+1 nonempty sets, X^(u,e)_0 ⊃ X^(u,e)_1 ⊃ X^(u,e)_2 ⊃…⊃ X^(u,e)_m, where 

    m := log_2 d_/log_2 log_2 d_,

and for all 0≤ i ≤ m, 
    X^(u,e)_i := {u' : |u'-e| ≤d_/(log_2 d_)^i}.


Note that, all the nodes in X^(u,e)_m are at most one distance away from the destination node e. This implies all of the nodes in the set X^(s,e)_m are physical neighbours of the destination node e.

In a ring network, C_n, one can verify that for all 0 ≤ i ≤ m,


    |X^(u,e)_i| ≥d_/(log_2 d_)^i.






The algorithm starts to discover a path from a node in u ∈ X^(u,e)_0 to a node in the set X^(u,e)_m through the nodes in the sets X^(u,e)_1, … , X^(u,e)_m-1. The algorithm stops when it discovers the path up to the destination node in X^(u,e)_m. Let the algorithm spends Y^(u,e)_i iterations in the set X^(u,e)_i. According to Algorithm <ref> the length of the path is,

    ∑_i=0^m Y^(u,e)_i.




Here, first we show that for each 0 ≤ i ≤ m, E[Y^(u,e)_i] is upper bounded by a constant. This gives us the proof that, E[Y_s,e] ≤ O(m) ≤ O(log_2 d_/log_2 log_2 d_). The detailed proof is given below.

For any 0 ≤ i ≤ m-1, suppose the path discovery algorithm discovers a path from u ∈ X^(u,e)_0 to a node u' such that u' ∈ X^(u,e)_i but u' ∉X^(u,e)_i+1. Let u' →_1 X^(u,e)_i+1 denotes the event that u' has a virtual neighbour in the set X^(u,e)_i+1. In Algorithm <ref> we are interested in the fact that whether u' is connected to X^(u,e)_i+1 via a path of length two or not (neighbour of the neighbour). So, we use the notation u' →_2 X^(u,e)_i+1 to denote the event u' is connected to the set X^(u,e)_i+1 via a path of length two. Similarly, the complement of this event is denoted by u' ↛_2 X^(u,e)_i+1.  If v ∈ X^(u,e)_i+1, then from equation <ref> we have (u',v) = 1/β_u'|u'-v|. Substituting the value of β_u' from lemma <ref> we get (u',v) ≥1/4log_2 d_1/|u'-v|. As v ∈ X^(u,e)_i+1, this implies |v-e| ≤d_/(log_2 d_)^i+1, similarly as u' ∈ X^(s,e)_i, this implies |u-e| ≤d_/(log_2 d_)^i. By combining these two inequalities we get, 




    |u'-e| + |v-e|    ≤2d_/(log_2 d_)^i.

From the triangle inequality we have, 

    |u'-e| + |v-e|    ≥ |u'-v|.

This implies,

    |u'-v|    ≤2d_/(log_2 d_)^i.


By substituting the upper bound of |u'-v| from equation <ref> and β_u' from lemma <ref> in the expression of (u',v) we get,


    (u',v) ≥1/4log_2 d_(log_2 d_)^i/d_.


In algorithm <ref> we are interested in finding whether the node u' is connected to any node in X^(u,e)_i+1 via path of length at most 2. In the set X^(u,e)_i+1, there are |X^(u,e)_i+1| such v's and each of them is a long distance neighbour of u' with probability (u',v). So, the probability that u is connected with one of them is,

    ∑_v ∈ X^(u,e)_i+1(u',v) 
       Substituting the value of (u',v)  from equation <ref>
       ≥∑_v ∈ X^(u,e)_i+11/4log_2 d_(log_2 d_)^i/d_
       = |X^(u,e)_i+1|1/4log_2 d_(log_2 d_)^i/d_
       Substituting |X^(u,e)_i+1| from equation <ref>
       ≥d_/(log_2 d_)^i+11/4log_2 d_(log_2 d_)^i/d_    
        = 1/4(log_2 d_)^2.


u' has k = log_2 d_ such virtual neighbours and each of them is identical and independently distributed according to . This implies,  


    [u' ↛_1 X^(u,e)_i+1]    ≤ (1 - |X^(u,e)_i+1|(u',v))^k

Each of the neighbours of u' has again k such virtual neighbours and each of those virtual neighbours are identically and independently distributed according to . This implies,


    [u' ↛_2 X^(u,e)_i+1]    ≤ (1 - |X^(u,e)_i+1|(u',v))^k^2.

As (1-x)^r ≤exp(-xr), this implies,

    [u' ↛_2 X^(u,e)_i+1]    ≤exp(-k^2|X^(u,e)_i+1|(u,v)).

Substituting the value of (u',v) and X^(u,e)_i+1 rom equation <ref> and <ref> we get,

    [u' ↛_2 X^(u,e)_i+1]   ≤exp(-k^2/4(log_2 d_)^2).

Substituting k= log_2 d_ we get,

    [u' ↛_2 X^(u,e)_i+1]   ≤exp(-1/4)
    
    1- [u' ↛_2 X^(u,e)_i+1]    ≥ 1- exp(-1/4)


As for any 0≤ x ≤ 1,1-e^-x≥x/2. This implies,

    [u' →_2 X^(u,e)_i+1]    ≥1/8.


If the algorithms discover the path to a node u' ∈ X^(u,e)_i, then with probability at least 1/8, the algorithms discover another node v ∈ X^(u,e)_i+1. This implies, each step of the algorithms manages to find a neighbour node v ∈ X^(s,e)_i+1 with probability at least 1/8. The phenomenon of this finding a node v∈ X^(s,e)_i+1 can be modelled as a sequence of independent trials, where each trial has two outcomes (success and failure) and each trial succeeds with probability at least 1/8.This implies the random variable Y^(u,e)_i follows geometric distribution with parameter 1/8. 


    E[Y^(u,e)_i] ≤ 8.


Substituting the value of E[Y^(u,e)_i] in Equation <ref> we get,


    ∑_i=0^mE[Y^(u,e)_i] ≤ O(log_2 d_/log_2 log_2 d_).
 
This concludes the proof.

As the result of lemma <ref> holds for all possible source destination pair (u,e), such that _C_n(u,e) ≤d_/2, so we can use this result to get the following upper bound on max_s,e ∈ C_nE[Y_s,e],


    max_s,e∈C_nE[Y_s,e] ≤ O(log_2 d_/log_2 log_2 d_).

Substituting the value of E[Y_s,e] in equation <ref> we get,

    max_s,e∈C_nE[|CommPath_s,e|] = O(n/d_ + log_2 d_/log_2 log_2 d_)


This concludes the proof of the upper bound on the total number of required entanglement swap operations for NoN local best effort algorithm. For the ease of the reader's understanding, we restate the part of theorem <ref>.

Power-law Part of Theorem <ref>: 
In the continuous model, for a power-law virtual graph, constructed from the physical graph C_n, if |D|=1 and for all i,j ∈ [0,n-1] if D_i,j∈{0,1} then for sharing an entangled link between any source destination pair s,e, the expected number of required entangled swap operations by the NoN Local best effort algorithm (max_s,eE[|CommPath_s,e|]), is upper bounded by

    O(n/d_+ log_2 d_/log_2log_2 d_).







§ UPPER BOUND ON THE NUMBER OF ENTANGLEMENT SWAP OPERATIONS FOR THE UNIFORM VIRTUAL GRAPHS




In the continuous model, the maximum distance (distance in the physical graph) between two virtual neighbour nodes is d_. Due to this upper bound, in the worst case any two nodes need to perform at least _G_/d_ swap operations for sharing an entangled state. In lemma <ref> we show that, in the worst case (when the distance between a source s and a destination e is _G_), for all of the proposed routing algorithms, after O(n/d_) number of swap operations, the source s can share an entangled state with a node u, such that _G_(u,e) ≤d_/2. Later, in lemma <ref> we show that, both local best effort and modified greedy routing algorithms take O(d_/(log_2 d_)^2) number of swap operations to share an entangled state from u to the destination e. By combining the results of lemma <ref> and <ref> we get the following upper bound,


    max_s,e∈ C_nE[|CommPath_s,e|] ≤ O(n/d_+ d_/(log_2 d_)^2).


In lemma <ref> we show that using the NoN greedy routing algorithm, the node u can share an entanglement link with the destination e using O(d_/(log_2 d_)^2) number of swap operations. Using the results of lemma <ref> and <ref> we prove the following upper bound on the total number of entanglement swap operations. 



    max_s,e∈ C_nE[|CommPath_s,e|] ≤ O(n/d_+ d_/(log_2 d_)^2).




In the next lemma we focus on proving O(n/d_) bound.


































For the uniform virtual graphs, constructed from the physical graph C_n, if |D|=1 and for all i,j ∈ [0,n-1] if D_i,j∈{0,1}, then for any source destination pair (s,e), all of the algorithms <ref>, <ref> and <ref> take O(n/d_) number of entanglement swap operations for distributing an entangled link between s and a node u such that _C_n(u,e) ≤d_/2.


Outline of the Proof: Like the proof of lemma <ref> here we divide the set of nodes of C_n into m' nonempty sets, Z^(s,e)_0, … , Z^(s,e)_m'-1, where 

    m' := ⌈2|s-e|/d_⌉.
 

Here for all 0≤ i ≤ m'-1, 
    Z^(s,e)_i := {w : |w-e| ≤ |s-e| - id_/2}.
 The greedy path discovery subroutines, start constructing the path from s ∈ Z^(s,e)_0. In this process if a node w ∈ Z^(s,e)_i, chooses v as a next hop in the path, then either v ∈ Z^(s,e)_i or v ∈ Z^(s,e)_i+1 (0 ≤ i ≤ m'-1). Note that all the nodes u ∈ Z^(s,e)_m'-1 are at most d_/2 distance away from the destination e. If for all 0≤ i ≤ m'-2, ^(s,e)_i denotes the number of nodes the path discovery algorithms visit to discover a node in the set Z^(s,e)_i+1 from a node in the set Z^(s,e)_i then this lemma we would like to prove,  

    ∑_i=0^m'-2 E[^(s,e)_i] ≤ O(n/d_).


Here we show that each of E[^(s,e)_i] is upper bounded by a constant, which is independent of n and d_. As a result, we get ∑_i=0^m'-2 E[^(s,e)_i] ≤ O(m').By substituting the value of m' from equation <ref> we get ∑_i=0^m'-2 E[^(s,e)_i] ≤ O(m') = O(⌈2|s-e|/d_⌉). As in C_n, for any two nodes s,e, _C_n(s,e) ≤n/2. This implies, ∑_i=0^m'-2 E[^(s,e)_i] ≤ O(⌈2|s-e|/d_⌉) ≤ O(n/d_). 


 We consider for any 0≤ i ≤ m'-1 the path discovery algorithm discovers the path from s to a node w ∈ Z^(s,e)_i. In the next step of the path discovery algorithm, w choses another neighbour v such that _C_n(v,e)≤_C_n(w,e). Now, let [w → Z^(s,e)_i+1] denotes the probability that w has a neighbour v in the set Z^(s,e)_i+1. From the definition of  (equation <ref>) we have,


    (w,v) = 
    1/N_≤ d_(C_n), _C_n(w,v) ≤ d_
    
     0   Otherwise,


For C_n, N_≤ d_(C_n) ≤ 2d_. Substituting the upper bound on N_≤ d_(C_n) in the equation above we get,


    (u,v) = 
    1/2d_, _C_n(w,v) ≤ d_
    
     0   Otherwise,

 
 Let Z'^(s,e)_i+1⊆ Z^(s,e)_i+1 denotes the set of nodes v such that ∀ v ∈ Z'^(s,e)_i+1, |w-v| ≤ d_. Each of the node in Z'^(s,e)_i+1 choose w as a virtual neighbour with probability (w,v). This implies w has a virtual neighbour v∈ Z'^(s,e)_i+1 with probability |Z'^(s,e)_i+1|(w,v). In section <ref> we mention that in the virtual graph, w has at least log_2 d_ such virtual links and each of them belongs to the set Z^(s,e)_i+1 with probability |Z'^(s,e)_i+1|(w,v). This implies,





    [w → Z^(s,e)_i+1] ≥ 1    - (1-|Z'^(s,e)_i+1|(w,v))^log_2 d_
    Substituting the value of     from equation <ref> we get,
    [w → Z^(s,e)_i+1]    ≥ 1- (1-|Z'^(s,e)_i+1| 1/2d_)^log_2 d_.


Now we focus on giving a lower bound on |Z'^(s,e)_i+1|.

For the lower bound, we consider the nodes in Z^(s,e)_i which are the furthest from the set Z'^(s,e)_i+1. According to the definition (see equation <ref>), all of the nodes in Z'^(s,e)_i are at most |s-e| - id_/2 distance away from the destination node e and all of the nodes in Z'^(s,e)_i+1 are at most |s-e| - (i+1)d_/2 away from the destination e. The maximum distance between a node ω∈ Z^(s,e)_i and the set Z'^(s,e)_i+1 is computed in the following equation, 



    max_ω∈ Z^(s,e)_imin_v' ∈ Z^(s,e)_i+1 |ω - v'|.

From the triangle inequality we have, for any three nodes ω, v', e, |ω - v'| ≥ |ω - e| - |v' - e|. This implies, 

    max_ω∈ Z^(s,e)_imin_v' ∈ Z^(s,e)_i+1 |ω - v'|    ≥max_ω∈ Z^(s,e)_imin_v' ∈ Z^(s,e)_i+1 |ω - e| - |v' - e|
        = max_ω∈ Z^(s,e)_i |ω - e| - min_v' ∈ Z^(s,e)_i+1   |v' - e|

As ω∈ Z^(s,e)_i this implies, |ω - e| ≥ |s-e| - id_/2. Similarly, as v' ∈ Z^(s,e)_i+1, this implies |v'-e| ≤ |s-e| - (i+1)d_/2. Substituting the values of |ω - e| and |v' - e| in equation <ref> we get, 

    max_ω∈ Z^(s,e)_imin_v' ∈ Z^(s,e)_i+1 |ω - v'|    ≥ |s-e| - id_/2 - |s-e| + (i+1)d_/2
       = d_/2.



The above derivation implies that in the worst case all of the nodes Z'^(s,e)_i+1 are at least d_/2 distance away from w. According to the definition of Z'^(s,e)_i+1, each of the nodes in this set are at most d_ distance away from the node w. This implies, the maximum distance between any two nodes in Z'^(s,e)_i+1 is at least d_/2. As, in C_n, there are at least d number of nodes within d distance from any node w. This implies, 


    |Z'^(s,e)_i+1| ≥d_/2.


Substituting the value of |Z'^(s,e)_i+1| in equation <ref> we get,

    [w → Z^(s,e)_i+1]    ≥   1- (1-|Z'^(s,e)_i+1| 1/2d_)^log_2 d_

Substituting the value of |Z'^(s,e)_i+1| we get,

    [w → Z^(s,e)_i+1]    ≥ 1- (1- d_/4d_)^log_2 d_
       ≥  1- (1/4)^log_2 d_
       ≥3/4    As d_≥ 2.



Here, ^(s,e)_i+1 denotes the number of required swap operations for distributing an entangled link between a node v ∈ Z^(s,e)_i+1 from a node w ∈ Z^(s,e)_i. From the equation <ref> we have that each of such node w ∈ Z^(s,e)_i is connected to a link v ∈  Z^(s,e)_i+1 with probability at least 3/4. This implies, each swap operation manages to create an entangled link with a node v ∈ Z^(s,e)_i+1 with probability at least 3/4. The phenomenon of this entanglement can be modelled as a sequence of independent trials, where each trial succeeds with probability at least 3/4. This implies, ^(s,e)_i+1 follows a geometric distribution with parameter 3/4. So, we have, for all 0≤ i ≤ m'-2, E[^(s,e)_i+1]≤4/3≤ 2 = O(1). This implies, 



    ∑_i=0^m'-2 E[^(s,e)_i]    ≤∑_i=0^m'-2 2
       ≤ 2m'
    Substituting the value of     m'  from equation <ref> we get,
    ∑_i=0^m'-2 E[^(s,e)_i]   ≤ 2⌈2|s-e|/d_⌉
       ≤2n/d_  As |s-e| ≤n/2
        = O(n/d_).

This concludes the proof.

Substituting the upper bound on ∑_i=0^m'-2 E[^(s,e)_i] to equation <ref> we get,

    max_s,e ∈ C_nE[|CommPath_s,e|] ≤ O(n/d_) + max_s,e ∈ C_nE[Y_s,e].


Up to this part, the proofs are the same for all of the proposed algorithms. The analysis changes when we compute E[Y_s,e]. 




 §.§ Proof of the upper bound on the swap operations for both local best effort and modified greedy algorithms
 In equation <ref>, the term Y_s,e is related to the term max_s,e ∈ C_nE[|CommPath_s,e|]. For a source destination pair (s,e), the term Y_s,e denotes how many more entanglement swap operations are required for creating an entangled link between s and e, given that s already has created an entangled link with a node u such that _C_n(u,e) ≤d_/2. In lemma <ref> we show that the modified greedy and the local best effort algorithm can share an entangled state between any two nodes u,e such that _C_n(u,e) ≤d_/2, using only O(d_/(log_2 d_)^2) swap operations. This gives us the required bound for max_s,eE[Y_s,e] ≤ O(d_/(log_2 d_)^2). The proof technique is just a simple adaptation of the proof given in <cit.>. For completeness, here we include the proof.





For the uniform virtual graphs, constructed from the physical graph C_n, if |D|=1 and for some u,e ∈ [0,n-1] if D_u,e = 1 and if _C_n(u,e) ≤d_/2 then the algorithms <ref>, <ref> take O(d_/(log_2 d_)^2) number of entanglement swap operations for distributing an entangled link between u and e.



Let us consider a hierarchy of m+1 nonempty sets, X^(u,e)_0 ⊃ X^(u,e)_1 ⊃ X^(u,e)_2 ⊃…⊃ X^(u,e)_m. Here for all 0≤ i ≤ m, 
    X^(u,e)_i := {u : |u-e| ≤d_/2^i},
 
where 


    m := O(log_2 (d_/log_2 d_)).



Note that, all of the nodes in X^(u,e)_m is at most log_2 d_ distance away from the destination node e. This implies all of the greedy routing algorithms can discover the destination node e using a constant number of entanglement swap operations. 

In a ring network, C_n, one can verify that for all 0 ≤ i ≤ m,


    |X^(u,e)_i| ≥d_/2^i.





As the Algorithms <ref> and <ref> are greedy in nature, this implies they start to discover a path from a node in u∈ X^(u,e)_0 to a node in the set X^(u,e)_m through the nodes in the sets X^(u,e)_1, … , X^(u,e)_m-1. The algorithm stops when the packet reaches X^(u,e)_m. Let the algorithm spends Y^(u,e)_i iterations in the set X^(u,e)_i. According to Algorithm <ref> and <ref> the length of the path is,

    ∑_i=0^m Y^(u,e)_i + Y'^(u,e),

where Y'^(u,e) denotes the length of the path for reaching e from a node in X^(u,e)_m.

For any 0 ≤ i ≤ m-1, suppose the path discovery algorithm has discovered a path from u ∈ X^(u,e)_0 to a node u' such that u' ∈ X^(u,e)_i but u' ∉X^(u,e)_i+1. Let u' → X^(u,e)_i+1 denotes the event that u' has a virtual neighbour in the set X^(u,e)_i+1. In a similar way, by the notation u' ↛X^(u,e)_i+1 we denote the event that u' has no virtual neighbour in X^(u,e)_i+1. Let v ∈ X^(u,e)_i+1, then from equation <ref> we get 

    (u',v) ≥1/2d_.




There are |X^(u,e)_i+1| such v's and each of them is a virtual neighbour of u' with probability (u',v). So, the probability that u' is connected with one of them is,

    ∑_v ∈ X^(u,e)_i+1(u',v)    ≥ |X^(u,e)_i+1| 1/4d_.


In the above expression, by substituting the value of |X^(u,e)_i+1| rom equation <ref> we get,

    ≥d_/2^i+11/4d_
        = 1/2^i+3.


As u' has k=log_2 d_ such virtual neighbours and each of them is identical and independently distributed according to . This implies,  


    [u' ↛X^(u,e)_i+1]    ≤ (1 - |X^(u,e)_i+1|(u',v))^k.

As for all real x and for all r>0 we have, (1-x)^r ≤exp(-xr), this implies,

    [u' ↛X^(u,e)_i+1]    ≤exp(-k|X^(u,e)_i+1|(u',v)).


Substituting the values of (u',v) and |X^(u,e)_i+1| from equation <ref> and <ref> in the above inequality we get,

    [u' ↛X^(u,e)_i+1]    ≤exp(-k/2^i+3)
    
    1- [u' ↛X^(u,e)_i+1]    ≥ 1- exp(-k/2^i+3)

Substituting k = log_2 d_ in the above inequality we get,


    1- [u' ↛X^(u,e)_i+1]    ≥ 1- exp(-log_2 d_/2^i+3)

As for any 0≤ x ≤ 1, 1-e^-x≥x/2, this implies,


    [u' → X^(u,e)_i+1]    ≥log_2 d_/2^i+4.


If the algorithms discover the path to a node u' ∈ X^(u,e)_i, then with probability at least log_2 d_/2^i+4, the algorithms discover another node v ∈ X^(u,e)_i+1. This implies, each step of the algorithm manages to find a neighbour node v ∈ X^(s,e)_i+1 with probability at least log_2 d_/2^i+4. The phenomenon of this finding a node v∈ X^(s,e)_i+1 can be modelled as a sequence of independent trials, where each trial has two outcomes (success and failure) and each trial succeeds with probability at least log_2 d_/2^i+4.This implies the random variable Y^(u,e)_i follows geometric distribution with parameter log_2 d_/2^i+4. This implies,

 


    E[Y^(u,e)_i] ≤2^i+4/log_2 d_.


In equation <ref> we get the expected path length,


    E[∑_i=0^m Y^(u,e)_i    + Y'^(u,e)]
    
    = ∑_i=0^m E[Y^(u,e)_i]    + E[Y'^(u,e)].

Substituting the value of E[Y^(u,e)_i] from equation <ref> in the above expression we get,

    E[∑_i=0^m Y^(u,e)_i + Y'^(u,e)]    ≤∑_i=0^m2^i+4/log_2 d_  + E[Y'^(u,e)]
       ≤ O(d_/(log_2 d_)^2)  + E[Y'^(u,e)].



As m = O(log_2 (d_/log_2 d_)), this implies from any node v ∈ X^(u,e)_m the destination node e is at most log_2 d_ far. All of the proposed algorithms are greedy in nature. This implies, if the path discovery algorithms use the physical neighbours to reach to the destination e then it will take at most O(log_2 d_) number of swap operations. Hence, we can conclude that E[Y'^(u,e)] ≤log_2 d_ < O( d_/(log_2 d_)^2) (for all integer d_≥ 2). Substituting this upper bound in equation <ref> we get the expected path length is 
    E[∑_i=0^m Y^(u,e)_i + Y'^(u,e)] ≤ O(d_/(log_2 d_)^2).

This concludes the proof. 

The proof of lemma <ref> holds for any source destination pair u,e such that _C_n(u,e) ≤d_/2. This implies, we can use this upper bound to prove the upper bound on max_s,e ∈ C_nE[Y_s,e].
Substituting the value of E[Y_s,e] in equation <ref> we get,

    max_s,e ∈ C_nE[|CommPath_s,e|] = O(n/d_ + d_/(log_2 d_)^2)


This proves the upper bound on the number of required entanglement swap operations for both local best effort and modified greedy routing algorithms. For the ease of the reader's understanding, we restate the uniform part of theorem <ref>

Uniform Part of Theorem <ref>: 
In the continuous model, for a uniform virtual graph, constructed from the physical graph C_n, if |D|=1 and for all i,j ∈ [0,n-1] if D_i,j∈{0,1} then for any source destination pair s,e, the expected number of required entangled swap operations for sharing an entangled link between s,e is upper bounded by

    For the routing algorithms <ref> and <ref>
       O(n/d_+ d_/(log_2 d_)^2).


Now, we give the upper bound for the NoN local best effort algorithms. 


 §.§ Proof of the upper bound on the swap operations for NoN local best effort algorithm
  






For the uniform virtual graphs, constructed from the physical graph C_n, if |D|=1 and for some u,e ∈ [0,n-1] if D_u,e = 1 and if for the source destination pair u,e, if _C_n(u,e) ≤d_/2 then the algorithms <ref> take O(d_/(log_2 d_)^2) number of entanglement swap operations for distributing an entangled link between u and e.



Let us consider a hierarchy of m+1 nonempty sets, X^(u,e)_0 ⊃ X^(u,e)_1 ⊃ X^(u,e)_2 ⊃…⊃ X^(u,e)_m such that for all 0≤ i ≤ m, 
    X^(u,e)_i := {u : |u-e| ≤d_/(log_2 d_)^i},
 where


    m = O(log_(log_2 d_)(d_/log_2log_2 d_)).

Note that, all of the nodes in X^(u,e)_m is at most log_2 log_2 d_ distance away from the destination node e. This implies, all of the greedy routing algorithms can discover the destination node e using log_2 log_2 d_ number of entanglement swap operations. 


In a ring network, C_n, one can verify that for all 0 ≤ i ≤ m,


    |X^(u,e)_i| ≥d_/(log_2 d_)^i.



The Algorithm <ref> starts discovering a path from a node in u ∈ X^(u,e)_0 to a node in the set X^(u,e)_m through the nodes in the sets X^(u,e)_1, … , X^(u,e)_m-1. The algorithm stops when the it discovers the destination node in X^(u,e)_m. Let the algorithm spends Y^(u,e)_i iterations in the set X^(u,e)_i. According to Algorithm <ref> the length of the path is,

    ∑_i=0^m Y^(u,e)_i + Y'^(u,e),

where Y'^(u,e) denotes the length of the path for reaching e from a node in X^(u,e)_m.


For any 0 ≤ i ≤ m-1, suppose the path discovery algorithm has discovered a path from u ∈ X^(u,e)_0 to a node u' such that u' ∈ X^(u,e)_i but u' ∉X^(u,e)_i+1. Let u' →_1 X^(u,e)_i+1 denotes the event that u' has a virtual neighbour in the set X^(u,e)_i+1. In Algorithm <ref> we are interested in the fact that whether u' is connected to X^(u,e)_i+1 via a path of length two or not (neighbour of the neighbour). So, we use the notation u' →_2 X^(u,e)_i+1 to denote the event u' is connected to the set X^(u,e)_i+1 via a path of length two. Similarly, the complement of this event is denoted by u' ↛_2 X^(u,e)_i+1.


Let v ∈ X^(u,e)_i+1, then (u',v) ≥1/2d_ (see equation <ref>). 

There are |X^(u,e)_i+1| such v's and each of them is a virtual neighbour of u' with probability (u',v). So, the probability that u' is connected with at least one of them is,

    ∑_v ∈ X^(u,e)_i+1(u',v)    ≥ |X^(u,e)_i+1| 1/2d_

Substituting the value of |X^(u,e)_i+1| from equation <ref> in the above expression we get,

    ∑_v ∈ X^(u,e)_i+1(u',v)    ≥d_/(log_2 d_)^i+11/2d_
        = 1/2 (log_2 d_)^i+1.


As u' has k=log_2 d_ such virtual neighbours and each of them is identical and independently distributed according to . This implies,  


    [u' ↛X^(u,e)_i+1]    ≤ (1 - |X^(u,e)_i+1|(u',v))^k.


Each of the neighbours of u' has again k such virtual neighbours and each of those virtual neighbours are identically and independently distributed according to  . This implies,


    [u' ↛_2 X^(u,e)_i+1]    ≤ (1 - |X^(u,e)_i+1|(u',v))^k^2

As for all real x and r >0 we have, (1-x)^r ≤exp(-xr). This implies 

    [u' ↛_2 X^(u,e)_i+1]     ≤exp(-k^2|X^(u,e)_i+1|(u',v))

In the above expression, by substituting the value of |X^(u,e)_i+1| and (u',v)) from equation <ref> and equation <ref> we get,

    [u' ↛_2 X^(u,e)_i+1]     ≤exp(-k^2/2(log_2 d_)^i+1)

By substituting k = log_2 d_ in the above expression we get


    [u' ↛_2 X^(u,e)_i+1]    ≥exp(-1/2(log_2 d_)^i-1)
    
    1- [u' ↛_2 X^(u,e)_i+1]    ≥ 1- exp(-1/2(log_2 d_)^i-1)


As for any 0≤ x ≤ 1, 1-e^-x≥x/2, this implies,


    [u' →_2 X^(u,e)_i+1]  ≥1/4(log_2 d_)^i-1   .



If the algorithms discover the path to a node u' ∈ X^(u,e)_i, then with probability at least 1/4(log_2 d_)^i-1, the algorithms discover another node v ∈ X^(u,e)_i+1. This implies, each step of the algorithm manages to find a neighbour node v ∈ X^(s,e)_i+1 with probability at least 1/4(log_2 d_)^i-1. The phenomenon of this finding a node v∈ X^(s,e)_i+1 can be modelled as a sequence of independent trials, where each trial has two outcomes (success and failure) and each trial succeeds with probability at least 1/4(log_2 d_)^i-1.This implies the random variable Y^(u,e)_i follows geometric distribution with parameter 1/4(log_2 d_)^i-1. This implies,



    E[Y^(u,e)_i] ≤ 4(log_2 d_)^i-1.


Now, from equation <ref> we get,


    E[∑_i=0^m Y^(u,e)_i + Y'^(u,e)]    = ∑_i=0^m E[Y^(u,e)_i] + E[Y'^(u,e)]
    Substituting the value of     E[Y^(u,e)_i]  from equation <ref> we get
    ≤∑_i=0^m4(log_2 d_)^i-1    + E[Y'^(u,e)]
    ≤ O(d_/(log_2 d_)^2)     + E[Y'^(u,e)].



As m = O(log_(log_2 d_)(d_/log_2 log_2 d_)), this implies from any node v ∈ X^(u,e)_m the destination node e is at most log_2log_2 d_ far. NoN local best effort algorithm is greedy in nature. This implies, if the path discovery algorithm discovers v as the next hop from u, then _C_n(v,e) < _C_n(u,e). Hence, we can conclude that E[Y'^(u,e)] ≤log_2 log_2 d_ < d_/(log_2 d_)^2. This implies, 
    E[∑_i=0^m Y^(u,e)_i + Y'^(u,e)] ≤ O(d_/(log_2 d_)^2).

This concludes the proof. 




The proof of lemma <ref> holds for any source destination pair u,e such that _C_n(u,e) ≤d_/2. This implies, we can use this upper bound to prove the upper bound on max_s,e ∈ C_nE[Y_s,e].
Substituting the value of max_s,e ∈ C_nE[Y_s,e] in equation <ref> we get,

    max_s,e ∈ C_nE[|CommPath_s,e|] = O(n/d_ + d_/(log_2 d_)^2)


This proves the upper bound on the number of required entanglement swap operations for both local best effort and modified greedy routing algorithms. For the ease of the reader's understanding, we restate the uniform part of theorem <ref>.

Uniform Part of Theorem <ref>: 
In the continuous model, for a uniform virtual graph, constructed from the physical graph C_n, if |D|=1 and for all i,j ∈ [0,n-1] if D_i,j∈{0,1} then for any source destination pair s,e, the expected number of required entangled swap operations for sharing an entangled link between s,e is upper bounded by

    For the routing algorithm <ref>
       O(n/d_+ d_/(log_2 d_)^2).











