PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Routing in a Quantum Internet

Kaushik Chakraborty, Filip Rozpedek, Axel Dahlberg, Stephanie Wehner

arXiv:1907.11630v1quant-phcs.NI

TL;DR

The paper addresses how to route entanglement with low latency in quantum networks whose devices have noisy memories and limited storage. It proposes distributed algorithms for continuous and on-demand models, analyzes swapping and fidelity, and evaluates them across several topologies and demand levels. Continuous routing helps under low demand, whereas on-demand routing can be preferable in some high-demand scenarios.

  • Problem

    The paper asks how to minimize latency when serving entanglement requests in quantum networks with noisy devices and limited qubit storage.

  • Method

    The paper proposes distributed routing algorithms using physical-topology knowledge and locally known virtual links, and studies continuous and on-demand entanglement models.

  • Results

    Continuous routing reduces latency for low demand, but on-demand routing can outperform it in some high-demand scenarios; simulations compare ring, grid, and recursive networks.

  • Takeaways & Limitations

    Pre-shared entanglement is useful when demand is small, while routing-model choice should depend on demand and network topology.

  • Takeaways & Limitations

    The model assumes stored entangled states have limited lifetimes because quantum-memory noise causes fidelity to decay over time.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper studies distributed routing for quantum networks where entanglement may be generated continuously or on demand. It develops routing algorithms and analyzes latency, topology, entanglement swapping, fidelity, and demand-dependent performance.

  • Motivation: Quantum networks use entanglement and teleportation to transmit qubits, because qubits cannot be copied and teleportation consumes entanglement.Entanglement swapping extends entanglement across intermediary nodes and supports long-distance links.
  • Models: The paper considers on-demand routing over physical links and continuous routing over virtual links formed by pre-shared entanglement.Virtual links can reduce the diameter of the routing graph relative to the underlying physical network.
  • Model design: The model limits both the physical distance and storage time of pre-shared entangled links, making the setting more realistic than approaches without these bounds.The paper also studies continuous models based on different choices of virtual neighbours.
  • Routing approach: It proposes distributed routing algorithms that use physical-topology information and locally available virtual-link information to choose next hops.The algorithms address dynamic virtual graphs and limited entangled-link availability between neighboring nodes.
  • Findings: For low demand, continuous networks reduce latency relative to on-demand routing, while higher demand can remove that advantage and expose weaknesses in classical greedy routing.The study evaluates ring, grid, and recursively generated networks, including deterministic and randomized virtual graphs.

C. Long-Distance Entanglement Creation

The paper models long-distance entanglement creation through elementary-link generation followed by entanglement swapping, while accounting for probabilistic generation, memory decoherence, and routing decisions. Its simplified model yields distance-dependent distribution latency and supports distributed routing with physical and virtual links.

  • Entanglement generation: Long-distance entanglement creation has elementary-link and longer-link stages, with intermediate nodes using entanglement swapping to connect the endpoints.Elementary links are created across physical connections before longer links are formed through swaps.
  • Generation assumptions: The model assumes endpoint entanglement is available only when all elementary links are created within the threshold time Tth.Classical communication time is omitted because Tth is assumed much larger than that communication time.
  • Generation assumptions: The probability of creating an entangled link within Tth is at least (1 −(1 −P0)Tth)d, so expected distribution time increases exponentially with distance d.
  • Memory noise: Stored quantum states decohere under a simplified symmetric depolarising-noise model with parameter p.The model represents memory aging as repeated application of a completely positive trace-preserving map.
  • Network models: The continuous model maintains physical and O(k) virtual neighbours, while the on-demand model stores no pre-shared entanglement and computes shortest physical paths when requests arrive.Continuous links are regenerated after each Tth interval; on-demand links are generated along the selected path.
  • Routing procedure: The routing procedure comprises path discovery, entanglement reservation, and entanglement distribution, with reservation preventing competing demands from using selected links.The algorithms differ mainly in path discovery and in whether they generate links or use already available entanglement.
  • Routing algorithms: The modified and best-effort approaches address a weakness of classical greedy routing by considering available entangled links during path discovery.Classical greedy routing always generates links through the selected neighbour, whereas the best-effort algorithm can choose a neighbour with sufficient existing entanglement.

A. Modified Greedy Routing

The modified greedy and local best effort algorithms use local entanglement availability and physical distance to select progressively closer hops. For a single demand, continuous pre-shared entanglement can reduce waiting relative to on-demand routing, while link fragility limits concurrent use.

  • Modified Greedy Routing: Modified greedy selects a virtual neighbour when enough entangled links exist and the hop preserves a shortest physical-graph distance relation; otherwise it chooses the closest physical neighbour.
  • Local Best Effort Routing: Local best effort first considers neighbours sharing more than D_s,e entangled links, choosing the closest destination-improving hop before falling back to a physical neighbour.
  • Continuous and On-Demand Models: For a single demand, continuous routing avoids entanglement generation during routing, whereas on-demand routing waits for link generation with expected time based on (1 − (1 − P0)^Tth)^d.
  • Latency Bound: The proposed distributed algorithms reduce physical-graph distance by at least one at every path-discovery step, yielding latency upper bounded by O(dthdiamG).
  • Continuous and On-Demand Models: Because pre-shared entangled links are temporary and single-use, multiple demands can rapidly alter the topology and may disconnect the network.
  • Continuous and On-Demand Models: In the continuous model, any two nodes can distribute at least mincutG.cap EPR pairs before regenerating links, by the minimum-cut characterization.

VIII. ANALYSIS OF THE ROUTING ALGORITHMS ON RING AND GRID NETWORK TOPOLOGY

The analysis studies ring and grid physical graphs under deterministic virtual-neighbour constructions. Ring parameters are chosen as powers of two, while virtual links are bounded by the threshold dth.

  • Network Topologies: The analysis considers ring Cn and grid Gridn′×n′ networks, assuming n = 2^m for rings and dth = 2^l with l ≤ m.
  • Deterministic Virtual Links: In the deterministic ring construction, nodes with increasingly divisible identifiers receive virtual neighbours at powers-of-two offsets, capped by dth.
  • Deterministic Virtual Links: The deterministic grid construction assigns virtual neighbours along coordinate directions to nodes whose coordinates have specified powers-of-two divisibility.
  • Deterministic Virtual Links: For dth = 2, even-indexed nodes have two virtual neighbours, while odd-indexed nodes have no long-distance virtual neighbour.

2) Randomly Chosen virtual neighbours:

Random virtual graphs assign neighbours independently, while on-demand routing uses only physical graphs. The analysis bounds swap counts and fidelity for single demands across deterministic, power-law, and uniform constructions.

  • Random Virtual Neighbours: Random virtual graphs give each node log2 dth independently chosen virtual neighbours, while the on-demand model has no virtual neighbours and uses the physical graph.
  • Power-Law Virtual Graphs: For power-law virtual graphs, all routing algorithms cross each partition using a constant number of hops, requiring O(m) swaps overall.
  • Power-Law Virtual Graphs: For local best effort and modified greedy routing on power-law graphs, the required swaps are O(n/dth + log2 dth).
  • Power-Law Virtual Graphs: For NoN local best effort on power-law graphs, the swap bound is O(n/dth + log2 dth log2 log2 dth).
  • Uniform Virtual Graphs: For uniform virtual graphs, local best effort and modified greedy require O(n/dth + dth(log2 dth)^2) swaps.
  • Fidelity Bounds: The swap bounds yield fidelity lower bounds because each swap between links of fidelity F produces an entangled state with fidelity F^2.

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

Simulations examine routing under multiple demands across virtual-graph types and network models, showing that algorithmic performance depends on demand volume, topology, distance, and pre-shared-link availability.

  • Simulation setup: 10000 samples of each demand matrix are averaged to compute the average entanglement distribution latency, with virtual-graph topology updated for each demand value.The simulations use C32 and Grid5×5 physical graphs, with distphys = 10km per time step.
  • Routing comparisons: Local best effort outperforms modified greedy routing for fewer demands, but large demand volumes exhaust pre-shared links and make it converge to the on-demand model.The modified greedy algorithm becomes preferable as the number of demands increases.
  • Model comparison: With four pre-shared EPR pairs per neighbour and demands of at most two pairs, the continuous model outperforms the on-demand model.The advantage is attributed to using pre-shared entangled links.
  • Topology effects: For demands of two to four entangled links, deterministic virtual graphs perform better on rings at high demand, whereas uniformly random virtual neighbours perform better on grids.This topology-dependent reversal is reported for the simulations corresponding to figure 7.
  • Distance and connectivity: Long-distance demands show behaviour similar to high-link-demand simulations, while the continuous–on-demand latency separation is larger on grids than on rings.Higher grid connectivity makes edge-disjoint paths easier to find for different demands.
  • NoN routing: NoN local best effort helps for fewer demands on random virtual graphs but performs worst at higher demand because it consumes existing entangled links fastest.In deterministic ring networks, NoN algorithms provide no advantage.

B. Recursively Generated Virtual Graph

The recursively generated virtual-graph construction models hierarchical quantum-network topologies by repeatedly substituting graph structures, then derives distance properties used for routing analysis.

  • Recursive graph model: Recursive graphs model growing, complex network topologies by repeatedly substituting each eligible edge or subgraph with a fixed graph.The construction is motivated by hierarchical quantum-network structure.
  • Entanglement assumptions: Nodes at different hierarchy levels receive different entanglement-generation capabilities and may pre-share links within a distance determined by dth and the graph diameter.The distance bound is dth(diamGl−l′−1 + 2) for the specified node levels.
  • Construction: In the studied construction, G0 = H = Cn and P = {Cn}; each matching Cn subgraph is expanded by substituting every edge with the base graph.Figures 10 and 11 illustrate the construction for C8.
  • Distance properties: Lemma 4 establishes that virtual neighbours of newly generated nodes remain within the prescribed dth-based distance bound after recursive substitution.The proof tracks how distances expand across recursive levels.
  • Routing analysis: For a single demand with Di,j in {0, 1}, Corollary 2 gives upper bounds on the latencies of routing algorithms 2, 3, and 4 in the continuous model.The bound applies to virtual graphs generated from the specified recursively generated ring graphs.

XI. CONCLUSION AND OPEN PROBLEMS

The paper proposes distributed routing algorithms and continuous pre-shared-entanglement models to reduce quantum-network latency, while identifying demand-dependent trade-offs and open limitations.

  • Pre-shared entanglement reduces latency for networks with a small number of demands, but offers limited advantage at very high demand.
  • The continuous model reduces swap operations through small-diameter virtual graphs, but threshold distance trades lower latency against reduced throughput.
  • Noise-limited storage can increase continuous-model latency, and the role of entanglement distillation remains unstudied.
  • The routing model reserves links during path discovery, requiring stateful nodes and potentially allowing reserved links to become useless before routing completes.
  • The proposed distributed algorithms outperform classical greedy routing in ring and grid simulations, with modified greedy performing best at high demand.
  • Virtual-graph choices trade off latency and fidelity: deterministic graphs perform better in rings, uniform and power-law graphs in grids, and power-law graphs favor end-to-end fidelity.
  • The hierarchical continuous model supports entanglement distribution with very few swaps, while multiple-pair performance remains future work.

APPENDIX

The appendix defines the network notation, states the single-demand swap-operation theorem, and outlines how path-length bounds are proved for several virtual-graph types.

  • Notation: The notation distinguishes physical and virtual graphs, ring networks, hop distances, threshold distance, storage time, neighbour probabilities, demands, and discovered paths.
  • Notation: The demand matrix entry D_i,j denotes how many EPR pairs source i and destination j request, while |D| counts nonzero entries.
  • Theorem 1: Theorem 1 bounds expected swap operations for one binary demand on ring and grid physical topologies when dth > 2.
  • Theorem 1: The bounds depend on whether the virtual graph is deterministic, power-law, or uniform, and on which routing algorithm is analyzed.
  • Theorem 1: For power-law virtual graphs, the stated bounds include O(n/dth + log dth) and O(n/dth + log dth log log dth) forms.
  • Proof framework: The proof framework equates swap count with discovered-path length and decomposes that length into progress across distance-based node sets.

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

For power-law virtual graphs on a ring, the appendix derives expected swap-operation bounds by analyzing greedy progress across distance layers and combining global and local routing costs.

  • The total bound separates progress toward the destination from the final local segment, whose cost differs by routing algorithm.
  • Local best effort and modified greedy use O(log^2 dth) swaps for the final segment, while NoN greedy uses O(log^2 dth log^2 log dth).
  • Power-law neighbour selection supplies the probabilistic progress used to bound layer transitions and path length.
  • In the worst case, the proposed algorithms require O(n/dth) swaps to reach a node within dth of the destination.
  • The resulting theorem applies to a single binary demand and bounds the maximum expected discovered-path length over source-destination pairs.
  • The analysis partitions the ring into distance layers and bounds the expected number of visited nodes between consecutive layers.

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

The proof for local best effort and modified greedy routing bounds the final distance-layer cost by showing that each layer is crossed with constant expected effort.

  • For nodes within dth of the destination, local best effort and modified greedy require O(log^2 dth) swaps.
  • The proof combines this local bound with the earlier power-law progress bound to obtain the theorem’s overall swap-operation guarantee.
  • The proof organizes nodes into nested sets X(u,e) and measures the iterations spent advancing between consecutive sets.
  • Summing the constant expected costs over O(log^2 dth) layers yields the final local bound.
  • Each layer transition succeeds with probability at least 1/32, so its iteration count follows a geometric distribution with constant expected value.

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

The proof bounds the expected swap operations for NoN local best effort routing by analyzing path discovery across a hierarchy of sets near the destination. In the power-law virtual graph, the resulting bound is O(log2 dth log2 log2 dth).

  • Proof setup: The proof partitions nodes into m + 1 nonempty sets X(u,e)_0, ..., X(u,e)_m and analyzes discovery between consecutive sets.The algorithm stops after discovering a path to the destination set X(u,e)_m.
  • Result: O(log2 dth log2 log2 dth) bounds the expected number of entanglement swap operations for distributing an entangled link between u and e.The bound follows from the constant expected work per hierarchy level and the number of levels.
  • Path discovery: Each path-discovery step tests whether a candidate node has a virtual neighbor, or a length-two connection, into the next set.The analysis represents these events using u′ →2 X(u,e)_{i+1} and its complement.
  • Path discovery: The virtual-neighbor selection probability is bounded using βu′ and the distance |u′−v|.The proof substitutes the bound on βu′ to obtain a lower bound involving log2 dth and |u′−v|.

2. This implies,

The analysis converts per-level progress into a global bound for all source–destination pairs within the threshold distance. It concludes the corresponding upper bound for NoN local best effort routing in the continuous power-law model.

  • Per-level progress: At least 1/8 success probability per level makes the iteration count a geometric random variable.The expected iteration count is therefore bounded by a constant at each hierarchy level.
  • Expected bound: The per-level bounds combine across the hierarchy to yield E[Ys,e] ≤ O(log2 dth log2 log2 dth).Ys,e measures the additional swap operations needed after the source reaches a node within distance dth of the destination.
  • Scope: The result applies to every source–destination pair satisfying distCn(u,e) ≤ dth and extends to the maximum expected path length over such pairs.The proof then substitutes this quantity into the total swap-operation bound.
  • Theorem 1: Theorem 1 states that, for a power-law virtual graph on Cn with one demand, NoN local best effort has the stated upper bound on expected entanglement swaps.The theorem concerns the continuous model and maximizes the expectation over source–destination pairs.

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

For uniform virtual graphs on a ring, the proof bounds swap operations by dividing the route into distance-based sets and showing constant expected work per level. This yields an O(n/dth) bound for all three proposed algorithms.

  • Uniform-graph bound: In the worst case, all proposed routing algorithms require O(n/dth) swap operations to connect the source to a node within distance dth of the destination.The bound uses the ring diameter and the maximum physical distance dth between virtual neighbors.
  • Theorem statement: The resulting theorem covers uniform virtual graphs in the continuous model for any source–destination pair and one demand.The proof combines the intermediate bounds for the proposed algorithms.
  • Proof setup: The proof partitions the ring into m′ nonempty sets Z(s,e)_0, ..., Z(s,e)_{m′−1} ordered by distance from the destination.The greedy path discovery process advances between consecutive sets.
  • Per-level analysis: Each level contributes a constant expected number of visits because a node reaches the next set with probability at least 3/4.The resulting waiting time is modeled by a geometric distribution.
  • Global bound: The ring geometry ensures the number of levels is O(n/dth), since source–destination distance is at most n/2.Substituting the level count into the per-level expectation gives the global bound.

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

For nodes within distance dth of the destination, greedy path discovery reaches the destination in O(log2 dth) swaps. Combining this local result with the uniform-graph bound gives an upper bound for local best effort and modified greedy routing.

  • Local routing phase: Ys,e counts additional swap operations after the source has reached a node u within distance dth of destination e.This separates the local routing phase from the earlier route toward the dth-neighborhood.
  • Local guarantee: The modified greedy and local best effort algorithms can distribute an entangled state between nodes u and e when distCn(u,e) ≤ dth.This is the local-distance condition used by the corresponding lemma.
  • Local best effort and modified greedy: The final hierarchy set is at most log2 dth from e, so greedy algorithms can reach the destination using O(log2 dth) swaps.The argument uses physical neighbors to advance through the remaining sets.
  • Expected path length: The proof models progress between hierarchy levels as independent trials and derives geometric waiting times from the per-step success probability.The path length combines the expected work across levels with the remaining distance to e.
  • Combined result: Theorem 1 combines the local bound with the preceding uniform-graph analysis to upper-bound total entanglement swap operations.The stated result applies to both local best effort and modified greedy routing algorithms.

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

The proof analyzes greedy routing through a hierarchy of virtual-neighbor sets and bounds the expected entanglement-swap operations needed to connect a source to its destination. It shows that the destination is reached within a doubly logarithmic number of swaps in the relevant threshold parameter.

  • Proof structure: The proof organizes routing through a hierarchy of m + 1 nonempty sets X(u,e).The algorithm starts from a node in X(u,e)_m and stops after discovering the destination in a lower-level set.
  • Final routing cost: All greedy routing algorithms can discover the destination using log2 log2 dth entanglement swap operations.This follows because the nodes in the final hierarchy set are at most log2 log2 dth distance from the destination.
  • Step success probability: Each routing step finds a virtual neighbor in the next set with probability at least 1/[4(log2 dth)^(i−1)].The resulting number of iterations Y(u,e)_i follows a geometric distribution with that parameter.
  • Greedy progress: The local path-reach cost is at most log2 log2 dth because each greedy hop strictly decreases the physical distance to the destination.This bounds E[Y′(u,e)] for reaching the destination from a node in the final hierarchy set.
  • Swap-operation bound: The analysis proves an upper bound on the number of entanglement swap operations required by the local best effort and modified greedy routing algorithms.The bound applies to source–destination pairs whose physical distance is at most dth^2.
  • Theorem 1: In the uniform continuous model on Cn, the expected number of required entanglement swap operations is upper bounded for any source–destination pair.The result is stated as the uniform part of Theorem 1 for a single request.
Loading 1907.11630v1…