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.
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.
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 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.
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.
Quantum annealing is a promising heuristic for combinatorial optimization, but on current hardware its performance degrades for larger and more complex problems due to noise and small energy gaps. Reverse annealing has been proposed as a refinement strategy, yet it remains unclear when it provides systematic advantages over standard forward annealing or simply increasing annealing time. We find that combining forward and reverse annealing consistently improves solution quality and efficiency across multiple problem classes. The benefits of reverse annealing increase with problem complexity and are strongest in regimes where forward annealing is increasingly limited. Moreover, reverse annealing yields larger efficiency gains than simply extending forward annealing times. We establish these results through a systematic experimental study on a D-Wave Advantage system, benchmarking reverse annealing across Max-Cut, Number Partitioning, and sparse clustering problems while varying reverse distance, pause duration, and annealing time. We identify a narrow optimal regime for reverse annealing parameters linked to the location of freeze-out points and energy-level crossings in the annealing schedule. These findings demonstrate that reverse annealing is most valuable for large, high-complexity optimization problems and is likely to gain importance as quantum annealing hardware scales toward more realistic applications.
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.
Efficient production planning is essential in modern manufacturing to improve performance indicators such as lead time and to reduce reliance on human intuition. While mathematical optimization approaches, formulated as job shop scheduling problems, have been applied to automate this process, solving large-scale production planning problems remains computationally demanding. Moreover, many practical scenarios involve conflicting objectives, making traditional scalarization techniques ineffective in finding diverse and useful Pareto-optimal solutions. To address these challenges, we developed a quantum-classical hybrid algorithm that decomposes the problem into two subproblems: resource allocation and task scheduling. Resource allocation is formulated as a quadratic unconstrained binary optimization problem and solved using annealing-based methods that efficiently explore complex solutions. Task scheduling is modeled as a mixed-integer linear programming problem and solved using conventional solvers to satisfy detailed scheduling constraints. We validated the proposed method using benchmark instances based on foundry production scenarios. Experimental results demonstrate that our hybrid approach achieves superior solution quality and computational efficiency compared to traditional monolithic methods. This work offers a promising direction for high-speed, multi-objective scheduling in industrial applications.