Applying Quantum Approximate Optimization Algorithm to the Oversubscribed Satellite Scheduling Problem

This paper explores the application of the quantum approximate optimization algorithm (QAOA) to the oversubscribed satellite scheduling problem (OSSP), a critical challenge in optimizing communication tasks between satellites and ground stations. The OSSP involves assigning tasks within predefined time windows while minimizing conflicts from overlapping assignments, a problem inherently combinatorial in nature. By formulating the OSSP as a quadratic unconstrained binary optimization problem and translating it into a quantum circuit suitable for QAOA, we present an algorithm for the optimization of the QAOA’s parameters as the number of circuit levels p increases, by retaining the best parameter values found at each iteration. Experimental evaluations on quantum simulators demonstrate the effectiveness of our approach, thus realizing the QAOA’s potential in addressing complex scheduling tasks efficiently and providing insights into its scalability and applicability in real-world satellite operations.