Challenges in Applying Variational Quantum Algorithms to Dynamic Satellite Network Routing
Phuc Hao Do [email protected],, Tran Duc Le [email protected], · 2025
Read Challenges in Applying Variational Quantum Algorithms to Dynamic Satellite Network Routing by Phuc Hao Do [email protected],, Tran Duc Le [email protected], (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-04288.txt.
Introduction
Phuc Hao Do and Tran Duc Le stated sobering failures of near-term quantum methods at satellite routing in a 2025 paper. Satellite constellations need routes recomputed constantly as links shift, and change-based quantum methods are often pitched as future optimizers for exactly such problems. The authors tested two groups: static optimizers, the change-based eigensolver and the approximate tuning method, work routes offline. Quantum reinforcement learning agents deciding online, all in ideal noise-free mock run that favors the quantum side.
Even so, the static solvers could not crack a four-node shortest path problem that is trivial classically, drowning in a nasty tuning landscape. A basic policy-gradient agent learned nothing useful in a dynamic eight-node network, matching random actions. Barren plateaus and learning instability are named as culprits.
Catalog record
| CREATOR | Phuc Hao Do [email protected],, Tran Duc Le [email protected], |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-04288
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Challenges in Applying Variational Quantum Algorithms to Dynamic Satellite Network Routing Phuc Hao Do [email protected],, Tran Duc Le [email protected], Abstract Applying near-term variational quantum algorithms to the problem of dynamic satellite network routing represents a promising direction for quantum computing. In this work, we provide a critical evaluation of two major approaches: static quantum optimizers such as the Variational Quantum Eigensolver (VQE) and the Quantum Approximate Optimization Algorithm (QAOA) for offline route computation, and Quantum Reinforcement Learning (QRL) methods for online decision-making. Using ideal, noise-free simulations, we find that these algorithms face significant challenges. Specifically, static optimizers are unable to solve even a classically easy 4-node shortest path problem due to the complexity of the optimization landscape. Likewise, a basic QRL agent based on policy gradient methods fails to learn a useful routing strategy in a dynamic 8-node environment and performs no better than random actions. These negative findings highlight key obstacles that must be addressed before quantum algorithms can offer real advantages in communication networks. We discuss the underlying causes of these limitations, including barren plateaus and learning instability, and suggest future research directions to overcome them. Keywords: Variational Quantum Algorithms, Quantum Reinforcement Learning, Dynamic Network Routing, Satellite Networks, Near-Term Quantum Computing. 1 Introduction The advent of large-scale Low Earth Orbit (LEO) satellite constellations, spearheaded by initiatives such as SpaceX’s Starlink, Amazon’s Project Kuiper, and OneWeb, is poised to revolutionize global connectivity Saeed et al. 2020 . By deploying thousands of interconnected satellites, these networks promise to deliver high-speed, low-latency internet access to every corner of the globe, including remote and underserved regions Reddy et al. 2023 . However, the very characteristics that enable this new paradigm - namely, the massive scale and high orbital velocity of the satellites - introduce unprecedented challenges in network management Hu 2023 . The network topology is in a constant state of flux, with inter-satellite links (ISLs) being established and terminated on a timescale of seconds, creating a highly dynamic and complex operational environment Bhattacharjee et al. 2024 . At the heart of managing these constellations lies the network routing problem: determining the optimal path for data packets to travel from a source to a destination Zhang et al. 2025 ; Chen et al. 2021 . In this dynamic context, the routing problem is far more complex than in terrestrial networks. It must account for time-varying latencies, intermittent link availability, and vast state spaces. Formally, finding the optimal path in such a dynamic graph, especially when subject to constraints like ensuring a simple (loop-free) path, is an NP-hard combinatorial optimization problem Hartmanis 1982 . Classical routing protocols often rely on heuristics that may provide fast but suboptimal solutions, while exact algorithms are computationally intractable for real-time decision-making in networks of this scale. Quantum computing offers a fundamentally new paradigm for tackling such computationally hard problems Younis et al. 2024 . By leveraging quantum-mechanical principles like superposition and entanglement, quantum computers can, in principle, explore a vast solution space more efficiently than their classical counterparts Raisuddin and De 2024 . While fault-tolerant quantum computers are still a distant prospect, the current Noisy Intermediate-Scale Quantum (NISQ) era has seen the emergence of hybrid quantum-classical algorithms Preskill 2018 . These algorithms are specifically designed to run on near-term, noisy quantum processors. They utilize a classical computer to guide the quantum computation via a variational feedback loop, making them promising candidates for achieving a practical quantum advantage on optimization tasks. This paper investigates the potential and, critically, the practical challenges of applying two leading classes of hybrid algorithms to satellite network routing. The first class includes variational quantum optimizers, such as the Variational Quantum Eigensolver (VQE) Peruzzo et al. 2014 and the Quantum Approximate Optimization Algorithm (QAOA) Farhi et al. 2014 . These algorithms reframe an optimization task as a search for the ground state of a corresponding Ising Hamiltonian, making them conceptually well-suited for static, offline route planning. The second class is Quantum-enhanced Reinforcement Learning (QRL) Jerbi et al. 2021 , which equips a reinforcement learning agent with a Parameterized Quantum Circuit (PQC) as its policy-making core. This approach is naturally tailored for sequential decision-making in the dynamic environments that characterize satellite networks. The primary contribution of this work is to provide a realistic benchmark of these quantum approaches, focusing on the practical hurdles encountered during implementation. In a field often characterized by hype, this type of critical assessment is crucial for guiding research efforts toward genuinely promising avenues. To achieve this, we formally model the dynamic routing problem and decompose it into two distinct sub-problems: a static shortest path problem for offline planning and a dynamic routing decision problem for online adaptation. We then implement and apply VQE, QAOA, and a QRL agent to these respective problems, detailing the process of mapping them to appropriate quantum representations such as Ising Hamiltonians and a PQC-based policy. Through extensive classical simulation of quantum circuits, our detailed performance analysis, contrary to demonstrating a quantum advantage, reveals the significant difficulties faced by these algorithms. Our analysis highlights critical failure modes, including the convergence of static optimizers to invalid solutions and the failure of the QRL agent to learn an effective policy. By carefully dissecting these informative ”negative” results, we provide valuable insights into the underlying challenges of intractable optimization landscapes and learning instability, ultimately concluding with concrete future research directions required to overcome these identified obstacles. The remainder of this paper is structured as follows. Section 2 provides the necessary background on the satellite routing problem and the quantum algorithms under study. Section 3 details our formal problem definition and the mapping to quantum models. Section 4 describes the implementation of our algorithms and simulation environment. Section 5 outlines the experimental setup. The results of our comparative analysis are presented in Section 6 . Finally, in Section 7 and Section 8 , we discuss the implications of our findings and conclude with suggestions for future research. 2 Background and Preliminaries This section provides the foundational concepts necessary to understand our work. We begin by providing a more detailed description of the satellite network routing problem, then introduce the hybrid quantum-classical computing paradigm that underpins our chosen algorithms, and finally provide an overview of VQE, QAOA, and QRL. 2.1 The Satellite Network Routing Problem As introduced in Section 1 , routing in LEO satellite constellations is a challenging optimization task, fundamentally modeled as finding optimal paths on a dynamic graph G(t)=(V,E(t)) Zhang et al. 2023b ; Zhang et al. 2023a . While the primary objective is typically to minimize end-to-end latency, a real-world formulation must contend with a variety of operational constraints that increase its complexity. For instance, each communication link possesses a finite link capacity , meaning routing decisions must avoid creating congestion that would introduce unpredictable queuing delays Grislain et al. 2024 . Furthermore, the satellites themselves operate under strict resource limitations , including power and processing capabilities, which may constrain the number of active links or the volume of traffic a single node can handle Xia et al. 2024 . Critically, to prevent routing loops and the inefficient use of resources, the chosen path must often adhere to a path validity constraint, such as being a simple