NASA: Quantum Annealing for Spacecraft Mission Scheduling

The Problem

Scheduling instrument observations across a fleet of Earth-observing satellites is one of the hardest operational problems in space mission management. Each satellite has constrained power budgets, limited downlink windows, competing observation requests, and orbital geometry that changes by the minute. With dozens of satellites and thousands of observation requests per day, this is a constraint satisfaction problem with a combinatorial search space that grows exponentially.

NASA’s Quantum Artificial Intelligence Laboratory (QuAIL) at Ames Research Center has been running quantum computing experiments since 2013, when NASA became one of the first organizations to install a D-Wave system. The QuAIL team has applied quantum annealing to crew scheduling, mission planning, and anomaly detection in addition to satellite operations.

QUBO Formulation for Satellite Scheduling

The scheduling problem maps naturally to a Quadratic Unconstrained Binary Optimization (QUBO) formulation. Each binary variable represents a decision: assign observation request i to time window j on satellite k.

import dimod
import numpy as np
from dwave.system import DWaveSampler, EmbeddingComposite
from dwave.samplers import SimulatedAnnealingSampler

# Build a small satellite scheduling QUBO
# Variables: x[i][j] = 1 if request i is scheduled in window j
n_requests = 8
n_windows = 6

# Penalty weight for constraint violations
penalty = 5.0

# Objective: maximize observation value (negate for minimization)
linear = {}
quadratic = {}

request_values = np.random.uniform(1, 10, n_requests)

for i in range(n_requests):
    for j in range(n_windows):
        var = f"x_{i}_{j}"
        # Reward for scheduling high-value observations
        linear[var] = -request_values[i]

# Constraint 1: each request scheduled at most once
for i in range(n_requests):
    vars_i = [f"x_{i}_{j}" for j in range(n_windows)]
    for a in range(len(vars_i)):
        for b in range(a + 1, len(vars_i)):
            quadratic[(vars_i[a], vars_i[b])] = 2 * penalty

# Constraint 2: each window handles at most one request
for j in range(n_windows):
    vars_j = [f"x_{i}_{j}" for i in range(n_requests)]
    for a in range(len(vars_j)):
        for b in range(a + 1, len(vars_j)):
            quadratic[(vars_j[a], vars_j[b])] = 2 * penalty

bqm = dimod.BinaryQuadraticModel(linear, quadratic, vartype='BINARY')

# Run on simulated annealing (swap in DWaveSampler for real hardware)
sampler = SimulatedAnnealingSampler()
response = sampler.sample(bqm, num_reads=200)
best = response.first.sample

scheduled = [(i, j) for i in range(n_requests)
             for j in range(n_windows) if best.get(f"x_{i}_{j}", 0) == 1]
print(f"Scheduled {len(scheduled)} observations: {scheduled}")

QAOA Experiments on IBM Hardware

For smaller instances (up to 20 variables), the QuAIL team also tested QAOA using Qiskit on IBM Quantum hardware. The QAOA formulation used the same QUBO objective but executed as a parameterized quantum circuit optimized with COBYLA.

At p=2 circuit depth, QAOA solutions approached optimal on 20-variable scheduling instances. Increasing to p=3 improved solution quality but required circuit depths that current hardware noise levels degraded significantly.

Results

NASA compared four approaches on scheduling instances ranging from 50 to 1000 variables:

• D-Wave hybrid solver: Matched constraint programming (CP) quality on all tested sizes up to 1000 variables. Runtimes were comparable, with hybrid solver occasionally faster on mid-range instances
• D-Wave direct (QPU only): Embedding overhead limited practical instance size to around 200 variables with good results
• QAOA on IBM Quantum: Competitive on instances up to 20 variables; noise dominated at larger sizes
• Classical CP and integer programming: Solved all instances; Gurobi found provably optimal solutions on instances up to 500 variables in under a minute

No quantum approach demonstrated a speed or quality advantage over classical methods at operationally relevant scales. The QuAIL team considers this an expected result given current hardware and views the work as establishing methodology for when fault-tolerant hardware arrives.

What’s Next

NASA continues quantum computing research under the DOE/NASA collaboration and through the QuAIL program. Priority areas include:

1. Larger hybrid problems: D-Wave’s hybrid solvers now support millions of variables via decomposition; testing on full operational scheduling instances is planned
2. Fault-tolerant projections: Analytical work on how many logical qubits are needed to achieve advantage over classical CP solvers for mission scheduling
3. Quantum annealing for anomaly detection: Applying similar QUBO formulations to spacecraft telemetry classification

Learn more: Ocean SDK Reference | Qiskit Reference