Airbus: Quantum Optimization for Satellite Constellation Scheduling

The Problem

Airbus Defence and Space operates Earth observation satellites including the Pleiades constellation and SPOT series. Each satellite passes over a given ground location for a window of minutes per day. Customers submit imaging requests: specific geographic coordinates, resolution requirements, delivery deadlines. The satellite operator must schedule which requests each satellite handles on each pass, subject to hard constraints:

• Power budget: imaging sensors draw significant power; batteries must recharge between long imaging sequences
• On-board memory: raw imagery fills storage quickly; download windows to ground stations are limited
• Attitude slew rate: satellites can only rotate so fast between consecutive image targets
• Priority tiers: defense customers have pre-emption rights over commercial orders

With 200-500 competing orders per day across a multi-satellite constellation, this is a constraint-satisfaction problem that sits in the NP-hard complexity class. Classical approaches use heuristics and constraint programming. Airbus investigated whether quantum annealing and QAOA could find better schedules faster.

QUBO Formulation

The scheduling problem was reformulated as a Quadratic Unconstrained Binary Optimization (QUBO). Binary variable x_{s,r,t} = 1 means satellite s takes image r during time window t.

The objective minimizes missed high-priority orders and resource conflicts. Constraints are encoded as penalty terms added to the objective with a large coefficient lambda.

import dimod
import numpy as np

def build_satellite_scheduling_qubo(
    n_satellites: int,
    n_requests: int,
    n_windows: int,
    priorities: list,
    conflicts: list,
    power_budget: float,
    power_costs: np.ndarray,
    penalty_lambda: float = 100.0
):
    """
    Build QUBO for satellite imaging schedule.

    Variables: x[s][r][t] = 1 if satellite s takes request r in window t
    Objective: maximize priority-weighted coverage
    Constraints (as penalties):
      - Each request fulfilled at most once
      - Power budget not exceeded per satellite per orbit
      - Conflicting requests (attitude slew too large) not both scheduled
    """
    bqm = dimod.BinaryQuadraticModel(vartype="BINARY")

    # Variable names: (satellite_id, request_id, window_id)
    def var(s, r, t):
        return f"x_{s}_{r}_{t}"

    # Objective: reward for scheduling high-priority requests
    for s in range(n_satellites):
        for r in range(n_requests):
            for t in range(n_windows):
                v = var(s, r, t)
                # Negative because dimod minimizes
                bqm.add_variable(v, -priorities[r])

    # Constraint 1: each request scheduled at most once across all sat/windows
    for r in range(n_requests):
        request_vars = [var(s, r, t)
                        for s in range(n_satellites)
                        for t in range(n_windows)]
        # Penalty for scheduling same request multiple times: lambda*(sum - 1)^2
        # Expanded: lambda * (sum^2 - 2*sum + 1)
        for v in request_vars:
            bqm.add_variable(v, penalty_lambda * (-2 + 1))
        for i, v1 in enumerate(request_vars):
            for v2 in request_vars[i+1:]:
                bqm.add_interaction(v1, v2, 2 * penalty_lambda)

    # Constraint 2: power budget per satellite per pass
    for s in range(n_satellites):
        for t in range(n_windows):
            window_vars = [(var(s, r, t), power_costs[s, r, t])
                           for r in range(n_requests)]
            # Penalize exceeding power budget
            for v, cost in window_vars:
                bqm.add_variable(v, penalty_lambda * cost * (cost - 2 * power_budget))
            for i, (v1, c1) in enumerate(window_vars):
                for v2, c2 in window_vars[i+1:]:
                    bqm.add_interaction(v1, v2, 2 * penalty_lambda * c1 * c2)

    # Constraint 3: attitude conflict pairs cannot both be scheduled on same satellite
    for s in range(n_satellites):
        for (r1, r2, t) in conflicts:
            v1 = var(s, r1, t)
            v2 = var(s, r2, t)
            bqm.add_interaction(v1, v2, penalty_lambda)

    return bqm

Solving with D-Wave Hybrid

For problem sizes with hundreds of imaging orders, pure quantum annealing runs into the qubit count limit of the D-Wave Advantage (5,000+ qubits, but connectivity is sparse). D-Wave’s hybrid solver decomposes large BQMs into subproblems and iterates.

from dwave.system import LeapHybridSampler

def solve_with_dwave_hybrid(bqm, time_limit=60):
    """
    Submit QUBO to D-Wave Leap hybrid solver.
    time_limit in seconds controls how long the hybrid loop runs.
    """
    sampler = LeapHybridSampler()
    sampleset = sampler.sample(bqm, time_limit=time_limit)

    best = sampleset.first
    return {
        "energy": best.energy,
        "solution": best.sample,
        "timing": sampleset.info.get("qpu_access_time", None)
    }


def decode_schedule(solution, n_satellites, n_requests, n_windows):
    """
    Convert QUBO solution back to a human-readable schedule.
    Returns list of (satellite, request, window) tuples.
    """
    schedule = []
    for s in range(n_satellites):
        for r in range(n_requests):
            for t in range(n_windows):
                v = f"x_{s}_{r}_{t}"
                if solution.get(v, 0) == 1:
                    schedule.append((s, r, t))
    return schedule

QAOA for Small Instances

Airbus also tested QAOA on IBM hardware for smaller instances (up to 15 imaging orders). At this scale, the QUBO maps to a circuit with manageable qubit count.

from qiskit import QuantumCircuit
from qiskit.circuit import Parameter
from qiskit_aer import AerSimulator
from qiskit_algorithms import QAOA
from qiskit_algorithms.optimizers import COBYLA
from qiskit.primitives import Sampler

def run_qaoa_scheduling(qubo_matrix, n_vars, p=2):
    """
    Run QAOA on the scheduling QUBO using Qiskit.
    qubo_matrix: (n_vars x n_vars) upper-triangular matrix
    p: QAOA circuit depth (number of layers)
    """
    from qiskit_optimization import QuadraticProgram
    from qiskit_optimization.converters import QuadraticProgramToQubo
    from qiskit_optimization.algorithms import MinimumEigenOptimizer

    qp = QuadraticProgram()
    for i in range(n_vars):
        qp.binary_var(name=f"x{i}")

    # Add QUBO terms to quadratic program
    linear = {f"x{i}": float(qubo_matrix[i, i]) for i in range(n_vars)}
    quadratic = {}
    for i in range(n_vars):
        for j in range(i + 1, n_vars):
            if qubo_matrix[i, j] != 0:
                quadratic[(f"x{i}", f"x{j}")] = float(qubo_matrix[i, j])

    qp.minimize(linear=linear, quadratic=quadratic)

    sampler = Sampler()
    qaoa = QAOA(sampler=sampler, optimizer=COBYLA(maxiter=300), reps=p)
    optimizer = MinimumEigenOptimizer(qaoa)
    result = optimizer.solve(qp)

    return result.x, result.fval

Results

Airbus Defence and Space researchers, working with the German Aerospace Center (DLR), published benchmarks on realistic Earth observation acquisition planning instances, run on a D-Wave 2000Q quantum annealer. Key findings:

• The tuned quantum annealing approach ran faster than classical exact solvers on some problem instances
• Solution quality matched classical heuristic methods on smaller instances; on larger instances quality degraded, an effect the authors attribute to the limited precision of the quantum annealer
• Gate-model approaches such as QAOA remain research prototypes at small instance sizes
• Full constellation management (1,000+ orders) remains a classical problem; quantum is most useful as a subproblem solver for conflict-heavy orbit windows

The Broader Satellite Scheduling Challenge

This work is distinct from Airbus’s quantum fluid dynamics research (focused on aircraft aerodynamics). The scheduling problem is purely combinatorial and maps more naturally to current quantum annealing hardware than the continuous simulation problems in aerodynamics.

The constraint structure (hard resource limits combined with a soft priority objective) is common across aerospace planning problems: launch windows, crew scheduling, ground station handoffs. Quantum optimization methods developed for satellite scheduling are transferable to this broader class of aerospace operations problems.

Learn more: Qiskit Reference | D-Wave Reference

Sources

• Stollenwerk et al., Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer (arXiv:2006.09724)