Linear programs for entanglement and key distribution in the quantum internet

I. INTRODUCTION

• Quantum networks must quantify achievable communication-task rates while serving multiple user pairs or groups over complex noisy-channel structures.The paper motivates efficient capacity estimation as a basis for selecting subnetworks that can quickly satisfy client requests.Source: §I · p. 2
• The recipe replaces quantum channels by capacity-weighted classical links and reduces capacity bounds to flow optimizations expressible as polynomial-size linear programs.The construction uses channel capacities or bounds as edge capacities and leverages classical network methods.Source: §I · p. 2, §II · p. 3
• The framework covers single-pair Bell or private-state distribution, parallel distribution for multiple user pairs, and multipartite GHZ or private-state sharing.The multiple-pair objectives include maximizing total rate or the worst-case pair rate.Source: §I · pp. 2–3, §II · p. 3

II. RESULTS

• The base model uses a finite directed graph with noisy quantum channels, locally processing repeater stations, free classical communication, and channel-use frequencies summing to one.Protocols are adaptive LOCC procedures described by average channel-use frequencies and an asymptotic error parameter.Source: §II · pp. 3–4

A. Bipartite user scenario

• For bipartite users, max-flow min-cut duality converts minimum-cut upper bounds into efficiently computable flow linear programs with channel capacities weighted by usage frequencies.The flow formulation imposes edge-capacity and flow-conservation constraints, enabling linear-program optimization.Source: A. Bipartite user scenario · p. 5
• Lower bounds are realized by distributing Bell pairs on edges and connecting them through edge-disjoint paths, while integer-flow scaling handles the absence of fractional Bell states.The same routing perspective is extended to many user pairs and GHZ distribution through edge-disjoint Steiner trees.Source: §I · p. 3, A. Bipartite user scenario · p. 6
• The bipartite capacities satisfy max(G′,{Q↔(N_e)}_{e∈E}) ≤ Q(G,{N_e}_{e∈E}) ≤ P(G,{N_e}_{e∈E}) ≤ f̄_s→t, with polynomially scaling LPs.For distillable channels, including erasure, dephasing, bosonic amplifier, and lossy optical channels, the bounds become tight.Source: A. Bipartite user scenario · p. 6

Capacity figures of merit

• Total multi-pair capacity maximizes the sum of entanglement or private-state rates across all user pairs, with usage frequencies optimized under a total-frequency constraint.Weighted capacities additionally assign different priorities to user pairs.Source: B. Multiple pairs of users · pp. 6–7
• Sum-rate optimization can be unfair because some user pairs may receive more entanglement than others or none at all.The worst-case figure of merit addresses this by maximizing the least rate achieved by any pair.Source: B. Multiple pairs of users · pp. 6–7

Total multi-pair capacity

• The total-capacity upper bound uses the minimum multicut, but computing minimum multicuts is NP-hard; total multi-commodity flow approximates it within a factor of order O(log r).A multicut disconnects every source-sink pair, whereas multi-commodity flow assigns separately conserved commodities subject to shared edge capacities.Source: B. Multiple pairs of users · p. 7
• 3.5 equals the minimum multicut and the summed concurrent flows in the Figure 3 example, so this instance has no gap.The figure illustrates the multicut and corresponding concurrent flow for three source-sink pairs.Source: B. Multiple pairs of users · p. 7, Figure 3 · p. 8
• The total quantum and private capacities are bounded by a polynomial-size linear program and a multi-commodity-flow upper bound separated by a factor gt(r) of order O(log r).The theorem states max(G′,{Q↔(N_e)}) ≤ Qtotal ≤ Ptotal ≤ gt(r) f̄total.Source: B. Multiple pairs of users · p. 7

Worst-case multi-pair capacity

• Worst-case capacity is upper bounded by the minimum cut ratio, while maximum concurrent multi-commodity flow supplies a lower bound up to a factor gw(r), which can be O(log r).The cut ratio divides cut capacity by the number of separated user pairs, and concurrent flow maximizes the rate simultaneously guaranteed to every pair.Source: B. Multiple pairs of users · pp. 7–8
• The worst-case quantum and private capacities likewise satisfy a polynomial-size linear-program bound using squashed entanglement, max-relative entropy, or, for Choi-stretchable channels, relative entropy of entanglement.The theorem gives max(G′,{Q↔(N_e)}) ≤ Qworst ≤ Pworst ≤ gw(r) f̄worst.Source: B. Multiple pairs of users · p. 8

Multipartite extension

• The multipartite construction uses a minimum Steiner cut for connectivity and a flow linear program; in the example, 1/2 connectivity supports two edge-disjoint Steiner trees for four-user GHZ states.The aggregated repeater protocol creates a Bell-state multigraph, after which generalized entangled swapping connects the Steiner trees into GHZ states.Source: Figure 4 · p. 9, B. Multiple pairs of users · p. 9

C. Multipartite target states

• Steiner trees generalize paths by spanning all users in S, enabling multipartite routing beyond creating a GHZ state at one node and teleporting its subsystems.A Steiner tree in the Bell-state network can be converted into a GHZ state among the users through a generalized entanglement-swapping protocol.Source: C. Multipartite target states · p. 10
• A Steiner tree packing counts edge-disjoint trees spanning S, but computing it is NP-complete, so connectivity-based bounds provide a tractable relaxation.The number of edge-disjoint Steiner trees is lower bounded by S-connectivity up to a factor 1/2 and an additive constant.Source: C. Multipartite target states · p. 10
• The multipartite quantum and private capacities are bounded by linear programs built from graph connectivity and max-flow min-cut arguments.The stated theorem gives the chain max(G′, {Q↔(N e)}e∈E) ≤ QS(G, {N e}e∈E) ≤ PS(G, {N e}e∈E) ≤ ¯fS.Source: C. Multipartite target states · pp. 9–10

III. DISCUSSION

• The framework covers bipartite, multi-pair, and multipartite entanglement or private-state distribution with linear programs whose size scales polynomially in network parameters.The required channel-capacity bounds enter as input parameters, reducing network-capacity bounding to single-channel bounds plus polynomial-time LPs.Source: §III · p. 10
• The bounds are tight for many practical channels in the bipartite case, whereas multi-pair settings retain flow-cut and factor-1/2 gaps tied to computationally hard problems.The flow-cut gap can scale logarithmically with the number of user pairs, and the additional factor-1/2 gap separates polynomial LPs from NP-complete Steiner tree packing.Source: §III · p. 10

A. Bipartite user scenario

• For bipartite communication, rates per total channel use can incorporate flooding, but they have no direct relation to single-path capacities and can differ by O(|E|).The figure contrasts an upper route achieving 0.5 per channel use with a lower route achieving 1/n per channel use, while single-path network-use rates favor the lower route.Source: A. Bipartite user scenario · p. 11, Figure 5 · p. 12

B. Multiple pairs of users

• The paper defines total and worst-case multi-pair quantum capacities per total channel use, with corresponding private capacities defined analogously.These capacities are optimized over adaptive protocols and their LOCC outcomes.Source: B. Multiple pairs of users · p. 13
• Multi-commodity flow treats each source-sink pair as a separate commodity and maximizes either their total flow or their minimum individual flow.The worst-case formulation introduces a variable representing the least flow among all source-sink pairs.Source: B. Multiple pairs of users · pp. 13–14
• Exact max-flow min-cut characterizations generally fail for multiple flows, so the resulting bounds incur flow-cut gaps that scale as O(log r), or O(log r*) for overlapping terminals.For some graph classes, the gap can instead be O(1).Source: B. Multiple pairs of users · p. 14

C. Multipartite target states

• Multipartite quantum and private capacities are defined for users seeking GHZ or multipartite private states, with private capacity upper bounding quantum capacity.Source: C. Multipartite target states · p. 15
• Steiner cuts separate at least one pair of users, while Steiner trees connect all users in the target set without cycles.Source: C. Multipartite target states · pp. 15–16
• The multipartite optimization can be expressed as a max-flow linear program by introducing flow variables for user pairs and maximizing a common slack rate.Source: C. Multipartite target states · p. 15
• The minimum Steiner-cut capacity is the S-connectivity, which is related to the number of edge-disjoint Steiner trees in unit-capacity multigraphs.Source: C. Multipartite target states · p. 16

D. On complexity

• Linear programs for the network scale polynomially in network size, including their iteration counts and total arithmetic operations.Source: D. On complexity · p. 16

A. Preliminaries

• A quantum network is a finite directed graph whose edges are quantum channels, with local quantum processing and public classical communication treated as free resources.Source: A. Preliminaries · p. 17
• Protocols are adaptive LOCC procedures interleaved with channel uses, characterized by average usage frequencies and an asymptotic error parameter.Source: A. Preliminaries · p. 17
• For entanglement distribution, directed channels are represented by an undirected graph that combines capacities of reciprocal edges.Source: A. Preliminaries · p. 17
• An undirected unit-capacity multigraph represents Bell-state networks by replacing each edge with a number of parallel unit-capacity edges determined by its capacity.Source: A. Preliminaries · p. 17

B. Bipartite user scenario

• Bipartite capacities distinguish fixed channel frequencies from optimized frequencies, with the latter corresponding to minimizing total channel uses and being achieved by a single repeater path.Source: B. Bipartite user scenario · p. 18

• For suitable entanglement measures, network capacities are upper-bounded by linear programs derived from channel-wise entanglement quantities.Source: §1 · pp. 18–19
• The fixed-frequency upper bound minimizes the capacity of cuts separating the two users, using an entanglement measure that cannot increase under amortization.Source: §1 · p. 18
• Max-flow min-cut converts the upper-bound problem into maximizing source-to-sink flow in the undirected graph G′.Source: §1 · p. 18
• The flow LP enforces edge-capacity constraints in both directions and flow conservation at every nonterminal vertex.Source: §1 · p. 19
• Optimizing usage frequencies can be incorporated into the LP, yielding a corresponding upper bound for variable-frequency capacities.Source: §1 · p. 19

• Proposition 2 establishes the lower-bound construction for finite directed networks, with limits over scaling and error parameters completing the proof.Source: §2 · pp. 19, 21, 22
• For distillable channels, combining the upper- and lower-bound propositions yields matching capacity characterizations.Source: §2 · p. 19
• A feasible LP flow can be decomposed into paths and scaled so that integer flows correspond to edge-disjoint paths in the unit-capacity multigraph G′′.Source: §2 · pp. 19–21
• The construction generates Bell states across channels at rates determined by usage frequencies, producing a multigraph whose paths can be connected by entanglement swapping.Source: §2 · p. 21
• Optimizing over usage frequencies extends the lower bound to variable-frequency capacities through a corresponding corollary.Source: §2 · p. 22

C. Multiple pairs of users

• Concurrent distribution is evaluated by total throughput, the least guaranteed user-pair rate, or independently weighted pair rates.These criteria distinguish aggregate performance from fairness and allow priorities among user pairs.Source: C. Multiple pairs of users · p. 22
• The worst-case multi-pair capacity maximizes the rate guaranteed simultaneously to every user pair.Source: C. Multiple pairs of users · p. 22
• Weighted multi-pair capacity assigns nonnegative weights q1, ..., qr summing to one to user pairs and optimizes their weighted rates.Equal weights recover the unweighted multi-pair formulation up to normalization, and usage frequencies can also be optimized.Source: C. Multiple pairs of users · p. 22
• The total multi-pair capacity sums achievable rates across all user pairs for a product target of maximally entangled or private states.Source: C. Multiple pairs of users · pp. 22–23

1. Upper bounding the capacity

• Upper bounds for worst-case multi-pair capacity are given by a polynomially sized linear program with a flow-cut gap of order O(log r*).The program maximizes a flow variable constrained below by every source-sink pair's flow.Source: §1 · p. 23
• Upper bounds for total throughput use a multi-commodity-flow linear program whose approximation factor gt(r) is of order O(log r).Its objective sums source-sink flows across commodities, while edge capacities are shared across all commodities and flow conservation applies to each pair.Source: §1 · p. 24
• The worst-case and total-throughput LPs remain valid when channel usage frequencies are included as optimization variables.Source: §1 · pp. 24–25
• Weighted user-pair capacities are formulated by optimizing over a polytope defined by bounds for every subset of user pairs.Using all subsets scales exponentially in r, so upper bounds can instead use selected subsets or only single-pair bounds.Source: §1 · p. 25

2. Lower bounding the capacity

• The lower bounds for worst-case and total-throughput multi-pair capacities are given by the LPs in Supplementary Equations (83)-(86) and (91)-(93).Source: §2 · p. 26
• Feasible worst-case LP flows can be decomposed into concurrently routed paths, whose corresponding Bell-state chains are connected by entanglement swapping.This produces simultaneous entanglement-generation rates for all source-sink pairs.Source: §2 · pp. 27–28
• The total-throughput construction similarly decomposes multi-commodity flows into paths and connects the resulting Bell-state chains for every source-sink pair.Source: §2 · p. 28
• Optimizing channel usage frequencies extends both lower-bound LPs to frequency-optimized formulations.Source: §2 · pp. 28–29
• Weighted capacities are obtained by time-sharing single-pair protocols and optimizing a weighted sum over the resulting convex region.The same region also supports optimization of a general concave target function as a convex optimization problem.Source: §2 · p. 29

D. Multipartite Target States

• Multipartite targets include Greenberger-Horne-Zeilinger states and multipartite private states shared among a disjoint set of users.Source: D. Multipartite Target States · p. 29
• A multipartite private state is constructed by twisting a GHZ key state with an arbitrary shield state.Source: D. Multipartite Target States · p. 29
• Multipartite capacities are defined from the final states produced by adaptive protocols using channel uses, LOCC rounds, and averaged protocol outcomes.Source: D. Multipartite Target States · pp. 29–30
• The multipartite capacities can be optimized over channel usage frequencies.Because multipartite private states include GHZ states, multipartite private capacity upper bounds multipartite quantum capacity.Source: D. Multipartite Target States · p. 30

1. Upper bounding the capacity

• The upper bound is obtained by an LP that maximizes a common flow lower bound across all disjoint user pairs in S.The formulation applies edge-capacity and flow-conservation constraints to every pair.Source: §1 · p. 30
• Taking n →∞ and ϵ →0 yields the multipartite capacity upper-bound proposition for users S.Source: §1 · p. 30
• Optimizing channel usage frequencies extends the upper bound through the same LP with frequency variables included.Source: §1 · p. 30

2. Lower bounding the capacity

• The lower bound is established by Proposition 9, which relates multipartite capacity to the LP-defined S-connectivity.Source: §2 · p. 31
• The proof constructs feasible LP flows from path flows while enforcing edge-capacity and flow-conservation constraints for every disjoint user pair.Source: §2 · pp. 31–32
• An integer flow in the constructed unit-capacity multigraph corresponds to edge-disjoint paths, enabling a protocol through Menger’s theorem.Source: §2 · p. 32
• Bell states along an S-tree are merged into a GHZ state and unwanted parties are removed by projective measurements and Pauli corrections.Source: §2 · p. 32
• The resulting lower bound is expressed through the LP for multipartite S-connectivity and can include optimization over usage frequencies.Source: §2 · pp. 32–33
• The construction takes asymptotic limits in the auxiliary parameters to complete the lower-bound proof.Source: §2 · p. 33

E. Numerical Examples

• The chord-network model has 2^l nodes on a circle, constant-capacity circle edges, and randomly selected diagonal edges whose capacities decrease with distance.Source: E. Numerical Examples · p. 33
• For lossy optical channels, the examples assign c0 = |E|^-1Q↔(N_e) = −|E|^-1 log(1 −η), yielding LP bounds for worst-case and total capacities.Source: E. Numerical Examples · p. 33
• With fixed usage frequencies, circle capacities are exhausted and diagonal edges are used; frequency optimization increases circle capacities and removes the need for diagonal edges.Source: E. Numerical Examples · p. 33