Quantum Intelligence-Driven Dynamic Clustering for 6G Mega-LEO Satellite Constellation Networks

Abstract

Mega low Earth orbit (LEO) satellite constellations are a key infrastructure for 6G global connectivity, but their high node density, fast orbital motion, and continuously changing inter-satellite topology make routing difficult. Clustering is widely used to reduce routing complexity by partitioning a constellation into routing domains. This paper evaluates, side by side, two quantum-ready clustering approaches for mega LEO constellations. The first is qc-kmeans, a hybrid quantum–classical compressive K-means algorithm that selects cluster centroids by solving small quadratic unconstrained binary optimization (QUBO) problems with the quantum approximate optimization algorithm (QAOA). The second, RS-QUBO, partitions the inter-satellite link (ISL) graph directly with a routing- and stability-aware QUBO that rewards compact, balanced routing domains and penalizes changes between consecutive snapshots. Both are compared with classical baselines under identical inputs, with every trial recorded. For qc-kmeans, selecting the best of repeated trials suggests better cluster quality than K-means, but over all trials the two are practically identical on a 10,687-satellite Starlink snapshot and on a synthetic benchmark; an ablation shows that the outcome is determined by the classical K-means seeding and refinement, while QAOA accounts for most of the runtime. For RS-QUBO, on a real, irregular 1454-satellite Starlink sub-network with time-varying links and 3% random link failures, it is the only method of the main comparison that keeps all routes inside their routing domains at every tested number of domains (0% routing failures, compared with 39–71% for K-means, 16–44% for a grid tiling, and 2–22% for recomputed METIS), with a delay stretch of 1.08–1.18 over the routed pairs and 4–11% of satellites changing domain between snapshots. A component ablation attributes the absence of failures to adapting the partition to the current links and repairing disconnected domains, which also removes the failures of recomputed METIS; the compactness objective lowers the delay stretch relative to cut-based partitioning in the recomputed pipelines at 8 and 32 domains but not at 16. Domain changes are costly for routing: under a link-state update model, RS-QUBO needs 0.6–1.2 times the update load of flat routing, mostly to announce satellites that change domain, whereas an incremental refinement of a static METIS partition is also free of routing failures and needs 0.3–0.4 times the flat load. QAOA solves 6–12-satellite instances of this QUBO better than random sampling in ideal simulation, but the benefit becomes marginal under an ibm_torino noise model, and the compiled circuits require up to 960 two-qubit gates. We conclude that, in the evaluated conditions, the benefit of quantum-ready clustering for satellite routing comes from the problem formulation and the classical pipeline around it, solved classically, and that domain stability matters as much for routing as domain quality; QAOA is demonstrated at small scale on current hardware and noise models.