CS Paper Radar

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

Yashpreet Khambay, Nitish K. Panigrahy

cs.NI quant-phcs.PF ·submitted 2026-09-17 01:42 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.NI quant-ph ·2026-09-14 ·Leonardo Bacciottini, Subhransu Maji, Don Towsley, Gayane Vardoyan
theory similarity 0.74
Abstract · 13 pages

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.

0.23

Multi-Pair Fidelity-Aware Rate Allocation in a Quantum Network: Approximation Schemes

cs.NI ·2026-08-11 ·Zunzheng Zhang, Xuanli Lin, Zhaofeng Zhang, Nageswara S. V. Rao, Guoliang Xue
theory similarity 0.70
Abstract

Entanglement distribution in quantum networks must jointly account for limited link capacities, probabilistic entanglement swapping, and heterogeneous link fidelities. In this paper, we study multi-pair fidelity-aware rate allocation in quantum networks. We formulate three rate-allocation problems: rate sum, rate sum subject to minimum-rate constraints, and max-min fairness. Prior work has studied a special case of the rate sum problem, where all links have identical fidelity. This special case admits a polynomial-time algorithm. We prove that all three problems are NP-hard. We then study optimization versions of these problems which maximize the minimum end-to-end fidelity subject to throughput or fairness requirements. We present fully polynomial-time approximation schemes (FPTAS) for solving these optimization problems. Experiments on randomly generated networks demonstrate the computational effectiveness of the proposed schemes.

0.04

Starlight: Whittle-Driven Fidelity Rescue for Satellite-Terrestrial Quantum Networks

cs.NI ·2026-11-13 ·Yaliang Shi, Zhiwei Zhao, Bangguo Yuan
similarity 0.69
Abstract · 10 pages, 7 figures, 2 tables

A planetary-scale quantum internet is constrained by exponential attenuation in terrestrial fibers. Low-Earth-orbit (LEO) satellites provide a low-loss vacuum backbone, but limited satellite resources must be allocated among competing connections under continuously evolving and heterogeneous physical conditions. Existing satellite scheduling remains largely provisioning-oriented, optimizing satellite-resource assignment for aggregate entanglement delivery. Recent age-based approaches instead incorporate chronological freshness into entanglement scheduling. Neither line of work directly identifies the connections most urgently requiring satellite assistance as their physical states evolve. We propose Starlight, a demand-driven satellite-terrestrial entanglement routing architecture that targets degrading connections before their terrestrial entanglement becomes unusable. Starlight introduces Effective Age of State (EAoS), a physics-aware metric that maps heterogeneous decoherence and swapping-induced fidelity penalties onto a unified additive coordinate. Representing each connection by evolving EAoS, we formulate rescue scheduling as a Restless Multi-Armed Bandit (RMAB) problem and derive a closed-form Whittle-style index approximation for top-K selection. Starlight further employs a two-timescale control plane and an asynchronous dispatch-and-mask pipeline to suppress redundant in-flight allocations. Simulations show that Starlight achieves up to 84.5% average satisfaction under constrained rescue capacity and sub-0.5-ms orchestration at 1,000 connections, while remaining robust to heterogeneous memory decay and stochastic atmospheric degradation.

0.17

QUASAR: Quantum Satellite Architecture and Routing Simulator

cs.NI ·2026-09-04 ·Yaliang Shi, Zi Wang, Bangguo Yuan, Gaojie Wu, Zhiwei Zhao
similarity 0.67
Abstract

The deployment of Low Earth Orbit (LEO) satellite constellations is an important step toward global-scale quantum networking. However, evaluating satellite quantum network protocols under spatiotemporal orbital dynamics and quantum physical constraints remains computationally expensive and challenging. In this paper, we propose QUASAR, a lightweight simulator for evaluating entanglement distribution in satellite-based quantum networks. QUASAR provides a decoupled architecture that integrates dynamic orbital topologies, time-varying optical transmittance, and quantum memory decoherence into network- layer attributes. To demonstrate its capabilities, we abstract and implement two representative hardware architectures: Simultaneous Downlink and On-Orbit Stitching. We further introduce an Entanglement Distribution Rate (EDR)-Aware Spatiotemporal Routing (EASR) heuristic as a reference workload. Our case study examines how QUASAR supports different satellite architectures, routing workloads, realistic orbital traces, concurrent requests, and scalable event-driven execution. With over 85% lower network-layer update latency than continuous polling, QUASAR provides a practical and extensible framework for future satellite quantum network protocol evaluation.

0.35

Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes

cs.ET quant-phmath.COmath.OC ·2026-10-30 ·Emanuele Casciaro, Mario De Simone, Stefano Martina, Fabio Mascherpa, Alfonso Amendola +1 more
similarity 0.67
Abstract · 12 pages, 6 figures, 1 table

With the expansion of complex transport infrastructure, new paths for linking different destinations have emerged, allowing the definition of multiple routes. The introduction of new roads may also lead to disruptions in traffic flow. This problem can be generalized into a special case of VRP, which aims to find the optimal route for a fleet of vehicles within a network of destinations. Finding solutions to this problem requires an exponential number of operations, hindering the ability of exact solvers to deal with large instances, which must therefore be tackled using heuristics, often leading to suboptimal results. Quantum-based algorithms may allow us to find exact solutions in polynomial time with high probability, offering a potential future alternative to classical solvers and in this work, we focus on the QAOA. Our novel contributions are a parameter-initialization strategy that improves the convergence probability and the integration of the subtour constraints directly into the optimization without using additional qubits by employing an approximation of exponential equality constraints. We believe that our results pave the way for effectively solving instances of VRP using quantum-based solutions, leveraging the space-efficient problem encoding and our initialization strategy, which limits the effect of barren-plateau under random parameter initialization.

0.08

Quantum Approximate Multi-Objective Optimization in Routing Problems

cs.ET quant-ph ·2026-09-15 ·Eduardo Willwock Lussi, Alisson dos Passos Fumaco, Marcos Vinicius Reballo, José Carlos Libois Neto, Fernando Augusto Caletti de Barros +1 more
similarity 0.66
Abstract

Multi-objective optimization (MOO) problems are common in logistics, where routing decisions must balance conflicting objectives such as travel distance, delivery time, and operational risk. A recently proposed Quantum Approximate Optimization Algorithm (QAOA) parameter-transfer strategy solves multi-objective MAX-CUT problems by reusing parameters trained on smaller instances, avoiding costly reoptimization for each scalarized problem. However, its effectiveness has only been demonstrated on proof-of-concept instances tailored to quantum hardware connectivity. In this work, we evaluate the applicability of this strategy to realistic routing problems. We formulate the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) as Quadratic Unconstrained Binary Optimization (QUBO) models, reduce them to MAX-CUT, and assess the parameter-transfer framework under conditions matching the original study. Validation is performed through classical simulations and experiments on IBM quantum hardware. The resulting Pareto fronts are compared with those obtained using an adapted classical ε-constraint method, using hypervolume as the primary quality metric. Results indicate that parameter transfer remains effective, frequently achieving higher hypervolume and often finding competitive solutions earlier. However, performance depends on problem structure. The approach is consistently effective for TSP instances but less stable for the more constrained VRP, suggesting that QAOA parameter transferability decreases as the optimization landscape becomes more complex. These results provide the first comprehensive evaluation of QAOA parameter transfer on realistic multi-objective routing problems and demonstrate its potential beyond proof-of-concept MAX-CUT benchmarks.

0.23

A hybrid quantum-classical neural network for learning to route

cs.LG quant-ph ·2026-08-31 ·Marcus Rolf Peter Ritt, Alexsandro Santos da Rosa Júnior, Marcos Vinicius Reballo, Cesar Augusto do Amaral, Fernando Augusto Caletti de Barros
similarity 0.64
Abstract · 5 pages. Submitted to the Congresso Brasileiro de Ciências e Tecnologias Quânticas (CBCTQ 2026)

This work studies hybrid quantum-classical neural networks for learning routing heuristics. Specifically, this paper asks whether small quantum neural networks can replace parameter-heavy modules inside a competitive attention-based routing model while maintaining solution quality. For the capacitated vehicle routing problem, encoder feed-forward replacement emerges as the most promising design: it reduces the number of model parameters by 56.6% while keeping the hybrid model close to the classical neural baseline at small and medium instance sizes, although the gap grows for larger instances. This work also compares to classical routing algorithms, which remain highly competitive and often superior on the fixed Euclidean test sets. Our results therefore do not indicate quantum advantage or solver dominance, but identify encoder feed-forward replacement as a viable hybrid-module compression strategy for neural combinatorial optimization.

0.41

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

cs.NI quant-ph ·2026-09-29 ·Aikaterini Mandilara, Antonia Tsili, Dimitris Syvridis, Konstantinos Christodoulopoulos
theory similarity 0.63
Abstract · 21 pages, 9 figures

Entanglement routing establishes entangled pairs between distant nodes of a quantum network by purifying and swapping pairs generated on elementary links. Existing methods typically restrict the decision space along two axes: the operation order, often fixed to purify-then-swap (PtS), and the purification schedule of each link, often restricted to pumping. Focusing on linear repeater chains with finite link capacities, we relax both restrictions and study the maximization of the expected end-to-end throughput subject to a fidelity threshold under two quantum-noise models. We develop a unified capacity-aware optimization framework comprising an exact mixed-integer linear program (MILP) under PtS, instantiated with either pumping or general tree purification schedules, and an exact dynamic program (DP) over arbitrary operation orders. Under symmetric Pauli noise, we prove that pumping converges to a fidelity strictly below unity, imposing a capacity-independent feasibility bound and a maximum chain length on every pumping-based PtS method, whereas general tree schedules yield a capacity-dependent bound. We further prove that post-swap purification never increases the throughput, so a free operation order can only increase feasibility. Numerical evaluations confirm the bounds: tree schedules serve over 90\% of the requests that pumping cannot at moderate fidelity thresholds; within the pumping class, a free operation order recovers much of this advantage; but once links use tree schedules, the tree-based MILP and the order-exact DP serve identical request sets throughout. Operation order and purification schedule are thus substitutes, with the purification schedule the dominant factor governing feasibility under symmetric Pauli noise.

0.24