A Bi-Objective Routing Framework for Hybrid Terrestrial-Satellite Quantum Networks

AI summary

Overview

Research area: Quantum networking — routing and resource allocation in hybrid terrestrial–satellite quantum networks, combining quantum routing theory with bicriterion network optimization (MAXMIN–MINSUM path problems, Pareto frontiers).

Technical level: Advanced. The paper assumes familiarity with entanglement swapping, Werner states, SPDC sources, and multi-objective shortest-path algorithms.

Scope: A single paper presenting a bi-objective (entanglement generation rate vs. fidelity) routing framework for hybrid fiber–LEO-satellite quantum networks, including an exact polynomial-time algorithm and a simulation study over the continental United States.

What This Paper Is About

Long-distance entanglement can be distributed over fiber links, over satellite free-space links, or over a mixture of both — and each route yields a different entanglement generation rate (EGR) and a different fidelity. The authors argue that existing routing algorithms collapse this into a single objective (maximize EGR, or maximize fidelity, or optimize one subject to a threshold on the other), which hides the rate–fidelity trade-off. Their goal is to compute, in polynomial time, the complete set of Pareto-optimal paths so that each application can choose the operating point matching its own requirements.

Key Contributions

1. Bi-objective formulation. Routing in a time-varying hybrid quantum network is formulated as a joint maximization of end-to-end EGR and end-to-end fidelity, rather than a single-metric optimization.
2. Structural transformation. The authors exploit the bottleneck (min-over-path) form of end-to-end EGR and convert the multiplicative fidelity objective into an additive cost via the transformed edge cost C_e = -log W_e, where W_e = (4F_e - 1)/3 is the Werner parameter. This reformulates routing as a MAXMIN–MINSUM bicriterion path problem.
3. Exact polynomial-time Pareto computation. Using Martins' bicriterion routing algorithm — iteratively solving Dijkstra's shortest-path problem on transformed fidelity costs and pruning all edges with EGR not exceeding the current bottleneck — they compute a minimal complete Pareto set, with complexity O(|E(t)|(|E(t)| + |V|) log |V|).
4. Evaluation on realistic topologies. A 24-hour simulation study comparing hybrid vs. terrestrial-only networks and the proposed Pareto policy against three baselines (Max-Fidelity, FC-MaxEGR, Distance-Based), including application-aware utility evaluation for three utility functions.

Main Findings

• Richer frontiers in hybrid networks. For a medium-distance pair, the terrestrial-only network has a single Pareto-optimal path in most time slots, whereas the hybrid network "often exceeds ten." For long-distance pairs the count is smaller — one or two paths (as far as the provided text reports).
• Satellite links help all policies. Adding satellite-assisted links increases both average EGR and average fidelity for all routing policies relative to the terrestrial-only network.
• Day/night asymmetry in virtual links. At night, free-space links maintain nearly constant average fidelity (≈ 0.97) and rate (> 10⁵). During daytime, average fidelity drops by ≈ 18% while end-to-end EGR increases, attributed to solar background photons; the degradation can worsen for paths with multiple satellite-assisted links.
• Pareto Routing sits between the extremes. Over all end-user pairs, Max-Fidelity attains the highest average fidelity but the lowest EGR, FC-MaxEGR attains the highest EGR with lower fidelity, and Pareto Routing lies between them; Distance-Based routing achieves lower fidelity and EGR than Pareto Routing.
• Weights move the operating point. For one medium-distance pair in a single time slot, changing (ω_F, ω_R) from (0.9, 0.1) to (0.5, 0.5) raised the selected EGR from 4.64 × 10⁴ to 1.32 × 10⁵ while fidelity fell from 0.945 to 0.915.
• Highest aggregate application utility. Under a mixed workload of secret key rate (SKR), negativity (NEG), and distillable entanglement (DE) utilities, Pareto Routing achieves the highest aggregate utility; FC-MaxEGR is the closest baseline because it considers both metrics, but commits to a single operating point.
• Route stability varies sharply (Table I). Number of route changes for the 1132.63 km pair / 3178.55 km pair: Max-Fidelity 838 / 2172; FC-MaxEGR 6357 / 1228; Pareto 3805 / 1228; Distance-Based 0 / 1507.
• Long-distance behavior. For the 3178.55 km pair, all policies operate at lower fidelity, and Pareto Routing and FC-MaxEGR select similar paths under the 0.5 fidelity threshold, so their EGR and fidelity appear almost identical; Distance-Based shows larger variations in both.

Methodology in Plain English

The authors build a network model with two layers. The terrestrial layer has 1000 fiber end-nodes at top population centers plus 10 optical ground stations (1010 nodes total), connected by fiber edges capped at d_rep = 110 km so repeaters can be inserted; because the initial proximity graph had 94 disconnected components, they repeatedly joined the closest pair of components (single-linkage clustering), ending with 28,777 static terrestrial edges and a longest added edge of 379 km requiring 3 intermediate repeaters. The space layer uses 3,980 Starlink satellites (inclinations 43°, 53°, 70°, 97°) from public TLE data; a satellite is visible to a ground station only above 20° elevation. Time is divided into slots, and within each slot a greedy scheduler assigns satellites to ground-station pairs — one satellite per pair, one pair per satellite, prioritizing geographically separated pairs and, among candidate satellites, the one giving the largest EGR — creating transient "virtual" edges. Since a ground-station pair may simultaneously have a fiber edge and a virtual edge, the network is a time-varying multigraph.

Each edge carries a rate R_e and a Werner-approximated fidelity F_e. End-to-end EGR is the minimum edge rate along the path (the bottleneck), while end-to-end fidelity is determined by the product of edge Werner parameters, F_p = 3(∏W_e + 1)/4. Because maximizing fidelity is equivalent to minimizing the sum of -log W_e, the problem becomes one bottleneck objective plus one additive objective. The algorithm repeatedly finds the cheapest path in transformed fidelity cost, records its bottleneck rate, deletes all edges whose rate is no greater than that bottleneck, and repeats until the endpoints disconnect — yielding one representative per Pareto point.

For final path selection the authors consider three application utilities (secret key rate, negativity, distillable entanglement), and, when no utility is given, a weighted utopia-point method that normalizes EGR and fidelity across the frontier and picks the path closest to the ideal point. The simulator is written in Python 3 using PyEphem, Matplotlib, Networkx, NumPy, and global-land-mask, and runs 100 randomly chosen source–destination pairs over 24 hours at 10-second intervals (8640 time slots), split into short-range (≤ 1000 km, 30 pairs), medium-range (> 1000 km and ≤ 2000 km, 34 pairs), and long-range (> 2000 km, 36 pairs). Fiber attenuation is 0.2 dB/km, atmospheric thickness is 5 km, and dark-click probability is 3 × 10⁻³ by day (6:00 AM–6:00 PM) versus 3 × 10⁻⁶ by night (6:00 PM–6:00 AM). The switching threshold for the distance-based baseline is derived empirically from the fraction of routes using the satellite layer as a function of user separation.

Why This Matters

Research impact. The paper shows that a quantum routing problem that is generically hard (multi-objective shortest path) becomes exactly solvable because of the specific algebraic structure of quantum metrics — a bottleneck rate and a multiplicative fidelity. It also reframes hybrid network evaluation: instead of asking which single policy is best, it asks what set of operating points the network exposes, and quantifies that hybrid networks expose many more of them than fiber-only networks.

Real-world applications:

• Quantum key distribution — selecting the path maximizing secret key rate, computed from rate and Werner-state fidelity.
• Blind quantum computing — requires remote entanglement delivery to a server; fidelity-driven path choice matters.
• Very-long-baseline interferometry — favors higher EGR over maximal fidelity.
• Synchronized atomic clocks / high-precision quantum sensing — requires higher-fidelity entangled states rather than raw rate.

Industry relevance. Satellite operators and ground-station builders (the paper notes the high cost of optical ground stations limits deployment), telecom fiber providers, and network-controller vendors all face the practical question of how to schedule entanglement requests across mixed infrastructure. Because the Pareto frontier is computed once and utilities are evaluated afterwards, a controller can serve heterogeneous applications without rerunning routing — an operationally attractive property. The paper also quantifies route churn (Table I), which matters for control-plane stability.

Future Directions

• Handling the truncated long-distance regime. The reported Pareto-path counts for long-distance pairs are markedly lower than for medium-distance pairs; whether this reflects limited satellite visibility windows or limited path diversity is a natural follow-up question the paper's framing invites.
• Mitigating daytime degradation. Since daytime fidelity drops ≈ 18% and multi-satellite-link paths degrade further, scheduling or noise-aware virtual-edge selection to preserve fidelity during daylight is an open design problem.
• Richer physical models. The framework assumes deterministic entanglement swapping and perfect quantum memories with unlimited storage time; relaxing these would break the clean bottleneck/product structure and is not addressed.
• Utility and policy integration. Only three utility functions and a weighted utopia-point fallback are studied; how a real controller learns or is told each application's utility — and how Pareto selection interacts with the greedy satellite scheduler's resource constraints — remains open.

Target Audience

Graduate students and researchers in quantum networking and quantum communication who already know entanglement swapping and Werner states; network-optimization researchers interested in multi-objective and bicriterion shortest-path methods with unusual objective structure; and engineers or architects designing controllers for hybrid fiber–satellite quantum infrastructure who want a concrete, polynomial-time method and empirical baseline comparisons. Beginners will find the physical-layer and optimization prerequisites steep.

Authors’ abstract

Hybrid terrestrial-satellite quantum networks combine terrestrial fiber infrastructure with free-space links to enable long-distance entanglement distribution. Entanglement can be routed over different combinations of terrestrial and satellite links, resulting in paths with different entanglement generation rates (EGRs) and fidelities. Existing routing algorithms, however, typically reduce routing to a single-objective problem by optimizing either EGR or fidelity, or by optimizing one while constraining the other, and thus do not explicitly capture the trade-off between the two. In this paper, we present a bi-objective routing framework for hybrid quantum networks that jointly optimizes end-to-end EGR and fidelity. We formulate routing as a Pareto optimization problem and show that it possesses a special mathematical structure: the bottleneck nature of end-to-end EGR and the multiplicative nature of end-to-end fidelity allow the problem to be transformed into a MAXMIN-MINSUM bi-criterion path problem. This transformation enables the exact polynomial-time computation of a minimal complete Pareto set using Martins' bicriterion routing algorithm. Our results demonstrate that hybrid networks expose substantially richer Pareto frontiers than terrestrial-only networks and that the proposed framework outperforms representative single-objective routing policies by allowing applications to select paths based on their EGR and fidelity requirements.