CS Paper Radar

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

Leonardo Bacciottini, Subhransu Maji, Don Towsley, Gayane Vardoyan

cs.NI quant-ph ·submitted 2026-09-14 18:30 UTC · v1
theory

Abstract

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.

Comment
13 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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.76
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

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.74
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

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

cs.NI quant-phcs.PF ·2026-09-17 ·Yashpreet Khambay, Nitish K. Panigrahy
similarity 0.74
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.

0.06

Priority-Aware Routing for Quantum Networks:Integrating Coherence-Time Constraints into Scheduling

cs.NI quant-ph ·2026-09-29 ·Sadhgun Ram Dasi, Aswath Babu H
similarity 0.68
Abstract · 10 pages and 3 figures

Quantum networks face a fundamental challenge absent in classical networks; finite memory coherence times mean that queuing delay directly degrades information quality, causing decoherence that has no classical analog. Existing routing protocols optimize for hop count or channel fidelity while treating scheduling delays as a secondary concern, leaving fidelity vulnerable to congestion-induced decoherence. We present a coherence-aware routing protocol that integrates decoherence constraints into path selection via a priority-modulated aging model derived analytically from Weighted Fair Queueing theory, where high-priority traffic receives compressed effective queue delay. We build a custom discrete-event simulator verified against NetSquid (across 104 states), and evaluate across two structurally diverse topology classes under identical physical parameters, isolating topology structure as the sole independent variable. In all experiments, our protocol is benchmarked against loss-only Dijkstra routing and FIFO scheduling as baselines. On topologies, P2 traffic achieves 96.08% fidelity under a 9x load increase with only 0.04 percentage point degradation, versus a 13.51 percentage point collapse for the loss-only baseline; P2 tail latency holds stable at 0.055 ms while Dijkstra degrades 5.5x. On Barabasi-Albert scale-free topologies, our protocol delivers a +4.12 percentage point fidelity advantage with 97.8% higher aggregate throughput at operational loads over the baseline, with a clearly characterized hub-saturation boundary at 160k QPS. FIFO scheduling provides negligible priority differentiation on both topology classes, providing strong evidence that coherence-aware routing-not scheduling alone is responsible for the observed QoS gains.

0.23

Distributing Quantum Circuits Using Pre-Distributed Entanglement Pairs over Quantum Networks

cs.ET quant-ph ·2026-10-19 ·Yukun Yang, Ranjani G. Sundaram, Himanshu Gupta
publishedbenchmark similarity 0.67
Abstract · 9 pages, 4 figures. Full author version revised after acceptance; includes the cost-aware entanglement consumption section omitted from the …

Distributing quantum circuits across a network of quantum devices is a recent approach to improve the scalability of quantum computation. Entangled pairs of qubits distributed across network nodes are used as a communication resource for executing inter-node (remote) gates. However, establishing these entanglement pairs incurs significant latency, and doing so during the circuit's execution may lead to the decoherence of logical qubits. Instead, it may be beneficial to distribute certain entanglement pairs before the circuit is executed. Thus, we consider the problem of distributing a quantum circuit across a quantum network containing some pre-distributed entanglement pairs and seek to minimize the execution time of the circuit. We address this problem in three steps. First, given the quantum network and (optionally) a probability distribution over training circuits, we determine a set of pre-distributed entanglement pairs under a specified budget. Second, we compute a qubit-to-memory allocation that minimizes the expected execution time given these pre-distributed resources. Finally, we identify any additional entanglement pairs required during execution, generate them concurrently, and execute the circuit gates. We evaluate our methods on a broad range of benchmark circuits.

0.46

WLPA: A Network Management Framework for Allocating Scarce Quantum-Safe Link Postures under Weakest-Link Exposure

cs.CR quant-ph ·2026-10-04 ·Bhanwar Gupta, Sanjeev Rana
benchmark similarity 0.66
Abstract · Network resource management; Quantum-safe network design; Post-quantum migration; Cloud and cluster network operations; Quantum key distribu…

Network operators migrating distributed systems to post-quantum and quantum-safe cryptography face a resource-management problem: quantum key distribution (QKD) gives the strongest guarantee available but is hardware-scarce and costly, so only a fraction of a deployment's links can receive it. Default practice -- ranking links by traffic or centrality and upgrading the top scorers -- optimizes each link in isolation, while a distributed job's real security is set by whichever active link ends up weakest. We present WLPA (Weakest-Link Posture Assignment), an implementation-ready decision framework and algorithm for allocating scarce quantum-safe postures under hardware, latency, and compliance constraints. WLPA computes the optimal weakest-link posture in closed form and returns an assignment in O(|E| log |E|) time -- 125 ms for a 20,000-link network on a laptop -- with a breach-aware refinement matching an exact integer program under common conditions. Our central contribution is a dichotomy telling operators exactly when existing per-link heuristics already match this optimum and when they systematically fail: under constant upgrade cost and uniform traffic-driven risk the two coincide exactly; once costs vary or an adversary concentrates on weak targets, heuristics leave the weakest link unprotected, unboundedly. We validate WLPA across 19 experiments: four microservice topologies, a real enterprise network (SNAP email-Eu-core), a post-quantum latency benchmark, a Qiskit BB84 simulation and a real-hardware BB84 run on IBM's ibm_marrakesh processor, checks against real production traffic traces, a CVE-calibrated correlated-compromise study, Bayesian uncertainty quantification, and seven baseline methods. A concrete-security reduction grounds the framework as theoretical foundation, not primary contribution.

0.27

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

Spatio-temporal Path Optimization for Stabilizer-Code-Protected Quantum Networks

cs.NI ·2026-08-24 ·Yuanbo Zhang, Qianfan Wang, Yangming Zhao, Lin Chen, Deke Guo
similarity 0.66
Abstract · ICNP 2026 extended version

Quantum Error Correction~(QEC)-protected direct transmission is a fundamental approach to preserve fragile quantum states while they are physically forwarded across noisy quantum networks. When a logical qubit traverses multiple hops, selected QEC-capable nodes may recover the encoded state before it continues along the route. The feasibility and cost of the final transmission strategy therefore depend on how we jointly choose the path, the recovery locations, and the protection schemes. In this paper, we formulate and analyze a cross-layer spatio-temporal path optimization problem for block-style stabilizer-code-protected direct transmission. Our main results include fixed-scheme and flexible-scheme single-flow routing algorithms, as well as a multi-flow routing algorithm. The framework developed in this paper can serve as an algorithmic building block for QEC-aware routing under logical-error and logical-lifetime constraints. Simulations show that it reduces single-flow average routing cost by approximately 25--30\% over Decode-Always and lowers multi-flow throughput-normalized congestion by approximately 28--31\% over Greedy-Assignment.

0.17