PaperlayerView exact revision on arXiv

Source-linked AI summary

Entanglement Distribution in a Quantum Network, a Multi-Commodity Flow-Based Approach

Kaushik Chakraborty, David Elkouss, Bruno Rijsman, Stephanie Wehner

arXiv:2005.14304v1quant-ph

TL;DR

The paper addresses how to maximize EPR-pair distribution rates for multiple source-destination pairs while satisfying end-to-end fidelity requirements, despite probabilistic swaps and the limits of ordinary flow formulations. It presents a polynomial-time LP and path-extraction algorithm, and reports that a prepare-and-swap protocol achieves the rates for the considered setting.

  • Problem

    The paper asks how to maximize entanglement-distribution rates for multiple demands while meeting end-to-end fidelity requirements, since probabilistic swaps disrupt ordinary flow conservation and standard flow formulations give only a loose upper bound.

    Source: §I · pp. 1–2

  • Method

    The authors formulate rate maximization as a polynomial-time LP and use a path-extraction algorithm to obtain per-demand paths and rates.

    Source: §I · p. 1, §IV · p. 11

  • Results

    The authors report that their solution is tight for a particular entanglement-distribution protocol, with prepare and swap achieving the rates produced by path extraction.

    Source: §I · p. 1, §1 · p. 9

  • Takeaways & Limitations

    The approach yields both maximum-rate solutions and paths that a practical prepare-and-swap protocol can use to achieve the corresponding rates.

    Source: §I · p. 1, §1 · p. 9

    The model leaves out realistic parameters such as bounded storage capacity and the time required to perform swaps.

    Source: §IV · p. 11

Abstract

from arXiv · show

We consider the problem of optimising the achievable EPR-pair distribution rate between multiple source-destination pairs in a quantum internet, where the repeaters may perform a probabilistic bell-state measurement and we may impose a minimum end-to-end fidelity as a requirement. We construct an efficient linear programming formulation that computes the maximum total achievable entanglement distribution rate, satisfying the end-to-end fidelity constraint in polynomial time (in the number of nodes in the network). We also propose an efficient algorithm that takes the output of the linear programming solver as an input and runs in polynomial time (in the number of nodes) to produce the set of paths to be used to achieve the entanglement distribution rate. Moreover, we point out a practical entanglement generation protocol which can achieve those rates.

I. INTRODUCTION

The paper seeks to maximize total EPR-pair distribution rates across multiple source-destination demands while meeting each demand’s end-to-end fidelity requirement. It develops a polynomial-time LP and path-extraction algorithm, with fidelity constraints handled through limits on path length.

I. INTRODUCTION

  • The network is modeled as a graph whose edges have capacities for elementary EPR-pair generation, while each demand specifies endpoints, a desired rate, and an end-to-end fidelity requirement.The goal is to maximize the sum of rates across demands.Source: §I · pp. 1–2
  • Probabilistic Bell-state measurements break ordinary flow conservation, and the standard multi-commodity-flow approach gives only a loose upper bound in this setting [23] [24].With such swaps, entanglement generation rate decays exponentially with the number of swap operations.Source: §I · p. 2

B. From the fidelity constraint to the path-length constraint

  • The fidelity requirement matters because each entanglement swap lowers EPR-pair fidelity, so longer paths yield lower end-to-end fidelity.For repeaters unable to distill entanglement, the paper addresses this by bounding path length; it assumes Werner states and elementary-pair fidelity F > 0.5, with each demand’s requirement no greater than F.Source: §I · p. 2, B. From the fidelity constraint to the… · p. 3

I. INTRODUCTION

  • Entanglement swapping lets repeaters extend shared entanglement beyond directly connected nodes, but probabilistic swaps distinguish quantum-network routing from classical flow routing.The paper’s motivating applications include quantum key distribution, clock synchronization, and secure multi-party computation.Source: §I · pp. 1–2

A. Our contributions in a nutshell

  • The edge-based LP has polynomially many variables and constraints, and its equivalence to the path-based formulation establishes that it provides a valid solution.The objective is to maximize total entanglement generation rate across the demands.Source: A. Our contributions in a nutshell · pp. 2–3, §I · p. 2
  • The path-extraction algorithm converts edge-based LP solutions into per-demand paths and rates; the prepare-and-swap protocol achieves those rates asymptotically.Its worst-case running time is O(|V|^4|E||D|).Source: A. Our contributions in a nutshell · p. 3

C. LP-formulation

The edge-based LP represents flows on network edges and uses an expanded graph to enforce path-length limits. Its validity is established by equivalence to a path-based formulation, and prepare and swap can attain the resulting path rates.

C. LP-formulation

  • The formulation treats the network as directed, while an undirected edge can be represented by two oppositely directed edges.A standard LP solver can solve the resulting construction.Source: C. LP-formulation · p. 3, §1 · p. 4
  • The prepare-and-swap protocol is shown to attain the required rate along a path, with the rate depending on edge capacity, path length, and BSM success probability.The edge capacities, path length, and q are identified as the relevant quantities.Source: C. LP-formulation · pp. 3–4

1. Edge-based formulation

  • The edge-based LP assigns variables to network edges, keeping the number of variables polynomial in the number of nodes.Figure 1 illustrates an s-to-e demand and edge EPR-pair generation rates.Source: §1 · p. 4, Figure 1 · p. 4
  • Because shared edges do not reveal route lengths, the formulation borrows length-constrained flow ideas and modifies both the graph and demand set.The construction uses the maximum demand length to determine the expanded graph.Source: §1 · p. 4
  • The expanded graph creates lmax + 1 copies of each node and connects each layer only to the next, preserving the original edge capacity.Figure 2 illustrates this layering for paths limited to two hops.Source: §1 · p. 4, Figure 2 · p. 5
  • Layered routes from s0 to e^j have exactly j hops, allowing an at-most-li demand to be represented by endpoint-specific demands for each permitted length.The example constructs demands from s0 to e1 and e2 for a two-hop limit.Source: §1 · pp. 4–5
  • For each modified demand, gij records flow on each expanded-graph edge; the LP imposes capacity and flow-conservation constraints.The objective maximizes total distribution rate.Source: §1 · p. 4
  • The compact construction alone does not make its validity intuitive; equivalence with the path-based formulation establishes that it solves the rate-maximization problem.The paper presents the equivalence argument as the guarantee that the edge-based solution is valid.Source: §1 · pp. 4–5

2. Path-extraction algorithm

The path-extraction algorithm converts the edge-based LP solution into paths and rates for each demand. The extracted routes respect path-length limits, and prepare and swap can achieve the allocated rates.

2. Path-extraction algorithm

  • The algorithm takes the edge-based LP solution and returns paths and rates for each demand, addressing the LP’s lack of route-level output.It is described as an efficient method for extracting the paths and rates.Source: §2 · pp. 5–6
  • The extracted paths satisfy each demand’s path-length constraint, and prepare and swap can achieve the rates allocated to them.A four-link repeater-chain example illustrates the protocol’s rate calculation.Source: §2 · p. 5, Figure 3 · p. 5
  • For each modified demand, the algorithm finds a path using positive-flow edges and allocates a rate based on the minimum flow along that path.The allocation also incorporates the BSM success probability for the corresponding path length.Source: §2 · p. 6

3. Example

The example applies the edge-based LP and path-extraction algorithm to an assumed quantum version of the 50-node SURFnet topology. The methods section outlines how fidelity limits, LP optimization, and path extraction form the rate-maximization procedure.

3. Example

  • The example treats the 50-node Dutch SURFnet classical topology as a quantum network of atomic-ensemble, linear-optics repeaters.Elementary-pair generation is assumed deterministic, with rates chosen uniformly from 1 to 400 EPR-pairs per second and BSM success probability q = 0.5.Source: §3 · p. 6, Figure 4 · p. 6
  • The example assumes unit-efficiency on-demand memories and a minimum storage time of 500 µs, based on a maximum 50 km fiber length.The storage-time assumption uses the maximum round-trip communication time between directly connected nodes.Source: §3 · p. 6
  • With elementary-pair fidelity F = 0.9925, four random demands, and random end-to-end fidelity requirements from 0.93 to 0.99, the resulting maximum path length is 8.The demands are optimized in parallel; their rates and paths are referenced in Figure 5.Source: §3 · p. 6

III. METHODS

  • The methods section also covers the path-based formulation, its equivalence to the edge-based formulation, prepare and swap, and complexity analysis.The paper states that prepare and swap achieves the optimized rates along the extracted paths.Source: §III · pp. 6–7
  • The overall method converts each fidelity requirement into a path-length limit, builds the modified graph and demands, solves the edge-based LP, then extracts paths and rates.The procedure is summarized as Algorithm 2.Source: §III · p. 7

A. Path-based formulation

The path-based formulation assigns a rate variable to each demand path and imposes a path-length cap. It also provides a basis for proving equivalence with the edge-based formulation through a modified network and demand set.

A. Path-based formulation

  • Each path p for a source-destination pair has a rate variable r_p, and a demand's total rate can be split across multiple paths.The path-based formulation expresses each path's achievable rate separately.Source: A. Path-based formulation · p. 7
  • For demand (45, 40, 7), Figure 5 shows two extracted paths, each of length 6, with thick edges marking edges used by paths.End-nodes are shown as square boxes.Source: Figure 5 · p. 7
  • The path-based formulation has O(|V|!) variables, making it unsuitable for solving the maximum-flow problem directly, though it helps prove the edge-based formulation's validity.The passage notes that the edge-based formulation is more efficient to use for solving the problem.Source: A. Path-based formulation · p. 7
  • The formulation restricts every path for demand i to length at most l_i, as specified in Table II.This path-length constraint is written as |p| ≤ l_i for every path p in P_i.Source: A. Path-based formulation · pp. 7–8, Table II · p. 8

B. Equivalence between the two formulations

  • The equivalence proof constructs solutions in both directions and first rewrites the path-based formulation on the modified graph and demand set.The proof's two constructions are intended to establish that the formulations are equivalent.Source: B. Equivalence between the two… · p. 8

1. Path-based formulation on the modified network

  • On the modified graph, each i,j demand has paths of length j, and the original demand's path set is the union of these sets across its allowed lengths.The construction decomposes each original demand into demands indexed by path length.Source: §1 · p. 8

2. Path-based formulation to edge-based formulation

  • The conversion defines edge-based flow by aggregating path rates with a q^(j−1) factor, yielding feasible edge constraints and the same objective value.The conversion constructs the edge-based solution from the modified-network path solution.Source: §2 · pp. 8–9

3. Edge-based formulation to path-based formulation

The path-extraction construction turns an edge-based solution into a feasible path-based solution, establishing equivalence between the formulations. The paper then relates those path rates to a prepare-and-swap protocol for chains and arbitrary networks.

3. Edge-based formulation to path-based formulation

  • Algorithm 1 extracts paths and corresponding rates from the edge-based solution, updating residual edge values as paths are allocated.The construction starts from the edge-based values and computes a rate for each extracted path.Source: §3 · p. 9
  • The extracted paths and allocated rates form a feasible path-based solution, and together with the reverse construction this establishes equivalence of the formulations.The two formulations have the same objective value under the described constructions.Source: §3 · p. 9

1. Prepare and swap protocol for a repeater chain

  • The prepare-and-swap protocol generates elementary entanglement links in parallel and swaps when both neighboring links are ready, assuming deterministic link generation.Probabilistic swaps lower the generation rate, while independent swaps avoid requiring long storage times.Source: §1 · p. 9
  • For the repeater chain, the expected end-to-end rate is q^(n−1) times the minimum elementary-link capacity under the stated deterministic-generation assumption.The expression is given for a chain with n + 1 repeaters and successful BSM probability q.Source: §1 · p. 9
  • The prepare-and-swap rate matches the path-based rate expression, so the rates extracted by Algorithm 1 are achievable with this protocol.This conclusion follows from the equivalence of the path-based and edge-based formulations.Source: §1 · p. 9

2. Prepare and swap protocol for an arbitrary network

  • For multiple demands sharing links, paths can be served sequentially or round-robin, with memory storage time bounded by the path's largest link-use time.The protocol assumes deterministic elementary-link generation, and the bound is given as an upper bound on average memory storage time.Source: §2 · pp. 9–10

D. Complexity analysis

The analysis establishes polynomial scaling for both the rate-maximising LP and path extraction. The conclusion qualifies the guarantee by protocol choice and identifies model extensions.

D. Complexity analysis

  • The edge-based LP has polynomially many variables and constraints, so its solver computes the maximum achievable rate in polynomial time.The stated bounds are N = |D||E||V| variables and M = |V|^2|E||D| + |V||E| + |V|^2|D| constraints.Source: D. Complexity analysis · pp. 10–11
  • Algorithm 1 extracts at most |V||E| paths for each demand.The bound follows from the modified graph's edge count.Source: D. Complexity analysis · p. 11
  • Path extraction runs in O(|D||V|^4|E|) time in the worst case.The bound assumes discovered path lengths can scale with |V|; the authors note that allowed lengths may grow more slowly in practical scenarios, making extraction faster.Source: D. Complexity analysis · p. 11, §IV · p. 11

IV. CONCLUSION

  • Without distillation, end-to-end fidelity drops sharply with path length, so the worst-case path-length assumption may overstate practical extraction time.The conclusion says allowed path length should increase slowly with network size in practical scenarios.Source: §IV · p. 11
  • The approach can also be extended to objectives such as minimizing weighted edge congestion.Source: §IV · p. 11
  • Future formulations could include bounded storage capacity and swap-operation time to support more realistic routing algorithms.Source: §IV · p. 11
  • The LP rate is optimal for the prepare-and-swap protocol, which can achieve the extracted path rates, but more sophisticated protocols may achieve higher rates with more quantum storage time.The protocol is described as practical and requiring very little quantum storage time.Source: §IV · p. 11

Appendix A: Outline

The appendix outlines the equivalence proof between path-based and edge-based formulations, then sets out the network and demand notation and the modified graph used in the proof.

Appendix A: Outline

  • The appendix proves equivalence by constructing an edge-based solution from a path-based solution and vice versa.It also outlines a description of how prepare-and-swap achieves the distribution rate across a path.Source: Appendix A · pp. 12–13

Appendix B: Notations

  • The notation defines a directed network with edge capacities for EPR-pair generation and demands whose paths have specified maximum lengths.A demand is a source-destination pair together with its path-length limit.Source: Appendix B · p. 13

Appendix C: Equivalence of the path-based and edge-based formulation for the prepare and swap protocol

  • The modified graph creates layer copies of each node and advances each original edge by one layer, enabling length-limited paths to be represented in the expanded graph.For a demand with limit l_i, the construction decomposes it into demands from the source's layer-0 copy to destination copies at the permitted layers.Source: Appendix C · p. 13

1. Path-based formulation

The path-based formulation represents flow on paths in the modified network and maximizes the total flow over the transformed demands.

1. Path-based formulation

  • The formulation is written for demands in the modified network G′ and their corresponding path sets.Source: §1 · p. 13
  • For each path in a transformed demand's path set, r_p denotes the flow sent along that path.Source: §1 · p. 13
  • The objective maximizes the sum of path flows, and Table IV presents the formulation on the modified network.Source: §1 · p. 13, Table IV · p. 13

2. Edge-based formulation

The edge-based formulation assigns an edge-flow function to each transformed demand in the modified network.

2. Edge-based formulation

  • The edge-based formulation uses the modified graph G′ and its transformed demands.Source: §2 · p. 13
  • For each transformed demand indexed by i and j, the formulation defines g_ij as a function from E′ to nonnegative reals.Source: §2 · p. 13
  • Table V gives the edge-based formulation.Source: §2 · p. 13

3. From the path-based formulation to the edge-based formulation

The section maps a solution of the path-based formulation to a valid solution of the edge-based formulation, showing that the edge-based formulation is at least as good.

3. From the path-based formulation to the edge-based formulation

  • The edge-based formulation is shown to be at least as good as the path-based formulation.The proof starts from a path-based solution and constructs an edge-based solution.Source: §3 · p. 13
  • The construction defines edge flows from the path-based solution and uses them to establish the edge-based formulation’s constraints.The section defines the constructed function in equation C9 and checks constraints C6–C8.Source: §3 · pp. 14–15
  • The constructed edge-based solution is valid and corresponds to the path-based solution’s objective value.Propositions 2–4 establish the objective correspondence and verify the edge-based constraints.Source: §3 · p. 15

4. From the edge-based formulation to the path-based formulation

Algorithm 3 decomposes an edge-based solution into paths and rates; the section establishes that this extraction preserves feasibility and the objective while using at most |E′| paths per demand.

4. From the edge-based formulation to the path-based formulation

  • Each iteration finds a path of positive residual flow and assigns it the minimum residual edge flow, scaled by (q)^(j−1).The algorithm subtracts the allocated rate along the discovered path before searching for another.Source: §4 · p. 16
  • For each demand, the algorithm extracts at most |E′| paths because every iteration zeros at least one edge’s residual flow.The proof bounds the number of iterations by the number of edges in the modified graph.Source: §4 · p. 16
  • The extraction preserves flow conservation and edge-capacity constraints, so the resulting path rates satisfy the path-based formulation’s feasibility conditions.The proof relates residual flows to the original edge flow and shows the accumulated extracted rates remain bounded by edge capacities.Source: §4 · pp. 16–17
  • The extracted path rates preserve the edge-based objective, yielding a path-based solution with the same objective value.The section proves equivalence of the objective functions after the algorithm has extracted the paths.Source: §4 · pp. 17–18

Appendix D: Prepare and swap protocol

For the prepare-and-swap protocol, the expected end-to-end rate in a repeater chain is the bottleneck link capacity discounted by the probability of successful swaps.

Appendix D: Prepare and swap protocol

  • The expected rate across a chain is (q)^(n−1) min{C0, …, Cn−1}.The lemma assumes elementary-pair generation succeeds with probability one and each successful Bell-state measurement has probability q.Source: Appendix D · p. 18
  • Elementary pairs are generated in parallel at each link, with each link producing Ci pairs per second.The chain has n elementary links, with capacities C0 through Cn−1.Source: Appendix D · p. 18
  • Independent swaps reduce the rate by the probability that all required swap operations succeed.The lemma states that each swap succeeds with probability q and gives the resulting expected-rate expression.Source: Appendix D · p. 18
Loading 2005.14304v1…