Efficient Quantum Network Communication using Optimized Entanglement-Swapping Trees

Our Contributions. We formulate the entanglement routing problem (§III) in QNs in terms of selecting optimal swapping trees in the “waiting” protocol, under fidelity constraints. In this context, we make the following contributions:

1. 1.

   For the QNR-SP problem, we design an optimal algorithm with fidelity and resource constraints (§IV).

2. 2.

   Though polynomial-time, the above optimal algorithm has high time complexity; we thus also design a near-linear time heuristic for the QNR-SP problem based on an appropriate metric which essentially restricts the solutions to balanced swapping trees (§V).

3. 3.

   For the general QNR problem, we design an efficient iterative augmenting-tree algorithm (§VI), and show its effectiveness w.r.t. an optimal LP solution based on hypergraph-flows.

4. 4.

   We conduct extensive evaluations (§VII) using NetSquid simulator, and show that our solutions outperform the prior approaches by an order of magnitude, while incurring little fidelity degradation. We also show that our schemes can generate high-fidelity EPs over nodes 500-1000kms away.

Qubit States. Quantum computation manipulates qubits analogous to how classical computation manipulates bits. At any given time, a bit may be in one of two states, traditionally represented by $0$ and $1$. A quantum state represented by a qubit is a superposition of classical states, and is usually written as $\alpha_{0}|0\rangle+\alpha_{1}|1\rangle$, where $\alpha_{0}$ and $\alpha_{1}$ are amplitudes represented by complex numbers and such that $|\alpha_{0}|^{2}+|\alpha_{1}|^{2}=1$. Here, $|0\rangle$ and $|1\rangle$ are the standard (orthonormal) basis states; concretely, they may represent physical properties such as spin (down/up), polarization, charge direction, etc. When a qubit such as above is measured, it collapses to a $|0\rangle$ state with a probability of $|\alpha_{0}|^{2}$ and to a $|1\rangle$ state with a probability of $|\alpha_{1}|^{2}$. In general, a state of an $n$ qubit system can be represented as $\Sigma_{i=0}^{2^{n}-1}\alpha_{i}|i\rangle$ where “$i$” in $|i\rangle$ is $i$’s bit representation.

Entanglement. Entangled pure¹¹1In this work, we largely deal with only pure qubit states. Entanglement of general mixed states is defined in terms of separation of density matrices [19]. states are multi-qubit states that cannot be ”factorized” into independent single-qubit states. E.g., the $2$-qubit state $\frac{1}{\sqrt{2}}|00\rangle+\frac{1}{\sqrt{2}}|11\rangle$; this particular system is a maximally-entangled state. We refer to maximally-entangled pairs of qubits as EPs. The surprising aspect of entangled states is that the combined system continues to stay entangled, even when the individual qubits are physically separated by large distances. This facilitates many applications, e.g., teleportation of qubit states by local operations and classical information exchange, as described next.

Teleportation. Direct transmission of quantum data is subject to unrecoverable errors, as classical procedures such as amplified signals or re-transmission cannot be applied due to quantum no-cloning [20, 10].²²2Quantum error correction mechanisms [21, 22] can be used to mitigate the transmission errors, but their implementation is very challenging and is not expected to be used until later generations of quantum networks. An alternative mechanism for quantum communication is teleportation, Fig. 1 (a), where a qubit $q$ from a node $A$ is recreated in another node $B$ (while “destroying” the original qubit $q$) using only classical communication. However, this process requires that an EP already established over the nodes $A$ and $B$. Teleportation can thus be used to reliably transfer quantum information. At a high-level, the process of teleporting an arbitrary qubit, say qubit $q$, from node $A$ to node $B$ can be summarized as follows:

1. 1.

   an EP pair $(e_{1},e_{2})$ is generated over $A$ and $B$, with $e_{1}$ stored at $A$ and $e_{2}$ stored at $B$;

2. 2.

   at $A$, a Bell-state measurement (BSM) operation over $e_{1}$ and $q$ is performed, and the 2 classical bits measurement output $(c_{1}c_{2})$ is sent to $B$ through the classical communication channel; at this point, the qubits $q$ and $e_{1}$ at $A$ are destroyed.

3. 3.

   manipulating the EP-pair qubit $e_{2}$ at $B$ based on received $(c_{1},c_{2})$ changes its state to $q$’s initial state.

Depending on the physical realization of qubits and the BSM operation, it may not always be possible to successfully generate the 2 classical bits, as the BSM operation is stochastic.

Entanglement Swapping (ES). Entanglement swapping is an application of teleportation to generate EPs over remote nodes. See Fig. 1 (b). If $A$ and $B$ share an EP and $B$ teleports its qubit to $C$, then $A$ and $C$ end up sharing an EP. More elaborately, let us assume that $A$ and $B$ share an EP, and $B$ and $C$ share a separate EP. Now, $B$ performs a BSM on its two qubits and communicates the result to $C$ (teleporting its qubit that is entangled with $A$ to $C$). When $C$ finishes the protocol, it has a qubit that is entangled with $A$’s qubit. Thus, an entanglement swapping (ES) operation can be looked up as being performed over a triplet of nodes $(A,B,C)$ with EP available at the two pairs of adjacent nodes $(A,B)$ and $(B,C)$; it results in an EP over the pair of nodes $(A,C)$.

Fidelity: Decoherence and Operations-Driven. Fidelity is a measure of how close a realized state is to the ideal. Fidelity of qubit decreases with time, due to interaction with the environment, as well as gate operations (e.g., in ES). Time-driven fidelity degradation is called decoherence. To bound decoherence, we limit the aggregate time a qubit spends in a quantum memory before being consumed. With regards to operation-driven fidelity degradation, Briegel et al. [23] give an expression that relates the fidelity of an EP generated by ES to the fidelities of the operands, in terms of the noise introduced by swap operations and the number of link EPs used. The order of the swap operations (i.e., the structure of the swapping tree) does not affect the fidelity. Thus, the operation-driven fidelity degradation of the final EP generated by a swapping-tree $T$ can be controlled by limiting the number of leaves of $T$, assuming that the link EPs have uniform fidelity (as in [15]).

Quantum Memories. Multiple quantum memories have been recently proposed to bring quantum networks into realization. Types of quantum memories that support BSM measurements and gate unitary operations, and probably have a long decoherence time can be used in quantum communications. Most of them are matter-based which have photonic interface to produce matter-matter entanglement over two neighboring nodes (see below). At a high-level, there are three different quantum memory platforms: quantum dots, trapped atoms or ions, and colour centers in diamond. Each has its own physical characteristics and applications. While quantum dots have the ability to process quantum information very fast, they exhibit a very low decoherence time among others [25, 26]. To overcome the low efficiency of single atom-photon coupling process, atomic ensemble schemes have been proposed [12] where along with dynamic decoupling and cooling techniques, decoherence times of a few seconds have been achieved [27, 28, 29]. For trapped ion memories, decoherence times from several minutes to few hours have been demonstrated [30, 31]. To further increase the entanglement generation rate, [32] proposes a way to use a single silicon–vacancy (SiV) colour center in diamond to perform asynchronous photonic BSM at the node located in the middle of two adjacent quantum nodes.

Network Model. We denote a quantum network (QN) with a graph $G=(V,E)$, with $V=\{v_{1},v_{2},\ldots,v_{n}\}$ and $E=\{(v_{i},v_{j})\}$ denoting the set of nodes and links respectively. Pairs of nodes connected by a link are defined as adjacent nodes. We follow the network model in [18] closely. Thus, each node has an atom-photon EP generator with generation latency ($t_{g}$) and probability of success ($p_{g}$). Generation latency is the time between successive attempts by the node to excite the atom to generate an atom-photon EP; this implicitly includes the times for photon transmission, optical-BSM latency, and classical acknowledgement. For clarity of presentation and without loss of generality, we assume homogeneous network nodes with same parameter values. The generation rate is the inverse of generation latency, as before. A node’s atom-photon generation capacity/rate is its aggregate capacity, and may be split across its incident links (i.e., in generation of EPs over its incident links/nodes). Each node is also equipped with a certain number of atomic memories to store the qubits of the atom-atom EPs.

Single vs. Multiple Links Between Nodes. For our techniques multiple links between a pair of adjacent nodes can be replaced by a single link of aggregated rate/capacity. Hence we assume only a single link between every pair of nodes. However, distinct multiple links between nodes have been used creatively in [14] (which refers to them as multiple channels); thus, we will discuss multiple links further in §VII when we evaluate various techniques. We note that the all-photonic protocol in [41] is essentially a more sophisticated version of the multi-link WaitLess protocol in [14] to further minimize memory requirements, but it uses multipartite cluster states which are challenging to create. In either case, in terms of selection of paths/trees, the path-selection techniques from [14] should also apply to the all-photonic protocol with certain modifications to account for how the cluster states are generated.

EP Generation Latency of a Swapping Tree. Given a swapping tree and EP generation rates at the leaves (network links), we wish to estimate the generation latency of the EPs over the remote pair corresponding to the tree’s root with the Waiting protocol. Below, we develop a recursive equation. Consider a node $(A,C)$ in the tree, with $(A,B)$ and $(B,C)$ as its two children. Let $T_{AB},T_{BC}$, and $T_{AC}$ be the corresponding (expected) generation latencies of the EPs over the three pairs of nodes. Below, we derive an expression for $T_{AC}$ in terms of $T_{AB}$ and $T_{BC}$; this expression will be sufficient to determine the expected latency of the overall swapping tree by applying the expression iteratively. We start with an observation.

From above, if assume $T_{AB}$ and $T_{BC}$ to be exponentially distributed with the same expected generation latency of $T$, then the expected latency of both EPs arriving is $(3/2)T$. Thus, we have:

Remarks. We make the following remarks regarding the above expression. First, when $T_{AB}\neq T_{BC}$, we are able to only derive an upper-bound on $T_{AC}$ which is given by the above equation but with $T$ replaced by $\max(T_{AB},T_{BC})$.⁴⁴4The 3-over-2 formula as an upper bound has also been corroborated in a recent work [42] which derives analytical bounds on EP latency times in more general contexts. However, in our methods, the above assumption of $T_{AB}=T_{BC}$ will hold as we would only be considering “throttled” trees to save on underlying network resources (see §IV). Second, our motivation for the exponential distribution assumption stems from the fact that the EP generation latency at the link level is certainly exponentially distributed if we assume the underlying probabilistic events to have a Poisson distribution. Third, note that the resulting distribution is not exponential. Despite this, we apply the above equation recursively to compute the tree’s generation latency. However, in our evaluations, we observe the validity of this approximation since our analysis matches closely with the simulation results. Finally, Eqn. (1) is conservative in the sense that each round of an EP generation of any subtree’s root starts from scratch (i.e., with no link EPs from prior round) and ends with either a EP generation at the whole swapping tree’s root or an atomic-BSM failure at the subtree’s root. We do not “pipeline” any operations across rounds within a subtree, which may lower latency; this is beyond this work’s scope.

QNR Single Path (QNR-SP) Problem. Given a quantum network and a source-destination pair $(s,d)$, the QNR-SP problem is to determine a single swapping tree that maximizes the expected generation rate (i.e., minimizes the expected generation latency) of EPs over $(s,d)$, under the capacity and fidelity constraints.

Basic Idea. The main reason for the high-complexity of our DP-based algorithms in §IV is that the goal of the QNR-SP problem is to select an optimal swapping tree rather than a path. One way to circumvent this challenge efficiently while still selecting near-optimal swapping tree, is to restrict ourselves to only “balanced” swapping trees. This restriction allows us to think in terms of selection of paths—rather than trees—since each path has a unique¹⁰¹⁰10In fact, there can be multiple balanced trees over a path whose length is not a power of 2, but, since they differ minimally in our context, we can pick a unique way of constructing a balanced tree over a path. balanced swapping tree. We can then develop an appropriate path metric based on above, and design a Dijkstra-like algorithm to select an $(s,d)$ path that has the optimal metric value. We note that Caleffi [18] also proposed a path metric based on balanced swapping trees, but their metric, though accurate, only had a recursive formulation without a closed-form expression—and hence, was ultimately not useful in designing an efficient algorithm. In contrast, we develop an approximate metric with a closed-form expression, based on the ”bottleneck” link, as follows.

Path Metric $M$. Consider a path $P=(s,x_{1},x_{2},\ldots,x_{n},d)$ from $s$ to $d$, with links $(s,x1),(x1,x2),\ldots,(x_{n},d)$ with given EP latencies. We define the path metric for path $P$, $M(P)$, as the EP generation latency of a balanced swapping over $P$, which can be estimated as follows. Let $L$ be the link in $P$ with maximum generation latency. If $L$’s depth (distance from the root) is the maximum in a throttled swapping tree, then we can easily determine the accurate generation latency of the tree. However, in general, $L$ may not have the maximum depth, in which case we can still estimate the tree’s latency approximately, if the tree is balanced, as follows. In balanced swapping trees, assuming the maximum latency link $L$ to be at the maximum depth, gives us a constant-factor approximation of the tree’s generation latency. Thus, let us assume $L$ to be at the maximum depth of a balanced tree over $P$; this maximum depth is $d=\lceil(\log_{2}|P|)\rceil$. Let the generation latency of $L$ be $T_{L}$. If we ignore the $\mbox{$t_{b}$}+\mbox{$t_{c}$}$ term in Eqn. (1) , then, the generation latency of a throttled swapping tree can be easily estimated to $T(\frac{3}{2\mbox{$p_{b}$}})^{d}.$ The term $\mbox{$t_{b}$}+\mbox{$t_{c}$}$ can also be incorporated as follows. Let $T(i)$ denote the expected latency of the ancestor of $L$ at a distance $i$ from $L$. Then, we get the recursive equation: $T(i)=(\frac{3}{2}T(i-1)+\mbox{$t_{b}$}+\mbox{$t_{c}$})/\mbox{$p_{b}$}.$ Then, the path metric value $M(P)$ for path $P$ is given by $T(d)$, the generation latency of the tree’s root at a distance of $d$ from $L$, and is equal to:

where $\bar{p}=3/(2\mbox{$p_{b}$})$ and $d=\lceil(\log_{2}|P|)\rceil$. The above is a $(1+3/(2\mbox{$p_{b}$}))$-factor approximation latency of a balanced and throttled swapping tree over $P$; this can be shown easily using analysis from §IV-B.

Optimal Balanced-Tree Selection. The above path-metric $M()$ is a monotonically increasing function over paths, i.e., if a path $P_{1}$ is a sub-sequence of another path $P_{2}$, then $M(P_{1})\leq M(P_{2})$. Thus, we can tailor the classical Dijkstra’s shortest path algorithm to select a $(s,d)$ path with minimum $M(P)$ value, using the link’s EP generation latencies as their weights. We refer to this algorithm as Balanced-Tree, and it can be implemented with a time complexity of $O(m+n\log n)$ using Fibonacci heaps, where $m$ is the number of edges and $n$ is the number nodes in the network.

Incorporating Fidelity Constraints. Fidelity constraints in our path-metric based setting can be handled by essentially computing the optimal path for each path-length (number of hops in the path) up to $\tau_{l}$, and then pick the best path among them that satisfies the fidelity constraints. This obviously limits the number of leaves to $\tau_{l}$ and addresses the operations-based fidelity degradation. The above also address the decoherence/age constraint, since it is easy to see (from analysis in §IV-B) that the age of a balanced swapping tree can be very closely approximated in terms of the latency and the number of leaves. Now, to compute the optimal path for each path-length, we can use a simple dynamic programming approach that run in $O(m\tau_{l})$ time where $m$ is the number of edges and $\tau_{l}$ is the constraint on number of leaves.

ITER Heuristic. To solve the QNR problem efficiently, we apply the efficient DP-Approx algorithm iteratively—finding an efficient swapping tree in each iteration for one of the $(s_{i},d_{i})$ pairs. The proposed algorithm is similar to the classical Ford-Fulkerson augmenting path algorithm for the max network flow problem at a high level, with some low level and theoretical differences as discussed below. The iterative-DP-Approx algorithm for the QNR problem consists of the following steps:

1. 1.

   Given a network, we compute maximum EP generation rates for each network link using Eqn. (6). Use these as weights on the link.

2. 2.

   For each $(s_{i},d_{i})$ pair, use DP-Approx algorithm to find the optimal path $P_{i}$, under the capacity and fidelity constraints. Consider a throttled and balanced swapping tree $\mathcal{T}_{i}$ over $P_{i}$. Let $\mathcal{T}^{*}$ be the swapping tree with highest generation rate; if this rate is below a certain threshold, then quit.

3. 3.

   Construct a residual network graph by subtracting the resources used by $\mathcal{T}^{*}$, using Eqn. (7).

4. 4.

   Go to step (1).

Before we present the expressions required above, we would like to point out key differences of our context with the classic network flow setting. Even though we are augmenting our solution one path at a time, the network resources are fundamentally being used by swapping trees created over these paths. These path-flows don’t really have a direction of flow, but we can assign them a symbolic direction from source to the direction. Even with these symbolic directions, the flows in opposite directions over any edge $k$ do not “cancel” each other as in the classical network flow. Moreover, flow conservation law doesn’t hold in our context (e.g., even a path may not use same link rates on all links, due to them being at different depths of the tree), and thus, the max-flow min-cut theorem doesn’t hold. Thus, ITER may not give an optimal solution, even for a single $(s,d)$ pair.

Link EP Generation Rate/Latency. Consider a pair of network node $i$ and $j$ with corresponding current (residual) values of node latencies as $\mbox{$t_{g}$}(i)$ and $\mbox{$t_{g}$}(j)$. Assuming $p_{g}$ values to be same for both nodes, the minimum EP link rate for $(i,j)$ is then given by

Residual Node Capacities. Let $P$ be a path added by ITER, at some earlier stage, and let $\mathcal{T}$ be the corresponding throttled swapping tree over $P$. As in §III, let $R(e,\mathcal{T})$ be the EP generation rate being used by $\mathcal{T}$ over a link $e\in P$, $R_{e}=\sum_{\mathcal{T}}R(e,\mathcal{T})$, and $E(i)$ be the edges incident on $i$. Then, the residual node rates can be calculated similar to Eqn. (2) as follows. Below, $\mbox{$t_{g}$}^{\prime}(i)$ is the original value.

The residual memory capacity is easy to compute—each path/tree uses 2 memory units for each intermediate node, and 1 memory unit for the end nodes.

Swapping Tree Protocol. Our algorithms compute swapping tree(s), and we need a way to implement them on a network. We build our protocol on top of the link-layer of [45], which is delegated with the task of continuously generating EPs on a link at a desired rate (as per the swapping tree specifications). Note that a link $(a,b)$ may be in multiple swapping trees, and hence, may need to handle multiple link-layer requests at the same time; we implement such link-layer requests by creating independent atom-photon generators at $a$ and $b$, with one pair of synchronized generators for each link-layer request. As the links generate continuous EPs at desired rates, we need a protocol to swap the EPs. Omitting the tedious bookkeeping details, the key aspect of the protocol is that swap operation is done only when both the appropriate EP pairs have arrived. We implement all the gate operations (including, atomic and optical BSMs) within NetSquid to keep track of the fidelity of the qubits. On BSM success, the swapping node transmits classical bits to the end node which manipulates its qubit, and send the final ack to the other end node. On BSM failure, a classical ack is send to all descendant link leaves, so that they can now start accepting new link EPs; note that in our protocol, a link $l$ does not accept any more EPs, while its ancestor is waiting for its sibling’s EP. See Fig. 6

Simulation Setting. We use a similar setting as in the recent work [14]. By default, we use a network spread over an area of $100km\times 100km$. We use the Waxman model [49], used to create Internet topologies, to randomly distribute the nodes and create links; we use the maximum link distance to be 10km. We vary the number of nodes from 25 to 500, with 100 as the default value. We choose the two parameters in the Waxman model to maintain the number of links to 3% of the complete graph (to ensure an average degree of 3 to 15 nodes). For the QNR-SP problem, we pick $(s,d)$ pairs within a certain range of distance, with the default being 30-40 kms; for the QNR problem, we extend this range to 10-70 kms.

Parameter Values. We use parameter values mostly similar to the ones used in [18] corresponding to a single-atom based quantum memory platform, and vary some of them. In particular, we use atomic-BSM probability of success ($p_{b}$) to be 0.4 and latency ($t_{b}$) to be 10 $\mu$ secs; in some plots, we vary $p_{b}$ from 0.2 to 0.6. The optical-BSM probability of success ($p_{ob}$) is half of $p_{b}$. We use atom-photon generation times ($t_{g}$) and probability of success ($p_{g}$) as 50 $\mu$sec and 0.33 respectively. Finally, we use photon transmission success probability as $e^{-d/(2L)}$ [18] where $L$ is the channel attenuation length (chosen as 20km for an optical fiber) and $d$ is the distance between the nodes. Each node’s memory size is randomly chosen within a range of 15 to 20 units. Fidelity is modeled in NetSquid using two parameter values, viz., depolarization (for decoherence) and dephasing (for operations-driven) rates. We choose a decoherence time of two seconds based on achievable values with single-atom memory platforms [50]; note that decoherence times of even several minutes [37, 38] to hours [39, 40] has been demonstrated for other applicable memory platforms. Accordingly, we choose a depolarization rate of 0.01 such that the fidelity after a second is 90%. Similarly, we choose a dephasing rate of 1000 which corresponds to a link EP fidelity of 99.5% [15].

Algorithms and Performance Metrics. To compare our techniques with prior approaches, we implement most recently proposed approaches, viz., (i) the WaitLess-based linear programming (LP) approach from [15] (called Delft-LP here), (ii) Q-Cast approach from [14] which is WaitLess-based but uses multiple links and requires memories. The Waiting-based algorithm by Caleffi [18] uses an exponential-time approach, and is thus compared only for small networks. The [16] and [17] approaches are not compared as they were found to be inferior to Q-Cast.

Comparison with [18] for QNR-SP Problem. Note that [18] gives only an QNR-SP algorithm referred to as Caleffi; it takes exponential-time making it infeasible to run for network sizes much larger than 15-20. In particular, for network sizes 17-20, it takes several hours, and our preliminary analysis suggests that it will take of the order of $10^{40}$ years on our 100-node network. See Appendix E. Thus, we use a small network of 15 nodes over a 25km $\times$ 25km area; we consider average node degrees of 3 or 6. See Fig.9. We see that DP-OPT outperforms Caleffi by 10% on a average for the sparser graph and minimally for the denser graph. However, for some instances, DP-OPT outperformed Caleffi by as much as 300% (see Appendix F). We see that DP-Approx performs similar to DP-OPT, while Balanced-Tree is outperformed slightly by Caleffi; however, for this small network, since the DP-OPT and DP-Approx algorithms only take 10-100s of msecs (Appendix E), Balanced-Tree need not be used in practice.

QNR-SP Problem (Single Tree) Results. We start with comparing various schemes for the QNR-SP problem, in terms of EP generation rate. We compare DP-Approx, DP-OPT, Balanced-Tree, SP, and Q-Cast; note that the LP schemes can’t be used to select a single tree, as they turn into ILPs. See Fig. 7, where we plot the EP generation rate for various schemes for varying number of nodes, $(s,d)$ distance, $p_{b}$, and network link density. We observe that DP-Approx and DP-OPT perform very closely, with the Balanced-Tree heuristic performing close to them; all these three schemes outperform the Q-Cast schemes (for $W=5,10$ sub-links) by an order of magnitude. We don’t plot Q-Cast for $W=1$ sub-links, as it performs much worse (less than $10^{-3}$ EP/sec). We note that Q-Cast’s EP rates here are much lower than the ones published in [14], because [14] uses link EP success probability of 0.1 or more, while in our more realistic model, the link EP success probability is $\mbox{$p_{g}$}^{2}\mbox{$p_{e}$}^{2}\mbox{$p_{ob}$}=0.012$ for the default $p_{b}$ value. We reiterate that our schemes require only 2 memory units per node, while the Q-Cast schemes requires $2W$ units. The main reason for poor performance of Q-Cast (in spite of higher memory and link synchronization) is that, in the WaitLess model, the EP generation over a path is a very low probability event—essentially $p^{l}$ where $p$ is the link-EP success probability and $l$ is the path length, for the case of $W=1$ (the analysis for higher $W$’s is involved [14]). Finally, our proposed techniques also outperform the SP algorithm, especially when the number of possible paths (trees) between $(s,d)$ pair increases. In addition, we see that performance increases with increase in $p_{b}$, number of nodes, or network link density, as expected due to availability of better trees/paths; it also increases with decrease in $(s,d)$ distance as fewer hops are needed.

QNR Problem Results. We now present performance comparison of various schemes for the QNR problem. Here, we compare the following schemes: ITER-DPA, ITER-Bal, ITER-SP, Delft-LP, and Q-Cast with the optimal LP as the benchmark for comparison (LP wasn’t feasible to run for more than 100 nodes). See Fig. 8. Our observations are similar to that for the QNR-SP problem results. We see that in all plots, LP being optimal performs the best, but is closely matched by ITER-DPA and the efficient heuristic ITER-Bal. We observe that the performance gap between our proposed techniques and ITER-SP is higher than in the QNR-SP case, as SP picks paths based on just number of links. Our schemes outperform both Delft-LP and Q-Cast by an order of magnitude, for the same reason as mentioned above.

Fidelity and Long-Distance Entanglements. We now investigate the fidelity of the EPs generated. First, we note that the Q-Cast and Delft-LP schemes will incur near-zero decoherence as they involve only transient storage. Decoherence for other schemes is also negligible as the EP generation latencies (10s of msecs) is much less than the coherence time. The operations-driven fidelity loss is expected to be similar for all schemes, as they all roughly use the same order of links. Overall, we observed fidelities of 94-97% across all schemes (not shown), with our schemes also performing better sometimes due to smaller number of leaves.

Long Path Graphs. To test the limits of the schemes in terms of decoherence and fidelity, we consider a long path network and estimate fidelity of EPs generated by schemes for increasing distances and link-lengths (link success probability decreases with increasing link length). Fig. 10(a)-(b) shows EP generation rates and fidelity for path lengths of 500km and 1000km for varying link lengths, for the single-tree schemes DP-Approx and Balanced-Tree. Q-Cast and Delft-LP are not shown as their EP rate is near-zero ($\leq 10^{-20}$) at these distances. We observe that our schemes yield EPs with qubit fidelities of 65-82% and 40-64% for 500km and 1000km paths respectively, with EP rates of 0.05 to 0.65/sec. These are viable results—since qubit copies with fidelities higher than 50% can be purified to smaller copies with arbitrarily higher fidelities [51, 52].

Validating the Analysis; Fairness. Fig. 11(a) compares the EP generation rates as measured by the analytical formulae and the actual simulations for the QNR-SP algorithms DP-Approx and Balanced-Tree. We observe that they match closely, validating our assumption of 3/2 factor in Eqn. (1) and of exponential distributions at higher levels of the tree, and of the path metric $M()$ for Balanced-Tree. Fig. 11(b)-(c) plots the EP generation rates for throttled and non-throttled trees. We see that the throttled tree underperforms the non-throttled tree by only a small margin for the single-tree case; however, for the multi-tree ITER-Bal algorithm, the throttled trees perform better as they are able to use the resources efficiently. Fig. 11(d) plots the average number of $(s,d)$ pairs that get at least one tree/path for varying number of requests; we see that our schemes exhibit 90-99% fairness.

Execution Times. We ran our simulations on an Intel i7-8700 CPU machine, and observed that the WaitLess algorithms as well our Balanced-Tree and ITER-Bal heuristics run in fraction of a second even for a 500-node network; thus, they can be used in real-time. Note that since our problems depend on real-time network state (residual capacities), the algorithms must run very fast. The other algorithms (viz., DP-OPT, DP-Approx, and ITER-DPA) can take minutes to hours on large networks, and hence, may be impractical on large network without significant optimization and/or parallelization. See Appendix G for the plot.