PaperlayerView exact revision on arXiv

Source-linked AI summary

Utility-Based Path Selection and Configuration in Quantum Networks via Layered Shortest Paths

Leonardo Bacciottini, Subhransu Maji, Don Towsley, Gayane Vardoyan

arXiv:2609.16198v1quant-phcs.NI

TL;DR

Quantum-network routing must balance end-to-end rate and fidelity while accounting for configurable rate–quality tradeoffs on individual links. QLSP computes a discretized rate–fidelity frontier with a layered shortest-path algorithm, and the paper reports higher utility than the considered simpler baselines while identifying when scalarization is optimal.

  • Problem

    Rate and fidelity trade off and compose non-additively, and per-link configuration choices make a path’s end-to-end performance depend jointly on its route and settings.

    Source: §I · p. 1

  • Method

    QLSP uses a layered shortest-path computation to obtain the rate–fidelity Pareto frontier for joint path selection and per-link configuration.

    Source: §I · p. 2, §III · p. 4

  • Results

    QLSP outperforms the considered baselines, and experiments find Pareto-optimal candidates that linear scalarization cannot recover in the considered cases.

    Source: §I · p. 2, §VI · p. 10

  • Takeaways & Limitations

    Weighted-sum scalarization is optimal under the stated convex-fidelity condition, while QLSP retains unsupported solutions for nonconvex profiles such as step-like or sigmoidal utilities.

    Source: §I · p. 2

Abstract

from arXiv · show

A path in a quantum network is a chain of repeaters that distributes entanglement between two users. Selecting a path requires balancing the rate and quality (e.g., fidelity) of the delivered entanglement, but these quantities, unlike standard routing metrics, compose non-additively. The problem is compounded by link-level configuration choices (e.g., distillation rounds or emitter brightness tuning), each trading rate against fidelity, so that a path's performance depends jointly on its route and its per-link settings. We cast this joint path selection and configuration problem as a shortest path computation on a layered graph whose layers track discretized end-to-end fidelity. A single run returns the full rate fidelity Pareto frontier, from which the path maximizing any nondecreasing utility function of rate and fidelity can be selected. We prove that for certain utility functions (including the secret key rate of BB84), the method is a fully polynomial time approximation scheme, returning a near-optimal path within a specified tolerance. We further characterize exactly when cheaper scalarization-based routing suffices: it is optimal for utility functions with convex fidelity profiles, but can be arbitrarily suboptimal otherwise (e.g., for step-like, sigmoidal utilities), whereas the layered method remains reliable in all cases.

I. INTRODUCTION

Quantum routing must balance end-to-end rate and fidelity, which trade off and compose non-additively, while also choosing configurations on individual links. The paper introduces QLSP to compute rate–fidelity tradeoffs and characterizes when cheaper scalarization can recover an optimal solution.

I. INTRODUCTION

  • QLSP jointly selects a route and per-link settings by computing the rate–fidelity Pareto frontier, retaining solutions that weighted-sum scalarization cannot recover for some utilities.Scalarization is sufficient under a condition that includes BB84 asymptotic secret key rate; step-like or sigmoidal utility profiles can have unsupported optima.Source: §I · pp. 1–2

II. RELATED WORK

  • Earlier routing methods often optimize rate or throughput, or impose a hard fidelity threshold; utility-based approaches differ in scope and solution guarantees.The paper positions its setting as single-pair routing with arbitrary monotone utilities and approximation guarantees.Source: §II · p. 2

III. MODEL

  • The model represents each link configuration as a rate–Werner-parameter pair and seeks the route and operating points that maximize end-to-end utility.It assumes Werner states; the selected single-path framework excludes time-multiplexing and multipath routing.Source: §I · p. 1, §III · p. 4

IV. METHODS

The methods section presents QLSP as an approximation algorithm for joint path selection and configuration, analyzes its guarantees, and introduces baselines. It also establishes when the surrogate sweep is optimal.

IV. METHODS

  • The methods section presents QLSP as an efficient approximation algorithm for jointly selecting and configuring a path to maximize quantum utility.Its correctness, computational complexity, and approximation guarantee are analyzed.Source: §IV · p. 4
  • The section introduces several baselines for evaluation against QLSP.One baseline is the surrogate sweep algorithm.Source: §IV · p. 4
  • The surrogate sweep is optimal for quantum utility functions with convex fidelity profiles.The section states this result as Theorem 2.Source: §IV · p. 4

A. Quantum layered shortest-path (QLSP) formulation

QLSP reparameterizes rate and fidelity loss so path composition becomes additive, then uses a layered graph to approximate achievable rate–fidelity tradeoffs. Shortest paths across fidelity layers yield candidates for utility-based selection.

A. Quantum layered shortest-path (QLSP) formulation

  • The layered graph maintains the best end-to-end rate for each node and discretized Werner-parameter value, approximating the achievable Pareto frontier.The construction uses fidelity-loss layers and shortest paths to recover an approximately optimal solution.Source: A. Quantum layered shortest-path… · p. 4
  • Reparameterizing rate as X = 1/R and Werner parameter as Y = −ln W makes path updates additive: X′ = X + 1/R_e,a and Y′ = Y − ln W_e,a.Each operating point supplies the rate and Werner parameter used for its edge transition.Source: A. Quantum layered shortest-path… · p. 4
  • Each physical node is replicated across fidelity-loss layers, with operating-point edges advancing the layer and carrying inverse-rate cost.In Fig. 1, alternative settings on an edge create distinct transitions; shortest paths to destination layers give the highest-rate route for each feasible fidelity.Source: A. Quantum layered shortest-path… · p. 4, Figure 1 · p. 5
  • A single Dijkstra run from the source finds candidate paths across reachable destination layers, from which the utility-maximizing path is selected.The candidate rate is the reciprocal of its shortest-path distance, while its exact fidelity is computed for final utility evaluation.Source: A. Quantum layered shortest-path… · pp. 4–5

B. Algorithmic analysis

QLSP uses a layered graph to track discretized end-to-end fidelity while finding the highest-rate path at each fidelity layer. Its approximation guarantees depend on the utility and, for threshold utilities, may require special handling.

B. Algorithmic analysis

  • Dijkstra’s algorithm finds the minimum cumulative inverse rate for each node and fidelity layer, after which QLSP selects the bin maximizing end-to-end utility.The layer index records discretized cumulative Werner parameter.Source: B. Algorithmic analysis · p. 5
  • The layered graph has O(nK) nodes and O(mKA) edges when each of m links has at most A operating points; Dijkstra’s algorithm uses a binary heap.The graph is polynomial in input size and 1/ϵ when K is polynomial in 1/ϵ.Source: B. Algorithmic analysis · pp. 5–6
  • Rounding fidelity loss upward adds at most L∆ cumulative error along any path of at most L edges.For negativity utility, choosing ∆≤ϵ(3Wmin−1)/3L suffices for a (1−ϵ)-approximation.Source: B. Algorithmic analysis · p. 5
  • For a nondecreasing utility with a suitable δ-to-ϵ bound, layer width ∆≤δ/L guarantees utility at least (1−ϵ) of optimal and yields an FPTAS when 1/δ is polynomial in 1/ϵ.For BB84, K = O(L log(1/ϵ)/ϵ); for negativity, K = O(L/ϵ), assuming fixed Wmin bounded away from the zero-utility threshold.Source: B. Algorithmic analysis · pp. 5–6
  • Threshold utilities can drop discontinuously to zero after an arbitrarily small fidelity decrease, so QLSP needs a margin or a rate-layered variant.With margin γ, ∆≤γ/L returns an optimum; without it, the variant discretizes inverse rate and accumulates fidelity loss exactly while retaining a (1−ϵ)-approximation.Source: B. Algorithmic analysis · p. 6

C. Baselines

The baselines choose paths using additive edge costs, a scalarized rate–fidelity objective, or physical distance. The scalarization sweep can recover an optimum for utilities with convex fidelity profiles.

C. Baselines

  • Fixed-cost baselines sum local edge costs, such as local utility or Werner-only cost, then choose each link’s operating point locally and evaluate the resulting path with the true end-to-end utility.The local-utility exponent is set to the network diameter; larger values emphasize fidelity over rate.Source: C. Baselines · p. 6
  • The scalar surrogate sweep minimizes weighted inverse rate and fidelity loss, evaluates each discovered path using true end-to-end utility, and returns the best found solution.Enumerating all supported solutions recovers a globally optimal solution for utilities with convex fidelity profiles.Source: C. Baselines · p. 6
  • The distance baseline first selects a minimum-physical-distance path, then runs QLSP on that fixed path using its available operating points.This separation can work when route choice is largely independent of configuration, such as when homogeneous links make the shortest-distance path dominant.Source: C. Baselines · p. 6

D. Comparison

QLSP substantially outperforms fixed-edge-cost baselines in the considered experiments, while scalarization is exactly optimal for convex fidelity profiles. For nonconvex profiles, scalarization can miss the utility-maximizing Pareto point.

D. Comparison

  • Across the considered graphs and utilities, QLSP substantially outperforms baselines based on fixed edge costs.The surrogate sweep matches QLSP when the utility’s fidelity profile is convex.Source: D. Comparison · p. 6
  • For convex fidelity profiles, a sufficiently fine weighted-sum sweep recovers an exactly optimal utility solution; negativity and BB84 SKR satisfy this condition.The condition is convexity of φ(y) in the additive fidelity-loss coordinate y = −ln W.Source: D. Comparison · pp. 6–7
  • For nonconvex profiles, including thresholds and sigmoids, a utility maximizer can be an unsupported Pareto point that scalarization misses, with a gap arbitrarily large relative to the optimum.The layered frontier retains unsupported points that the lower convex hull omits.Source: D. Comparison · p. 7
  • A single QLSP run returns a discretized rate–fidelity frontier reusable across nondecreasing utilities and destinations; scalarization instead enumerates lower-hull vertices and can require superpolynomially many runs.Continuous operating points can be accommodated under a per-link cost convexity condition, and multiplexing is not advantageous for convex utilities.Source: D. Comparison · p. 7

V. NUMERICAL EVALUATION

The numerical evaluation uses BB84 secret-key rate and a fidelity-threshold utility to illustrate convex- and nonconvex-profile cases. The proof-of-concept examples show how QLSP’s joint route and operating-point choices affect utility.

V. NUMERICAL EVALUATION

  • The evaluation compares BB84 SKR, a convex-profile utility, with a fidelity-threshold utility, a nonconvex-profile case.The threshold is set to Wreq = 0.94, corresponding to Freq = 0.955.Source: §V · p. 7

A. Proof of Concept

  • With threshold Wreq = 0.94, the mixed feasible configuration (1, 4, 3) lets QLSP outperform the baseline by 22.2%.The figure contrasts the unsupported threshold-optimal Pareto point with the surrogate’s hull-supported solution.Source: A. Proof of Concept · p. 7, Figure 3 · p. 8
  • On the small network, QLSP’s mixed operating points (1, 4, 1) achieve the largest end-to-end SKR utility among five candidate solutions.The figure contrasts rate-seeking and fidelity-seeking choices, which sacrifice too much fidelity or rate, respectively.Source: Figure 2 · p. 8
  • For BB84 SKR, the scalarized surrogate matches QLSP in the example, while the threshold requirement makes the optimum unsupported and inaccessible to scalarization.The evaluation uses Wreq = 0.94, corresponding to Freq = 0.955, for the threshold utility.Source: §V · p. 7, Figure 3 · p. 8

B. Comparison with Baselines

Across ER, SURFnet, and protocol-banded-grid evaluations, QLSP exposes frontier solutions missed by scalarization and generally retains more utility than simpler baselines. Runtime and operating-point resolution vary with network size, configuration-menu size, and approximation tolerance.

B. Comparison with Baselines

  • QLSP finds unsupported Pareto-frontier points in all three network settings, which no surrogate weight choice can recover.The evaluation covers spatially heterogeneous links, SURFnet, and heterogeneous protocols.Source: B. Comparison with Baselines · p. 8, Figure 4 · p. 9
  • The distance-path baseline retains approximately 86%–93% of QLSP utility on ER and SURFnet and matches QLSP on the banded grid.Physical-path preselection can be lossless when route and configuration decisions are separable, but heterogeneous lengths or menus can make a longer path preferable after configuration.Source: B. Comparison with Baselines · p. 9
  • Local utility retains 0% to approximately 80% of QLSP utility, while Werner only retains approximately 1%–47%.Their performance varies between BB84 and threshold utility, so a fixed local objective need not align with the application objective.Source: B. Comparison with Baselines · p. 9
  • SURFnet reaches its high-utility regime around A = 7, while the banded grid stabilizes around A = 11; additional operating points then yield marginal gains.The resolution needed for saturation depends on topology and protocol composition.Source: B. Comparison with Baselines · p. 9
  • QLSP solves the 50 × 50 grid with 2,500 nodes and 4,900 links in approximately 11.8 seconds, with observed growth consistent with polynomial worst-case analysis.Runtime grows approximately linearly with A; reducing ε increases explored fidelity layers, yet the ε = 10−6 instance on an 8 × 8 grid takes approximately 5.9 seconds.Source: B. Comparison with Baselines · p. 9
  • The adaptive surrogate is generally faster than QLSP, while distance-path restriction takes approximately 0.28 seconds on the 50 × 50 grid.Path preselection is valuable when independent of link configuration; otherwise, its speed advantage must be weighed against utility losses.Source: B. Comparison with Baselines · p. 9

VI. CONCLUSION

  • The conclusion identifies extensions beyond Werner states, to multipath routing, and to non-Pauli noise models as future directions.The authors report that QLSP reaches higher utility than baselines tracking only rate, fidelity, or local link utility.Source: §VI · p. 10

APPENDIX

The appendix examines time multiplexing and continuous operating points. Convex utility profiles rule out a multiplexing gain, but nonconvex threshold utility can benefit from mixing; continuous tuning also does not eliminate the global scalarization gap.

APPENDIX

  • Continuous operating points do not eliminate the global scalarization gap because the union of path-specific feasible sets need not be convex.Different paths may require different Lagrange multipliers, leaving constrained-optimal configurations unsupported by every global weighted-sum scalarization.Source: APPENDIX · p. 11
  • When the transition matrix has Monge structure, optimal transition indices vary monotonically across layers, enabling all min-plus values in O(K) time or O(K log K) with divide-and-conquer.The appendix describes a hop-indexed dynamic program for incorporating continuous operating points without the K^2 penalty under certain conditions.Source: APPENDIX · p. 11

TIME MULTIPLEXING

  • For utility U(R, F) = R g(F) with convex g, time multiplexing cannot outperform the better of the two solutions, including for negativity and BB84 utilities.For nonconvex utility, multiplexing can improve the outcome.Source: TIME MULTIPLEXING · p. 11
  • A high-rate solution below the fidelity threshold can be mixed with a lower-rate feasible solution to strictly outperform using the feasible solution alone.The optimal mixture uses the largest feasible fraction of the high-rate solution, making the threshold active.Source: TIME MULTIPLEXING · p. 11

CONTINUOUS OPERATING POINTS

Continuous tuning makes each physical path's attainable configurations denser but does not make the global union convex. Consequently, even with fine sampling, QLSP can select an unsupported threshold-utility configuration that scalarization misses.

CONTINUOUS OPERATING POINTS

  • A configuration may be optimal for the constrained routing problem yet unsupported by every global weighted-sum scalarization.Each fixed path may have a convex configuration problem with zero duality gap, while the discrete choice among paths leaves the global achievable set nonconvex.Source: CONTINUOUS OPERATING POINTS · p. 12
  • Finer operating-point sampling fills path-specific attainable regions more densely but does not make their union convex.The illustrative network has three internally disjoint two-link paths; their attainable regions are disjoint in this example.Source: CONTINUOUS OPERATING POINTS · p. 12
  • At A = 257, QLSP selects an unsupported P2 configuration for Uth with Wreq = 0.88, while the surrogate selects P3.Their rates are approximately 6.05 × 10^3 and 4.80 × 10^3 pairs/s, respectively.Source: CONTINUOUS OPERATING POINTS · p. 12

OPERATING POINTS

For convex per-link inverse-rate costs, a hop-indexed dynamic program incorporates continuous operating points through Monge edge relaxations, reducing layer-transition work. The resulting destination layers yield candidate paths whose exact fidelity can be evaluated for utility.

Continuous operating points

  • O(L|E|K log K), or O(L|E|K) with SMAWK, replaces O(L|E|K^2) when convex per-link costs make edge relaxations Monge.The faster transitions avoid examining every source–destination layer pair.Source: OPERATING POINTS · p. 12

Hop-indexed dynamic program

  • Dh(v,k) stores the minimum cumulative inverse rate for paths using at most h edges and ending in layer k; edge relaxations start from D0(s,0)=0, with other states infinite.The recurrence incorporates edge costs ce(j), including costs induced by continuous feasible operating-point sets.Source: OPERATING POINTS · p. 12

Recovered paths

  • Each reachable destination layer yields a candidate path; its layer approximates fidelity loss as k∆, while exact fidelity can be recomputed from its operating points for utility evaluation.The layer's approximate Werner parameter is Wk ≈ e^-k∆.Source: OPERATING POINTS · p. 12

Convexity of the per-link cost

  • The Monge acceleration requires convex minimum inverse-rate cost ce(j); continuous single-click operating points satisfy this condition, and uniform-grid sampling preserves discrete convexity.The single-click inverse-rate cost is decreasing and strictly convex for nonnegative y.Source: OPERATING POINTS · pp. 12–13

Monge structure

  • Monge structure makes minimizing source-layer indices nondecreasing with destination layer, enabling divide-and-conquer or SMAWK edge relaxations.The divide-and-conquer implementation computes all transitions through one edge in O(K log K) time.Source: OPERATING POINTS · p. 13
Loading 2609.16198v1…