QUARGS - Quantum Reinforced Ground Station Scheduling

Kurzfassung

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.