⚛️ quantum physics

Satellite Mission Planning with Rydberg Atoms

This paper investigates the application of Rydberg atom-based quantum processors to solve the Earth Observation satellite mission planning problem by formulating it as a Maximum Independent Set problem, demonstrating through numerical experiments that a QUBO-based approach is the most effective method for optimizing scheduling in an operational context.

Original authors: Michel Nowak, Benjamin Marchand, Yassine Naghmouchi, Serge Rainjonneau, Wesley Coelho, Louis Vignoli, Louis-Paul Henry

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Michel Nowak, Benjamin Marchand, Yassine Naghmouchi, Serge Rainjonneau, Wesley Coelho, Louis Vignoli, Louis-Paul Henry

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the director of a massive, high-stakes movie production. You have a fleet of camera crews (satellites) zooming around the Earth, and you have hundreds of requests from clients who want to film specific cities or events. Your job is to create a shooting schedule that gets the most important scenes filmed without any crew crashing into each other, running out of battery, or forgetting to download their footage.

This is the real-world problem tackled in the paper: Satellite Mission Planning.

Here is how the authors approached solving this puzzle using a new kind of computer, explained simply:

1. The Problem: A Scheduling Nightmare

Every day, a scheduler has to decide which satellite films which city. It's not just about picking the best shots; there are strict rules:

Battery Life: The satellites need sunlight to recharge.
Memory: They can only hold so much video before they need to download it to Earth.
Turning Speed: Satellites can't spin instantly; they need time to turn their "head" to face a new target.
Clouds: If it's cloudy, the shot is useless.
Priority: Some requests are more critical than others.

If you have a few satellites and a few requests, a human or a regular computer can figure this out. But if you have hundreds of satellites and thousands of requests, the number of possible schedules becomes so huge that even the world's fastest supercomputers get stuck trying to find the best one.

2. The Solution: Turning the Problem into a "Party Game"

The authors decided to translate this complex scheduling problem into a game called the Maximum Independent Set (MIS).

Imagine a room full of people (nodes). Some people are friends, but some are enemies (edges).

The Goal: You want to invite as many people to a party as possible.
The Rule: No two enemies can be at the party at the same time.

In the satellite context:

Each "person" is a specific time slot where a satellite could film a specific city.
An "enemy" relationship exists if two slots conflict (e.g., the same satellite can't be in two places at once, or it can't turn fast enough between two cities).
The Solution: The "Maximum Independent Set" is the largest group of time slots you can pick where no two slots conflict. This gives you the maximum number of successful observations.

3. The New Tool: Rydberg Atom Computers

Instead of using a standard laptop to solve this "party game," the authors used a Quantum Processing Unit (QPU) based on Rydberg atoms.

Think of a Rydberg atom computer not as a calculator, but as a physics playground:

The Atoms: Imagine tiny, super-charged atoms acting like the people at the party.
The Rules: The scientists arrange these atoms in a specific pattern. If two atoms are too close to each other, they repel (like enemies). This is called the "Rydberg blockade."
The Magic: When the computer runs, the atoms naturally settle into a state where the maximum number of them are "excited" (at the party) without any two enemies being too close. The physics of the atoms does the math for you instantly, finding the best arrangement naturally.

4. What They Actually Did

The team didn't just talk about this; they built a software toolkit (a Python package) to test it.

The Setup: They simulated a fleet of 3 satellites trying to film up to 2,000 cities in a single day.
The Method: They converted the satellite schedule into a graph (the party guest list) and tried to solve it using two methods:
1. Classical: Using standard computer algorithms (like a very smart human planner).
2. Quantum: Using the Rydberg atom computer (specifically a QUBO method, which is a way of writing the problem so the atoms understand it).

5. The Results: A Glimpse of the Future

Here is what they found, sticking strictly to their data:

Quality: The quantum computer found schedules that were just as good as the classical computer. It successfully maximized the number of filmed cities.
Speed (The Catch): Currently, the quantum computer was slower than the classical one.
- Why? The quantum machine they used was small (only about 100 atoms) and had to wait in a queue to be used. It also took time to break the big problem into smaller chunks that the machine could handle.
The Potential: The authors argue that the way the quantum computer solves the problem is fundamentally different. While the classical computer's time to solve the problem grows very fast as you add more cities, the quantum computer's time grows much more slowly.
The Outlook: They predict that as quantum machines get bigger and faster (specifically, if they can take measurements 10 times faster per shot), they will eventually beat classical computers at this specific task.

Summary

The paper is a "proof of concept." It shows that you can translate a difficult satellite scheduling problem into a format that a Rydberg atom quantum computer can understand and solve. While the current quantum hardware isn't fast enough to beat a regular computer yet, the experiment proves the method works and suggests that with better hardware in the near future, this approach could revolutionize how we plan space missions.

Technical Summary: Satellite Mission Planning with Rydberg Atoms

Problem Definition

The paper addresses the Satellite Mission Planning (SMP) problem, specifically for a fleet of Earth Observation satellites tasked with scanning a high density of targets (e.g., cities) within a single day. The objective is to assign observation requests to specific satellites to maximize the total value of completed missions while adhering to strict operational constraints.

Key constraints include:

Resource Limits: Battery capacity (recharged by sunlight) and onboard memory (requiring periodic downlinks).
Agility: Satellites require reorientation (slew) time between targets, limited by rotation speed to prevent image vibration and loss of resolution.
Environmental Factors: Daylight operation requirements and cloud coverage (incorporated into opportunity windows).
Priorities: Requests have varying criticality levels.

The problem is mathematically formulated as a maximization of the total value of observations subject to binary decision variables representing whether a satellite $s$ observes target $t$ in time window $w$ .

Methodology

The authors propose encoding the SMP problem into a Maximum Independent Set (MIS) problem, which is then solved using a Quantum Processing Unit (QPU) based on Rydberg atoms in analog mode.

1. Problem Encoding

Graph Construction: The scheduling problem is mapped to a graph where nodes represent "Data Take Opportunities" (DTOs)—specific combinations of a satellite, a target, and a time slot.
Edges: Edges are added between nodes representing incompatible opportunities (e.g., a single satellite cannot be in two places at once, or a single target cannot be observed twice simultaneously).
Agility Consideration: The authors refine a "naive" formulation by incorporating satellite agility. Instead of fixed time slots, the DTO generation accounts for the variable time required for a satellite to reorient (slew) based on its current attitude, reducing the total number of nodes in the graph compared to fixed-slot methods.

2. Quantum Solvers

The paper explores two strategies for embedding the problem onto Rydberg hardware:

Autoencoder Embedding: A neural network approach to map graph nodes to physical atom positions while minimizing a loss function that respects hardware constraints (unit disk property, Rydberg blockade). The authors note this method was discarded for further experiments due to the excessive length of the training phase.
QUBO Formulation: The problem is mapped to a Quadratic Unconstrained Binary Optimization (QUBO) model. The Rydberg Hamiltonian is tuned to minimize the energy of the system, where the ground state corresponds to the solution of the MIS problem. This approach utilizes an adiabatic evolution strategy, starting from an initial state and slowly evolving the Hamiltonian parameters (laser amplitude $\Omega$ and detuning $\delta$ ).

3. Classical Baseline and Decomposition

Decomposition: Since the generated graphs often exceed the capacity of current QPUs (limited to ~100 atoms), the authors employ a decomposition strategy to split large graphs into smaller, disconnected subgraphs. The MIS of the total graph is the union of the MIS of these subgraphs.
Classical Comparison: A baseline is established using the NetworkX Python library to solve the MIS problem classically.

Key Contributions

First Application: This work represents the first known use of a Rydberg-atom-based QPU to solve the Satellite Mission Planning problem.
Encoding Strategy: The proposal of a specific strategy to encode SMP into a MIS problem, including the integration of satellite agility constraints into the DTO generation.
Software Release: Development and open-sourcing of a Python package (spot) to reproduce the results, simulate satellite trajectories (using TLE strings and OREKIT), and interface with QPU solvers.
Comparative Analysis: A detailed benchmark comparing quantum (QUBO) and classical (NetworkX) approaches in terms of solution quality (completion rate) and time-to-solution.

Results

Numerical experiments were conducted using a dataset of virtual satellites (ISS trajectories) and random city targets, varying the number of requests (10 to 2000) and time-step discretization (30s, 60s, 90s).

Solution Quality: Both the classical solver and the QUBO-based solver achieved similar global completion rates for up to 1,000 requests. The QUBO solver successfully recovered the main performance metrics of the classical approach.
Time-to-Solution:
- The total time to solution for the quantum approach (including queue wait times) was currently prohibitive compared to classical methods.
- However, the effective run time (excluding queue wait) for the QPU showed a lower slope relative to the number of requests compared to classical emulations.
- The sampling rate of the current QPU (<1 Hz) is independent of graph size, whereas classical solvers scale with graph complexity.
Scalability: Most generated subgraphs contained fewer than 100 nodes, making them suitable for current-generation QPUs.

Significance and Claims

The paper concludes modestly regarding the current state of quantum advantage but highlights significant potential for the future:

Current Limitations: The authors acknowledge that no speedup was observed in the current operational context due to the low sampling frequency of existing QPUs and queue wait times.
Future Outlook: The significance lies in the scalability of the approach. The authors project that future QPU generations, with sampling frequencies potentially increasing by orders of magnitude (e.g., 10x per shot), could eventually surpass classical naive MIS algorithms for large-scale instances.
Operational Utility: The work demonstrates that formulating SMP as an MIS problem is a viable pathway for Rydberg architectures, providing a foundational framework for future operational deployment as hardware matures.

The authors emphasize that this is an exploratory study establishing the feasibility of the approach rather than a demonstration of immediate quantum supremacy over classical solvers.