A strategy for the analysis of active debris removal missions targeting multiple objects from a set of objects in near-circular orbit with similar inclination is presented. Algebraic techniques successfully reduce the orbital mechanics regarding specific inter-debris transfer and disposal methods to simple computations, which can be used as the coefficients of a quadratic unconstrained binary optimisation (QUBO) problem formulation which minimises the total propellant used in the mission whilst allowing for servicing time and meeting the mission deadline. The QUBO is validated by solving artificial small problems (from 2 to 11 debris) using classical computational methods and the weaknesses in using these methods are examined prior to solution using quantum annealing hardware. The quantum processing unit (QPU) and quantum-classical hybrid solvers provided by D-Wave are then used to solve the same small problems, with attention paid to evident strengths and weaknesses of each approach. Hybrid solvers are found to be significantly more effective at solving larger problems. Finally, the hybrid method is used to solve a large problem using a real dataset. From a set of 79 debris objects resulting from the destruction of the Kosmos-1408 satellite, an active debris removal mission starting on 30 September 2023 targeting 5 debris objects for disposal within a year with 20 days servicing time per object is successfully planned. This plan calculates the total propellant cost of transfer and disposal to be 0.87km/s and would be complete well within the deadline at 241 days from the start date. This problem uses 6,478 binary variables in total and is solved using around 25s of QPU access time.
A strategy for the analysis of active debris removal missions targeting multiple objects from a set of objects in near-circular orbit with similar inclination is presented. Algebraic techniques successfully reduce the orbital mechanics regarding specific inter-debris transfer and disposal methods to simple computations, which can be used as the coefficients of a quadratic unconstrained binary optimisation (QUBO) problem formulation which minimises the total propellant used in the mission whilst allowing for servicing time and meeting the mission deadline. The QUBO is validated by solving artificial small problems (from 2 to 11 debris) using classical computational methods and the weaknesses in using these methods are examined prior to solution using quantum annealing hardware. The quantum processing unit (QPU) and quantum-classical hybrid solvers provided by D-Wave are then used to solve the same small problems, with attention paid to evident strengths and weaknesses of each approach. Hybrid solvers are found to be significantly more effective at solving larger problems. Finally, the hybrid method is used to solve a large problem using a real dataset. From a set of 79 debris objects resulting from the destruction of the Kosmos-1408 satellite, an active debris removal mission starting on 30 September 2023 targeting 5 debris objects for disposal within a year with 20 days servicing time per object is successfully planned. This plan calculates the total propellant cost of transfer and disposal to be 0.87km/s and would be complete well within the deadline at 241 days from the start date. This problem uses 6,478 binary variables in total and is solved using around 25s of QPU access time.
Abstract The rapid accumulation of space debris in Low Earth Orbit (LEO) poses a significant challenge to the sustainability of space operations. While preventive measures limit new debris generation, they are insufficient to mitigate the growing population of defunct satellites, rocket stages, and collision fragments. Active Debris Removal (ADR) has emerged as a viable solution, which requires solving NP-hard combinatorial optimization problemsimilar to the Traveling Salesman Problem (TSP) to maximize mission efficiency by minimizing fuel and mission duration. This work explores the application of Quantum Annealing (QA) and Hybrid Quantum Annealing (HQA) for optimizing multi-target ADR missions. Specifically, it introduces a Quadratic Unconstrained Binary Optimization (QUBO) model for ADR, exploiting quantum computing to enhance solution efficiency. A novel quadratization method is developed to reduce computational complexity, enabling large-scale mission planning. Additionally, a novel constraint-handling strategy is proposed, integrating mission constraints into post-processing to enhance quantum solver efficiency. The proposed approach is validated using real-world satellite debris datasets and benchmarked against classical metaheuristic optimizers, including Simulated Annealing (SA), Tabu Search (TS), and Genetic Algorithms (GA). The obtained results demonstrate the advantages of quantum optimization for ADR mission planning, providing a scalable and computationally efficient solution.
The continued growth of orbital debris threatens the safety and sustainability of near-Earth space, making Active Debris Removal (ADR) an important mitigation strategy. Selecting k targets from N candidates yields a combinatorial search space of size (kN), making joint target selection and mission sequencing computationally demanding. We present a topology-aware quantum-classical framework integrating orbital mechanics, weighted orbital-transfer graphs, Gaussian Boson Sampling (GBS), and multi-objective evolutionary optimization. Seven target-prioritization strategies represent physical consequence, orbital persistence, conjunction risk, network centrality, community structure, inferred source families, and random selection. GBS generates candidate target subsets from the weighted graph, which are then evaluated using PyGMO-based evolutionary optimization to identify servicing sequences that jointly minimize total velocity increment (Δv) and mission duration, accounting for modeled timing, propulsion, and mass feasibility. We evaluate the framework across three benchmark environments, SOCRATES Minefield, Collision Cloud, and Random, with candidate-pool sizes N∈{15,18,22,25} and target cardinalities k∈{3,5}. The experiments characterize how benchmark topology, prioritization strategy, and problem scale relate to sampling behavior and downstream mission performance. By separating candidate-subset generation from detailed trajectory optimization, the framework offers a topology-aware approach to focusing computational effort on a limited set of candidate ADR missions.
Mission planning often involves optimising the use of ISR (Intelligence, Surveillance and Reconnaissance) assets in order to achieve a set of mission objectives within allowed parameters subject to constraints. The missions of interest here, involve routing multiple UAVs visiting multiple targets, utilising sensors to capture data relating to each target. Finding such solutions is often an NP-Hard problem and cannot be solved efficiently on classical computers. Furthermore, during the mission new constraints and objectives may arise, requiring a new solution to be computed within a short time period. To achieve this we investigate near term quantum algorithms that have the potential to offer speed-ups against current classical methods. We demonstrate how a large family of these problems can be formulated as a Mixed Integer Linear Program (MILP) and then converted to a Quadratic Unconstrained Binary Optimisation (QUBO). The formulation provided is versatile and can be adapted for many different constraints with clear qubit scaling provided. We discuss the results of solving the QUBO formulation using commercial quantum annealers and compare the solutions to current edge classical solvers. We also analyse the results from solving the QUBO using Quantum Approximate Optimisation Algorithms (QAOA) and discuss their results. Finally, we also provide efficient methods to encode to the problem into the Variational Quantum Eigensolver (VQE) formalism, where we have tailored the ansatz to the problem making efficient use of the qubits available.
Quantum computers relying on cold atoms are being built and promise a high flexibility in the way information in encoded into the physical system. In particular, the analog mode is spiking interest in the field of optimization as a classically intractable number of configurations can be tackled. In this work, we investigate a problem that requires every-day scheduling of critical tasks involving a large number of actors. Namely, fixing the planning for a Earth Observation satellite fleet composed of several of units exposed to a high density of targets to be scanned. We explore numerical schemes that convert the formulated problem into a cold-atoms friendly setup. We begin by a naive formulation of the Satellite Mission Planning problem without taking account for the agility of the satellites. We then extend the problem to take it into account based on the literature. By formulating the planning problem as a Maximum Independent Set problem, we are able to solve the problem with a QPU based on Rydberg atoms. We explore two ways of solving the MIS problem on the QPU, one relying on the graphs and on the Quadratic Unconstrained Binary Optimization Framework (QUBO). We show that the QUBO methodology is the most relevant and explore it more deeply with numerical experiments. We conclude on the potential utility of using a QPU to solve the Satellite Mission Planning problem in an operational context.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum. We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu’s Digital Annealer (DA) and D-Wave’s Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum.We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.