  Satellite mission planning for Earth observation satellites is a
combinatorial optimization problem that consists of selecting the optimal
subset of imaging requests, subject to constraints, to be fulfilled during an
orbit pass of a satellite. The ever-growing amount of satellites in orbit
underscores the need to operate them efficiently, which requires solving many
instances of the problem in short periods of time. However, current classical
algorithms often fail to find the global optimum or take too long to execute.
Here, we approach the problem from a quantum computing point of view, which
offers a promising alternative that could lead to significant improvements in
solution quality or execution speed in the future. To this end, we study a
planning problem with a variety of intricate constraints and discuss methods to
encode them for quantum computers. Additionally, we experimentally assess the
performance of quantum annealing and the quantum approximate optimization
algorithm on a realistic and diverse dataset. Our results identify key aspects
like graph connectivity and constraint structure that influence the performance
of the methods. We explore the limits of today's quantum algorithms and
hardware, providing bounds on the problems that can be currently solved
successfully and showing how the solution degrades as the complexity grows.
This work aims to serve as a baseline for further research in the field and
establish realistic expectations on current quantum optimization capabilities.
