Henry and Colleagues Models Cold-Atom Scheme for Earth Observation Satellite Fleet Planning

A new application of quantum computing to Earth Observation satellite fleet scheduling is demonstrated by Michel Nowak of the Thales Research and Technology and colleagues from Thales Alenia Space and Pasqal. The challenges of planning scan across numerous targets are converted into a format suitable for solution using a Rydberg atom-based quantum processor. By framing the problem as a Maximum Independent Set problem and employing a Quadratic Unconstrained Binary Optimisation framework, the team show the potential for quantum processing units to offer a strong solution for operational satellite mission planning. The work highlights a promising avenue for using emerging quantum technologies to address real-world logistical challenges.

Quantum computation optimises satellite observation scheduling for enhanced target coverage

Space and Pasqal have, for the first time, solved a realistic Satellite Mission Planning problem using a quantum processing unit. This achieved a completion rate increase of over 20% compared to previously intractable scenarios. Previously, optimising scans for satellite constellations with hundreds of targets proved impossible with conventional methods, due to the exponential growth of possible combinations. The core difficulty lies in the combinatorial nature of the problem; each satellite has multiple potential observation windows, and each target requires observation within specific timeframes, leading to a vast search space for the optimal schedule. The team successfully formulated the scheduling challenge as a Maximum Independent Set problem, enabling implementation on a quantum computer based on Rydberg atoms, utilising the interactions of highly excited atoms to perform calculations.

The Maximum Independent Set problem, in this context, involves identifying the largest possible set of observation requests that can be fulfilled without any conflicts, that is, without two requests requiring the same satellite resource at the same time. This abstract mathematical formulation allows the problem to be mapped onto the qubits of the quantum processor. The Quadratic Unconstrained Binary Optimisation (QUBO) framework then translates the mathematical constraints into a form suitable for the Rydberg atom-based quantum computer. Rydberg atoms are particularly well-suited for this task because of their strong, controllable interactions when excited to high principal quantum numbers. These interactions can be programmed to represent the relationships between different observation requests, effectively encoding the problem’s constraints within the quantum system. An open-source software package has been released, enabling independent verification of their findings and further development. The total number of completed observation requests served as the primary metric to assess performance, alongside considerations for power, memory constraints, and target priority. In scenarios where classical optimisation methods failed, a 20% increase in completed observation requests was achieved, extending to simulations involving constellations ranging from a single satellite up to several hundred units, demonstrating scalability beyond traditional approaches.

The significance of this 20% improvement should be considered within the context of existing optimisation techniques. While sophisticated metaheuristics, such as genetic algorithms and simulated annealing, are routinely employed in satellite scheduling, they often become trapped in local optima, failing to find the globally optimal solution. The quantum approach, leveraging the principles of superposition and entanglement, offers a potential pathway to escape these local optima and explore a wider range of possible solutions. Furthermore, the ability to scale the simulations to several hundred satellite units is crucial, as modern Earth observation constellations are rapidly increasing in size. This scalability demonstrates the potential for the quantum approach to address the growing complexity of future satellite missions. Despite this, the current Rydberg atom-based quantum processing unit is limited by qubit count and speed, hindering its ability to decisively outperform established classical algorithms. Existing work on agile satellite scheduling, including sophisticated metaheuristics and adaptive algorithms detailed by Habet and Vasquez, Cordeau and Laporte, and others, provides a strong baseline for comparison. Further work will focus on improving qubit connectivity and coherence times to unlock the full potential of this quantum approach.

Quantum approaches to satellite scheduling pave the way for future optimisation

Practical application of quantum computation to logistical challenges is beginning to be demonstrated, with effective satellite mission planning as a prime example. This work establishes a vital pathway for future optimisation techniques, successfully translating a complex, real-world problem, planning observations for a fleet of Earth-observing satellites, into a format suitable for a new type of quantum computer. Rydberg atoms, which hold promise due to their flexibility in encoding information, underpin this new computational approach. The long-term implications extend beyond mere scheduling improvements; a more efficient allocation of satellite resources can lead to more timely and accurate Earth observation data, benefiting a wide range of applications, including climate monitoring, disaster response, and urban planning.

A method for translating complex satellite observation schedules into a format suitable for quantum computers has been demonstrated, and cold atom architectures can support hundreds to thousands of atoms. By framing the task as a Maximum Independent Set problem, the team successfully utilised a Quantum Processing Unit (QPU) built with Rydberg atoms. These atoms, excited to a high energy level, allow for strong interactions and facilitate solution-finding. The interactions are mediated by the dipole-dipole interaction between the Rydberg states, allowing for the creation of complex quantum circuits. The successful demonstration of this technique opens new avenues for optimising complex logistical problems using quantum computation, potentially revolutionising satellite operations and Earth observation capabilities. The current generation of Rydberg atom QPUs typically employs a two-dimensional array of atoms, with each atom representing a qubit. Control over these qubits is achieved using precisely shaped laser pulses. However, limitations in laser addressing and qubit connectivity remain significant challenges. Future research will focus on developing more sophisticated control schemes and improving the physical layout of the qubits to enhance performance. Furthermore, exploring alternative quantum computing architectures, such as trapped ions or superconducting qubits, may offer complementary advantages for satellite scheduling applications.

The ability to handle the 20% increase in completed observation requests, even with the current limitations of the hardware, suggests that future generations of quantum computers, with increased qubit counts and improved coherence times, could deliver substantial performance gains. This could lead to a paradigm shift in satellite mission planning, enabling more responsive and efficient Earth observation systems. The open-source nature of the software package released by the team is also crucial, fostering collaboration and accelerating the development of quantum algorithms for satellite scheduling and other logistical challenges. This work represents a significant step towards realising the potential of quantum computation to address real-world problems and unlock new capabilities in the field of Earth observation.

Researchers successfully demonstrated a solution to a complex satellite mission planning problem using a quantum processing unit based on Rydberg atoms. This approach converts the scheduling of Earth observation satellites and their targets into a format suitable for quantum computation, achieving improvements in handling observation requests. The team formulated the problem as a Maximum Independent Set problem and employed a Quadratic Unconstrained Binary Optimisation framework to solve it on the QPU. The authors intend to continue developing more sophisticated control schemes and improving qubit layout to further enhance performance.