Optimal Entanglement Routing in Quantum Repeater Chains: Beyond Fixed Operation Order and Purification Schedule

I. Introduction

• Finite link capacities and fidelity loss make routing a tradeoff between delivered-pair rate and quality, formalized as maximizing expected end-to-end throughput subject to a fidelity threshold.Swapping extends communication but lowers fidelity, while probabilistic purification raises fidelity by consuming pairs.Source: §I · p. 1
• The framework relaxes fixed purify-then-swap order and pumping-only schedules, using an exact PtS MILP for pumping or tree schedules and an exact DP over arbitrary operation orders.With tree schedule frontiers, the DP is globally optimal across the schedule and operation-order dimensions considered.Source: §I · p. 2
• Under symmetric Pauli noise, pumping converges below unit fidelity, imposing a capacity-independent fidelity ceiling and maximum chain length for pumping-based PtS; tree schedules instead have a capacity-dependent bound.The paper also proves post-swap purification never increases throughput, so free operation order can add feasibility but cannot raise a solution’s throughput.Source: §I · p. 2

II. Related Work

• The optimization formulations rely on structural properties rather than specific state equations, allowing both Werner and two-Bell-state diagonal models without structural re-derivation.The stated properties are diminishing purification returns for the heuristic, log-linear swapping, and objectives that are log-linear for the MILP and decomposable over subpaths for the DP.Source: §I · p. 2, §II · p. 3

I. Introduction

• Tree schedules served over 90% of requests infeasible under pumping at moderate fidelity thresholds, while the tree-based MILP and order-exact DP served identical instance sets.The DP retained a modest throughput advantage on longer chains; arbitrary operation order recovered much of the tree-schedule advantage within the pumping class.Source: §I · p. 2

II. Related Work

• The work solves the path-level routing subproblem on linear chains, while identifying an exact-operation-order gap in prior methods for probabilistic operations and finite capacity.Prior approaches commonly restrict order and, except for, restrict link purification to pumping; the proposed DP separates the roles of order and schedule.Source: §II · p. 3

A. Entangled States and Noise Models

• The paper considers entangled pairs on elementary and virtual links, with fidelity fully characterizing each assumed Bell-diagonal state family and preserved under swapping and purification.The models are symmetric Pauli noise yielding Werner states and single-Pauli-error noise yielding two-Bell-state diagonal states; entanglement holds exactly when F > 1/2.Source: §III · p. 3, A. Entangled States and Noise Models · pp. 3–4

B. Entanglement Protocols

• A link may be elementary or virtual and contain one or more pairs; raw pairs are elementary-link pairs before purification.Swapping and purification act on pairs and thereby transform links.Source: B. Entanglement Protocols · p. 4
• The framework combines swapping, which extends entanglement, with probabilistic purification, which consumes lower-fidelity pairs to produce one higher-fidelity pair.Their fidelity and success-probability update rules provide the physical layer for the purification schedules and optimization framework.Source: B. Entanglement Protocols · p. 4

1) Entanglement Swapping:

• Swapping consumes pairs on consecutive links and uses a Bell-state measurement at their shared node to create a virtual link between the distant endpoints.The section identifies this primitive as enabling long-distance entanglement; it was proposed by Żukowski et al. and experimentally demonstrated by Pan et al..Source: 1) Entanglement Swapping · p. 4
• For both Werner and two-Bell-state diagonal inputs, swapping preserves the input state family, so its action is characterized by a fidelity update rule.The section considers symmetric Pauli noise for Werner states and single-Pauli-error noise for two-Bell-state diagonal states.Source: 1) Entanglement Swapping · p. 4, B. Entanglement Protocols · p. 4
• For equal input fidelities, Werner-state swapping preserves entanglement only when F > (1 + 3)/4 ≈ 0.683, while two-Bell-state diagonal outputs remain entangled for every F ≥ 1/2.Thus the single-Pauli-error model has no swapping threshold beyond the entanglement threshold.Source: 1) Entanglement Swapping · p. 5
• In the Bell parameter, swapping has an identical multiplicative form for both noise models, making end-to-end fidelity composition multiplicative along the repeater chain.The representation uses η = 1 for ideal local operations and selects ξW or ξ2B according to the noise model.Source: 1) Entanglement Swapping · p. 5

2) Purification:

• BBPSSW combines two entangled pairs into one higher-fidelity pair, retaining it only when measurement outcomes coincide.Under the stated link constraint, pairs must have fidelity F > 1/2; purification is probabilistic and consumes pair resources.Source: 2) Purification · p. 5
• Purification is symmetric in its inputs and increases fidelity at the expense of entangled-pair resources and success probability in both noise models.These update rules quantify the fidelity-throughput trade-off underlying the optimization framework.Source: 2) Purification · p. 5

IV. Purification Schedule and Analytical Results

• The section establishes feasibility bounds for pumping and tree schedules and analyzes operation order under the throughput objective.Purification schedule and the order of purification and swapping are identified as two fundamental design axes.Source: §IV · p. 5

A. Pumping and Tree Schedules

• A link schedule is a rooted binary tree whose leaves are raw pairs and whose internal nodes are purification operations; finite capacity determines its parallel width.For a tree using b ≤ c_e raw pairs per output and link capacity c_e, the link runs floor(c_e/b) identical trees in parallel, leaving c_e mod b pairs unused.Source: A. Pumping and Tree Schedules · p. 5
• Pumping repeatedly purifies one stored pair against a raw pair; k rounds consume k + 1 raw pairs and permit floor(c_e/(k + 1)) outputs in parallel.This is the maximally unbalanced tree construction.Source: A. Pumping and Tree Schedules · p. 5
• Balanced trees recursively purify equal-depth pairs, consuming 2^m raw pairs over m levels; their recursion and pumping converge to fundamentally different limits.Unlike pumping, both inputs to each balanced-tree purification are themselves recursively produced balanced trees.Source: A. Pumping and Tree Schedules · pp. 5–6
• The tree class includes all binary purification schedules, with pumping and balanced trees as particular members, so optimization searches all feasible schedules rather than a structured subclass.The pumping class, by contrast, is specified by purification depth k.Source: A. Pumping and Tree Schedules · p. 6

B. Purification limits and feasibility bounds

• Under single-Pauli-error noise, every purification tree with the same number of leaves yields the same output state, cumulative success probability, and raw-pair cost.This equivalence follows from associativity of the purification map in a transformed variable.Source: B. Purification limits and feasibility… · p. 6
• With baseline fidelity 0.8, four raw pairs yield fidelity 0.864 under pumping versus 0.874 under a balanced tree; eight yield 0.870 versus 0.905.Under symmetric Pauli noise, tree shape directly affects achievable fidelity.Source: B. Purification limits and feasibility… · p. 6
• Pumping fidelity rises monotonically to 1 under single-Pauli-error noise but to a unique limit strictly below 1 under symmetric Pauli noise, while balanced-tree fidelity converges to 1 under both models.The pumping limit under symmetric Pauli noise is the unique root of a quadratic; the balanced-tree result holds as the number of raw pairs grows.Source: B. Purification limits and feasibility… · p. 6
• Under symmetric Pauli noise, the per-link pumping limits compose into a PtS fidelity ceiling that makes thresholds above it infeasible, regardless of purification depth or link capacity.For raw-pair fidelity 0.8 over four links, the stated end-to-end ceiling is 0.601; for 0.9, the per-link limit is 0.943 and the end-to-end ceiling is 0.798.Source: B. Purification limits and feasibility… · p. 6

C. Escaping the Pumping Bound

• The pumping bound can be escaped by allowing general tree schedules, relaxing the PtS operation order, or combining both changes.These changes relax the two design restrictions considered in the paper: pumping-only purification and PtS operation order.Source: C. Escaping the Pumping Bound · p. 6

1) Tree Schedules:

• General tree schedules can approach unit fidelity as raw pairs become available, so their achievable per-link fidelity is limited by link capacity rather than raw-pair fidelity.The passage defines Φ_e(c) as the highest fidelity attainable on link e using at most c_e raw pairs and states that it follows a recursion.Source: 1) Tree Schedules · pp. 6–7
• Unlike the capacity-independent pumping bound, the tree-schedule PtS end-to-end bound recedes as link capacity grows.Both bounds assume PtS operation order.Source: 1) Tree Schedules · p. 7
• Post-swap purification can purify the composed end-to-end pair beyond any composition of per-link maxima, although the paper reports that such interleaved sequences rarely exceed the PtS bounds.The passage says Section VII quantifies how rarely this occurs but supplies no numerical rate here.Source: 1) Tree Schedules · p. 7

2) Post-swap purification:

• Post-swap purification strictly reduces expected throughput, though it can raise fidelity enough to meet an otherwise unreachable threshold.Its throughput scaling factor is strictly below one because the available width is halved and purification succeeds with probability below one.Source: 2) Post-swap purification · p. 7
• Interleaving swaps with post-swap purification creates recursive, distributed purification trees that can drive fidelity toward one and escape the PtS pumping bound.For example, pairs swapped across links can subsequently be purified against one another in a balanced structure.Source: 2) Post-swap purification · p. 7

D. Implications for the Optimization Framework

• Under single-Pauli noise, pumping already converges to unit fidelity; under symmetric Pauli noise, tree schedules expand feasibility and throughput, while post-swap purification expands feasibility alone.The latter necessarily sacrifices throughput to reach fidelity targets otherwise unattainable.Source: D. Implications for the Optimization… · p. 7

V. Network Operation Model

• Each routing cycle separates raw-pair generation from purification and swapping, with link capacity ce = floor(Rgen,e · τgen) and cycle length τslot = τgen + τop.The stop-and-wait model stores pairs generated during τgen for use in the subsequent operation phase.Source: §V · p. 7, Figure 4 · p. 8
• The model assumes memory decoherence during generation and neglects operation-phase decoherence; its stop-and-wait pool excludes pipelined or asynchronous generation.The simulations set τgen = 10 ms and τcoh = 1.46 s; the modeled generation-phase fidelity discount is approximately 0.7%.Source: §V · p. 8

A. Problem Formulation

• A routing solution is a tree of SWAP and PUR operations over raw-pair leaves, executed in parallel to produce width W with fidelity Fe2e and success probability P.The objective maximizes expected end-to-end throughput subject to Fe2e ≥ Fth.Source: A. Problem Formulation · p. 8
• PtS forbids post-swap purification, while arbitrary operation orders allow it; exact MILPs handle both schedule classes under PtS, and exact DP handles arbitrary orders.A greedy heuristic is also provided for online operation.Source: A. Problem Formulation · p. 9

VI. Problem Formulation and Algorithms

• The framework is noise-model agnostic through precomputed coefficients, and its PtS formulation has a multiple-choice knapsack structure that is NP-hard in general.The choice-set abstraction supports two MILP instantiations, a greedy heuristic, and two order-exact DP methods.Source: A. Problem Formulation · p. 9

1) Mixed-Integer Linear Programming Formulation:

• Under PtS, logarithms linearize fidelity and success-probability products, yielding an exact MILP for pumping or tree schedules.The two MILP instantiations differ only in their candidate schedules and associated width, success-probability, and Bell-parameter coefficients.Source: 1) Mixed-Integer Linear Programming… · pp. 9–10
• Both PtS MILP instantiations solve in milliseconds at the evaluated chain lengths, despite the underlying resource-allocation problem being NP-hard in general.The linear relaxation is tight in practice, and precomputed logarithmic coefficients decouple the solver from the noise model and schedule class.Source: 1) Mixed-Integer Linear Programming… · p. 10

2) Throughput-First Greedy Heuristic:

• The throughput-first greedy heuristic selects purification steps by marginal log-Bell-parameter gain relative to expected-throughput loss, accounting for capacity bottlenecks.It sweeps candidate bottleneck widths and returns the feasible configuration with the highest throughput.Source: 2) Throughput-First Greedy Heuristic · p. 10

3) Dynamic Programming over Arbitrary Operation Orders:

• Each DP sub-path stores non-dominated configurations tracking fidelity, width, success probability, and the routing tree that constructs the virtual link.The DP applies the exact fidelity composition maps and tests the threshold directly, without linearization.Source: 3) Dynamic Programming over Arbitrary… · p. 10
• For each span, the DP combines adjacent sub-paths by swapping and then post-swap purifying while width permits, retaining intermediate configurations below the fidelity threshold.An inner span may need to preserve width and probability for a sibling span rather than meet the threshold itself.Source: 3) Dynamic Programming over Arbitrary… · p. 10
• The DP filters configurations by fidelity, width, and probability—not throughput alone—and its cost is O(L^3 Cmax^2 log cmax) plus per-link frontier construction.The monotone operations make this Pareto filter sufficiency-preserving; Cmax is the largest retained Pareto set, with no useful a priori bound.Source: 3) Dynamic Programming over Arbitrary… · pp. 10–11
• The DP returns a maximum-throughput routing tree among those satisfying the fidelity constraint, for any given per-link schedule choice set.It searches routing trees over contiguous sub-paths, allowing swaps and purification of virtual links after swaps.Source: 3) Dynamic Programming over Arbitrary… · pp. 10–11

VII. Numerical Results

• The evaluation uses 200 shared-seed instances per plotted point, heterogeneous link fidelities, and default L = 4, ce = 50, and Fth = 0.70 across both noise models.The comparison includes MILP and DP with pumping or tree schedules, Heuristic (tree), Q-PATH, and Chen–Jia per-link; selections are recomposed and checked for exact feasibility.Source: §VII · p. 11
• Blocking probability is the primary metric because blocked requests deliver nothing; median served throughput measures the price of feasibility gains and is reported on a logarithmic axis.Throughput values below 10^-3 are shown at the display floor, and Section VII-B evaluates the caveat of served instances falling below an operator’s minimum rate.Source: §VII · p. 11

A. The Two Noise Models

• Symmetric Pauli noise exposes feasibility differences: pumping blocks 66% at every capacity, while tree methods’ blocking falls from 0.30 to 0.03 as capacity rises from 10 to 150.MILP (pumping) matches the capacity-independent bound; MILP (tree) and DP (tree) match each other and track the capacity-dependent tree bound.Source: §VII · p. 11, Figure 5 · p. 12, A. The Two Noise Models · p. 12
• The single-Pauli-error model yields about 1% blocking for every method and capacity, with pumping and tree instantiations coinciding across all 1,000 instances.The residual blocking comes from two instances with baseline fidelity clipped to 1/2, which carries no entanglement and cannot be improved by purification.Source: A. The Two Noise Models · p. 11, Figure 5 · p. 12
• In the single-Pauli-error model, pumping approaches unit fidelity doubly exponentially, so post-swap purification cannot improve feasibility; only above Fth = 0.999 did a probe show a thin DP advantage.On a 20-instance probe, DP (pumping ≡tree) served two instances that the PtS optimum could not, while blocking differences otherwise vanished.Source: A. The Two Noise Models · pp. 11–12
• Tree methods serve more requests as capacity grows, but instances with throughput below 10^-3 rise from 3% to 24%, limiting blocking reductions at that rate requirement.At a minimum rate of 10^-3, tree-method blocking falls only from 0.325 to 0.265; capacity often converts infeasible requests into feasible, low-throughput ones.Source: A. The Two Noise Models · p. 12, Figure 5 · p. 12
• Under symmetric Pauli noise, DP (pumping) has less blocking than MILP (pumping) but more than tree methods, showing that free operation order recovers part of the tree-schedule advantage.MILP (pumping) has the highest median throughput at every capacity because it serves only the easiest third of instances; tree methods and Heuristic (tree) are close together.Source: A. The Two Noise Models · p. 12, Figure 5 · p. 12
• The single-Pauli-error model eliminates most effects studied, so the remaining numerical sweeps use symmetric Pauli noise as the more physically representative regime.Under the single-Pauli-error model, exact methods coincide in throughput, Heuristic (tree) trails slightly, and Chen–Jia per-link lies well below because it does not coordinate width across links.Source: §VII · p. 11, A. The Two Noise Models · p. 12

B. Fidelity-Threshold Sweep

• At Fth ≤0.70, trees serve >90% of pumping-infeasible requests and 29% at 0.90; MILP (tree) and DP (tree) block identical sets.MILP (pumping) and Q-PATH also block identical instance sets at all eight thresholds.Source: B. Fidelity-Threshold Sweep · pp. 12–13, Figure 6 · p. 13
• With Tmin ≤10^-2, the tree advantage persists, but at Tmin = 1 the tree blocking curve nearly coincides with strict pumping.Tree methods, DP (pumping), and the heuristic reach the display floor in median throughput by Fth = 0.80; MILP (pumping) and Q-PATH stay near 10 pairs per cycle. Deeper tree schedules can reduce width and success probability, making throughput requirements consequential.Source: Figure 7 · p. 13, B. Fidelity-Threshold Sweep · p. 13, Figure 6 · p. 13

C. Chain Length and Runtime

• At L = 6, MILP (pumping) blocks 0.94 versus 0.10 for MILP (tree) and DP (tree); median served throughput falls seven orders from L = 2 to 6.The pumping-class bound defines a maximum chain length for every PtS method in that class.Source: C. Chain Length and Runtime · p. 13, Figure 8 · p. 14
• At L = 6, DP (tree) takes about 25 s versus 1–2 s for MILP (tree), while heuristic (tree) stays below 15 ms at every length.DP (pumping) grows from about 10 ms to about 2 s; at L = 6, DP (tree) reaches 42,688 configurations, and one instance exceeding the 6 GB memory guard is excluded from its statistics.Source: C. Chain Length and Runtime · pp. 13–14, Figure 8 · p. 14

D. Throughput on a Common Instance Set

• On MILP (pumping)’s served instances, every other method returns a solution at least as good per instance; aggregate gains are under 1% in easy settings and a few percent near the feasibility boundary.The gains are insensitive to capacity; the highest-threshold plot uses a 2000-instance extension, while the L = 6 marker represents fewer than 20 common instances.Source: Figure 9 · p. 14, D. Throughput on a Common Instance Set · p. 14

E. Inside the Routing Trees

• Within the pumping class, optimal routing trees that interleave purification and swapping rise from 13% at Fth = 0.55 to 100% at 0.85.In one Fth = 0.70 instance, DP (pumping) uses link depths (2, 2, 3, 2) and one post-swap round to raise throughput from MILP (pumping)’s 0.12 to 0.84, a factor of 7.0.Source: E. Inside the Routing Trees · pp. 14–15

VIII. Conclusions

• Under symmetric Pauli noise, purification schedule chiefly governs feasibility: trees overcome pumping’s capacity-independent fidelity ceiling, while free operation order adds no tree-class feasibility.With tree schedules, the order-exact DP adds at most ∼10% median throughput; under single-Pauli-error noise, the schedule classes do not differ in attainable fidelity.Source: §VIII · p. 15, E. Inside the Routing Trees · p. 15
• The framework combines capacity-aware exact MILP and DP formulations with a low-complexity heuristic, and accommodates different schedule, operation-order, and noise models through model-dependent parameters.The paper identifies extension to general network topologies, including path selection and competition for shared resources, as future work.Source: §VIII · p. 15

A. The Bell basis

• The Bell basis comprises four states generated using H and CNOT, with β0, β1, β2, and β3 corresponding to Φ+, Ψ+, Φ−, and Ψ−.Source: A. The Bell basis · p. 16
• An elementary link ideally shares target state β0; noise produces a mixed Bell-state density matrix whose fidelity is its overlap with β0.Source: A. The Bell basis · p. 16

B. Noise models

• The analysis assumes Pauli noise and contrasts isotropic errors across three Pauli types with a regime dominated by one error type.Source: B. Noise models · p. 16, 2) Symmetric Pauli Noise Model –… · p. 16, 3) Single-Pauli-Error Model —… · p. 16

1) Asymmetric Pauli errors – Bell-diagonal states:

• A Pauli error on one qubit maps Bell states to Bell states, yielding a Bell-diagonal state with fidelity F = pI.Source: 1) Asymmetric Pauli errors –… · p. 16

2) Symmetric Pauli Noise Model – Werner states:

• Under symmetric Pauli noise, pI = F and pX = pY = pZ = (1 − F)/3, producing a Werner state.Source: 2) Symmetric Pauli Noise Model –… · p. 16

3) Single-Pauli-Error Model — Two-Bell-State Diagonal States:

• With only X errors, pI = F and pX = 1 − F, giving a two-Bell-state mixture that models a strongly asymmetric noise regime.The two models distinguish the effect of overall fidelity from that of underlying error structure.Source: 3) Single-Pauli-Error Model —… · p. 16

C. Bell parameter and operation noise

• For entangled states, ξ2B equals two-Bell-state concurrence, while Werner concurrence is C = max{0, (3ξW − 1)/2}; swapping is multiplicative in ξ.Source: C. Bell parameter and operation noise · p. 17
• Operation imperfections reduce the Bell parameter as ξ → ηξ, exactly when operation noise preserves the state family; two-Bell-state diagonal states are not closed under symmetric Pauli noise.Source: C. Bell parameter and operation noise · p. 17

D. Isotropic twirling

• Isotropic twirling maps Bell-diagonal outputs to Werner-family states while preserving target-state population and fidelity.When pI = pmax, it also preserves concurrence.Source: D. Isotropic twirling · p. 17

Appendix B Structural Properties Underlying the Optimization Framework

• The optimization framework applies to both noise models when diminishing returns, log-linearity of swap composition, and objective compatibility hold.Diminishing returns is used only by the heuristic; other models and objectives satisfying these properties can be incorporated without modifying the framework.Source: Appendix B · p. 17

A. Property 1. Purification Limits and Strict Concavity

• The purification-limit analysis formulates pumping recursions for both single-Pauli-error and symmetric Pauli noise.It considers pumping fidelity after k rounds from a raw-pair baseline fidelity.Source: A. Property 1. Purification Limits and… · p. 17, 1) Proof of Proposition 1 · p. 17

1) Proof of Proposition 1:

• For single-Pauli-error noise, pumping fidelity increases strictly to unity as the number of rounds tends to infinity.The proof gives a closed-form solution using the initial error ratio x0 = (1 − F (0))/F (0).Source: 1) Proof of Proposition 1 · p. 17
• Under symmetric Pauli noise, pumping converges monotonically to a fixed fidelity strictly between the raw fidelity and unity.The positive fixed point is in (F (0), 1), and the pumping fidelity increases toward it.Source: 1) Proof of Proposition 1 · pp. 17–18
• Balanced-tree purification converges to unity under both symmetric Pauli and single-Pauli-error noise for raw fidelity above 1/2.For symmetric Pauli noise, each balanced level increases fidelity; for single-Pauli-error noise, the error odds transform as x → x^2.Source: 1) Proof of Proposition 1 · p. 18

• Successive pumping rounds exhibit diminishing returns for both noise-model families.Source: 2) Diminishing returns and concavity · p. 18
• For two-Bell states under the single-Pauli error model, the second finite difference is negative because x0 < 1.This follows directly from Eq. (31).Source: 2) Diminishing returns and concavity · p. 18
• Under symmetric Pauli noise, the fidelity update h(F) is strictly increasing and strictly concave for F (0) ∈ [1/2, 1].Eq. (30) is a Möbius transformation with positive determinant and c > 0 for F (0) > 1/2.Source: 2) Diminishing returns and concavity · p. 18

B. Property 2. Log-Linearity of Swap Composition

• For both symmetric Pauli and single-Pauli noise, swapping composes Bell parameters multiplicatively, making end-to-end fidelity constraints linear in per-link log-Bell parameters.The threshold constraint is the sum of per-link log-Bell parameters bounded below by the log threshold adjusted for swap quality.Source: B. Property 2. Log-Linearity of Swap… · p. 18, 1) Consequence · p. 18

1) Consequence:

• With imperfect swaps η < 1, the log threshold shifts by (L−1) log η while MILP structure is unchanged; imperfect purification changes only precomputed coefficients.The MILP uses each per-link choice’s log Bell parameter as a precomputed coefficient in the fidelity constraint.Source: 1) Consequence · p. 18

1) MILP compatibility:

• An objective expressible as a sum of log-domain quantities with a bottleneck auxiliary variable preserves MILP structure because selection variables have linear coefficients.The coefficients are determined by precomputed log-domain quantities for width, success probability, and Bell parameter.Source: 1) MILP compatibility · p. 18

2) DP compatibility:

• DP compatibility requires split-decomposable objectives, componentwise-monotone operations on (F, W, P), and finite retained sets; the studied throughput objective satisfies these conditions.Dominance must be tested on (F, W, P), not scalar throughput T, because widths compose through a minimum and probabilities through a product.Source: 2) DP compatibility · pp. 18–19

3) Consequence:

• End-to-end success probability and weighted products W^a P^b ξ_e2e^c also admit the MILP and DP under Property 2 and monotonicity; multi-request utilities additionally require capacity coupling.The two noise models studied are examples of this broader objective-compatible class.Source: 3) Consequence · p. 19

Appendix C Greedy Counter-Example and the Width Sweep

• 64%: the MILP’s k=(3, 0, 0) achieves T_e2e = 1.94 at F_e2e = 0.707, versus greedy k=(2, 1, 0)’s T_e2e = 1.18 at F_e2e = 0.740.The greedy choice spends width on a capacity-limiting link, whereas the MILP preserves the bottleneck width; sweeping width downward repairs the choice at a runtime cost of a factor of cmax. The same gap and repair occur over tree frontiers under single-Pauli noise.Source: Appendix C · p. 19

Appendix D Optimality of the DP Framework

• The DP finds the operation sequence with maximum expected throughput subject to the fidelity threshold for a linear chain and an instantiated per-link choice set.The operation set includes raw-pair generation, link-schedule purification, virtual-link self-purification, and swaps of adjacent virtual links.Source: Appendix D · p. 19

A. Dominance Relation

• The Pareto filter retains a configuration only if no other configuration in its set dominates it, with dominance assessed across components rather than scalar throughput.Configurations are represented by fidelity, width, probability, and operation sequence; expected throughput is width times probability. Equal-throughput configurations can behave differently after a swap, so filtering on fidelity and throughput alone could discard the better survivor.Source: A. Dominance Relation · p. 19
• Dominance guarantees nondecreasing throughput and preserves feasibility: a configuration meeting the fidelity threshold remains feasible when replaced by one that dominates it.The feasibility condition is F ≥ Fth.Source: A. Dominance Relation · p. 19

B. Decomposition

• Every longer-span operation sequence decomposes into two subpath sequences joined by a swap and followed by zero or more self-purification rounds.On an elementary link, schedules from the per-link choice set are enumerated directly; Algorithm 1 tries each split and subpath pair, then retains intermediate purification states while width permits.Source: B. Decomposition · pp. 19–20

C. Pareto Sufficiency

• If one configuration dominates another, every operation applicable to the latter is applicable to the former, and its output dominates or equals the latter’s output.Swap is unconditional; purification requires width at least two, which is preserved by dominance. The componentwise monotonicity argument applies in the entangled regime to the fidelity, width, and probability transition maps.Source: C. Pareto Sufficiency · p. 20
• Pareto sufficiency holds for noise models with the stated transition monotonicity and for cumulative-success accounting nondecreasing in probability and fidelity.The same monotonicity makes Pareto filtering of the per-link choice set lossless: a dominated frontier point can be discarded without losing the optimum.Source: C. Pareto Sufficiency · p. 20

D. Global Optimality

• The base pools are sufficient because they exhaust admissible pumping depths or retain the tree-schedule Pareto frontier, and Pareto filtering preserves sufficiency.The tree frontier covers schedules with at most the link capacity in leaves.Source: D. Global Optimality · p. 20
• For longer spans, the algorithm combines dominating sub-path configurations at each split, swaps them, and appends feasible purification rounds before Pareto filtering.The inductive argument uses the decomposition of any sequence into purification after a swap and the fact that dominance preserves applicability.Source: D. Global Optimality · p. 20
• The full-chain pool contains a configuration that matches or exceeds the throughput of any feasible sequence, so maximizing over that pool returns the global optimum.The returned configuration is attainable and feasible, establishing equality with the maximum feasible throughput.Source: D. Global Optimality · p. 20

E. Scope and Caveats

• Theorem 1 assumes uniform pair pools that replicate identical routing trees and excludes heterogeneous pools, cross-chain purification, bypass swapping, and distillation protocols other than BBPSSW.Under pumping, it also excludes link-level recurrence; for two-Bell-state diagonal states this is without loss because schedule shape does not affect throughput, unlike in Werner states.Source: E. Scope and Caveats · pp. 20–21
• The recurrence exclusion is without loss for two-Bell-state diagonal states, where schedule shape does not affect throughput; in Werner states, tree schedules add distinct constructions.The result concerns identical raw-pair costs and shape-independent cumulative success probability in the diagonal-state case.Source: E. Scope and Caveats · pp. 20–21
• The transition maps must be monotone in fidelity, width, and success probability, a condition verified for both noise models considered.Source: E. Scope and Caveats · p. 21
• Exactness is relative to the instantiated choice set: pumping is complete through kmax = 20, while the tree frontier has a certified per-link loss below 10^-3.Proposition 1 states that pumping saturates well before the bound; the tree frontier is built with the ϵ-optimal schedule DP of.Source: E. Scope and Caveats · p. 21
• The result is exact for linear chains; general topologies require path selection, and correctness does not guarantee tractability because Pareto-set sizes lack an a priori bound.Retained Pareto-set sizes are reported empirically in Section VII.Source: E. Scope and Caveats · p. 21