Satellite tasking: the operations problem that fits a quantum computer

Why this one is different

Every problem on the neighbouring logistics and manufacturing pages fails on encoding cost before it fails on anything else: a 20-stop route needs 400 binary variables and a 10 by 10 job shop needs tens of thousands. Satellite tasking does not have that problem.

It is a maximum weighted independent set on the conflict graph, which takes exactly one binary variable per observation request. Sixteen requests means sixteen qubits. That linear encoding is what makes it the rare operations problem you can actually put on a quantum computer today, and it is the reason this page has a benchmark at all rather than an explanation of why one is impossible.

The setup

Observation windows generated from seed 20260902 with random start times, durations and values, giving a realistic conflict density. Two classical baselines: exhaustive search over all 2^n subsets, which proves the optimum, and OR-Tools CP-SAT, which is what a mission planner would actually use. QAOA at depth 2, 512 shots, COBYLA with three restarts of 150 iterations, with every circuit evaluation counted.

What the numbers say

QAOA matched the proven optimum once in three runs, at 14 requests. At 12 requests it came in 12 percent below the best schedule and at 16 requests 3.6 percent below. As a heuristic it is respectable and it is not reliable.

CP-SAT solved every instance in around 10 milliseconds, roughly a thousand times faster than QAOA, and its solve time barely moved as the problem grew. Exhaustive search rose from 0.010 to 0.210 seconds across the same range, which is the exponential curve becoming visible. CP-SAT's flatness is the point: constraint solvers prune, so they do not follow that curve.

At the sizes a quantum computer can address, the classical solver is not merely winning. It is finishing before the quantum optimiser has evaluated its first circuit.

Where this could go

The linear encoding is genuinely favourable, so the interesting extrapolation is real rather than rhetorical. A constellation-scale tasking problem with a few thousand candidate observations would need a few thousand qubits, which is a plausible hardware target in a way that 40,000 for a delivery route is not.

Two things would have to hold for that to matter. Error rates would have to fall far enough that a depth-2 QAOA circuit on thousands of qubits returns signal, and QAOA's solution quality would have to stop degrading as the instance grows, which our three data points already show it doing. Neither is settled, and the second is a software question that could be answered long before the hardware exists.

The roadmaps make the first condition concrete. Hundreds of logical qubits by 2029, which IBM and Quantinuum both target, would cover a few hundred candidate observations. That is a real constellation planning problem rather than a toy, and it is reachable precisely because the encoding is linear.

Meanwhile CP-SAT will also have improved, and it currently solves these instances in around 10 milliseconds with room to spare. Any honest projection has to beat where the classical solver will be, not where it is now, and on this problem it is not close today.