Hundreds of satellites equipped with cameras orbit the Earth to capture images from locations for various purposes. Since the field of view of the cameras is usually very narrow, the optics have to be adjusted and rotated between single shots of different locations. This is even further complicated by the fixed speed-determined by the satellite's altitude-such that the decision what locations to select for imaging becomes even more complex. Therefore, classical algorithms for this Satellite Mission Planning Problem (SMPP) have already been proposed decades ago. However, corresponding classical solutions have only seen evolutionary enhancements since then. Quantum computing and its promises, on the other hand, provide the potential for revolutionary improvement. Therefore, in this work, we propose a hybrid classical quantum computing approach to solve the SMPP combining the advantages of quantum hardware with decades of classical optimizer development. Using the Variational Quantum Eigensolver (VQE), Quantum Approximate Optimization Algorithm (QAOA), and its warm-start variant (W-QAOA), we demonstrate the applicability of solving the SMPP for up to 21 locations to choose from. This proof-of-concept-which is avail-able on GitHub (https://github.com/cda-tum/mqt-problemsolver) as part of the Munich Quantum Toolkit (MQT)-showcases the potential of quantum computing in this application domain and represents a first step toward competing with classical algorithms in the future.
Hundreds of satellites equipped with cameras orbit the Earth to capture images from locations for various purposes. Since the field of view of the cameras is usually very narrow, the optics have to be adjusted and rotated between single shots of different locations. This is even further complicated by the fixed speed-determined by the satellite's altitude-such that the decision what locations to select for imaging becomes even more complex. Therefore, classical algorithms for this Satellite Mission Planning Problem (SMPP) have already been proposed decades ago. However, corresponding classical solutions have only seen evolutionary enhancements since then. Quantum computing and its promises, on the other hand, provide the potential for revolutionary improvement. Therefore, in this work, we propose a hybrid classical quantum computing approach to solve the SMPP combining the advantages of quantum hardware with decades of classical optimizer development. Using the Variational Quantum Eigensolver (VQE), Quantum Approximate Optimization Algorithm (QAOA), and its warm-start variant (W-QAOA), we demonstrate the applicability of solving the SMPP for up to 21 locations to choose from. This proof-of-concept-which is avail-able on GitHub (https://github.com/cda-tum/mqt-problemsolver) as part of the Munich Quantum Toolkit (MQT)-showcases the potential of quantum computing in this application domain and represents a first step toward competing with classical algorithms in the future.
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.
Earth imaging satellites are a crucial part of our everyday lives that enable global tracking of industrial activities. Use cases span many applications, from weather forecasting to digital maps, carbon footprint tracking, and vegetation monitoring. However, there are limitations; satellites are difficult to manufacture, expensive to maintain, and tricky to launch into orbit. Therefore, satellites must be employed efficiently. This poses a challenge known as the satellite mission planning problem, which could be computationally prohibitive to solve on large scales. However, close-to-optimal algorithms, such as greedy reinforcement learning and optimization algorithms, can often provide satisfactory resolutions. This paper introduces a set of quantum algorithms to solve the mission planning problem and demonstrate an advantage over the classical algorithms implemented thus far. The problem is formulated as maximizing the number of high-priority tasks completed on real datasets containing thousands of tasks and multiple satellites. This work demonstrates that through solution-chaining and clustering, optimization and machine learning algorithms offer the greatest potential for optimal solutions. This paper notably illustrates that a hybridized quantum-enhanced reinforcement learning agent can achieve a completion percentage of 98.5% over high-priority tasks, significantly improving over the baseline greedy methods with a completion rate of 75.8%. The results presented in this work pave the way to quantum-enabled solutions in the space industry and, more generally, future mission planning problems across industries.
The trend of building larger and more complex imaging satellite constellations leads to the challenge in managing multiple acquisition requests of the Earth surface. Optimally planning these acquisitions is an intractable optimization problem, and heuristic algorithms are used today for finding sub-optimal solutions. Recently, quantum algorithms have been considered for this purpose, due to the potential breakthroughs that they can bring in optimization, expecting either a speedup or an increase in the solution quality. Hybrid quantum-classical methods have been considered as a short-term solution for taking advantage of small quantum machines. In this paper, we propose reverse quantum annealing as a method for improving the acquisition plan obtained by a classical optimizer. We investigate the benefits of the method with different annealing schedules and different problem sizes. The obtained results provide guidelines on designing a larger hybrid quantum-classical framework based on reverse quantum annealing for this application.
Consider a constellation of n satellites in medium-earth orbit as well as k ground stations distributed over the Earth. Such satellites require semiregular contacts with mission control in order to upload telecommands or general purpose maintenances, which is done via ground stations. In order to plan ground station contacts for such a constellation it is necessary to calculate possible visibilities between satellite--ground station pairs, and then build a valid schedule from that data which satisfies all mission-specific constraints. This is a typical challenge for the mission planning system of a satellite constellation. In addition, there is often some kind of relevant optimization goal, for example fairness conditions or minimization of total number of contacts to have more time available for the actual missions objectives. Depending on the constraints for such ground station contact plans as well as the size of n and k, this problem may be hard to solve optimally. In particular, if k is much smaller than n it may be non-trivial to find any solution at all. For such problems one often employs global optimizers such as Gurobi, CPLEx or SCIP, or problem-specific heuristic search algorithms that try to find a solution that is good enough for practical purposes. While such approaches can be made to work for most real scenarios, classical solvers tend to struggle to find solutions in a reasonable time for very large satellite constellations. Due to this reason, we investigate potential applications of quantum computers to larger instances of this problem in this paper. To this end, we developed a library called QUARGS (Quantum Reinforced Ground Station Scheduling) which allows solving examples for such ground station scheduling problems using different quantum algorithms. In this paper we compare and evaluate these different solutions against each other as well as against a classical solution using the global optimizer SCIP. After an overview of similar problems in the literature we define the concrete problem including all constraints as well as possible optimization functions. Then we give a brief overview of quantum algorithms that may be used to solve such scheduling problems. This includes in particular quantum annealing (QA), quantum approximate optimization algorithm (QAOA), variational quantum eigensolvers (VQE), as well as evolutionary variational quantum eigensolvers (E-VQE). The latter in particular was implemented and published in an open-source Python library QUEASARS (Quantum Evolving Ansatz Variational Solver). Besides evaluating these algorithms on sample cases regarding their solution quality and quantum circuit depths, we discuss difficulties for the implementation of various constraints in the algorithms and their potential solutions.
Earth observation satellites (EOS) play a crucial role in collecting data for applications like weather forecasting and disaster management. Optimizing EOS missions to capture high-priority targets within constraints such as storage, energy, and weather is challenging for traditional computing methods. Quantum computing shows promise in enhancing efficiency by exploring vast solution spaces for optimal schedules, even with complex constraints. This paper demonstrates the potential of a quantum algorithm to improve real-time EOS mission planning, maximizing high-priority target acquisition under resource limitations. Compared to classical algorithms like simulated annealing and Gurobi optimizer, the proposed quantum algorithm outperformed in selecting high-priority targets by 23.46%, executed faster than Gurobi by 39.09%, and successfully satisfied all constraints for all data.
This paper presents a qualitative analysis of hybrid quantum-classical computing approaches aimed at solving complex optimization problems using near-term quantum processors. Hybrid algorithms leverage the strengths of quantum and classical computing to tackle computationally intensive tasks often constrained by current quantum hardware limitations. Through an extensive literature review and synthesis of recent empirical studies, we benchmark various hybrid algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE), focusing on their performance, scalability, and practical applicability on noisy intermediate-scale quantum (NISQ) devices. The study highlights the advantages, challenges, and future prospects of integrating hybrid quantum-classical computation in optimization domains, providing a comprehensive framework and qualitative insights into benchmarking methodologies and critical performance metrics.