QAOA for Optimal Flight Gate Assignment

The QAOA is one of the candidates for quantum algorithms which might outperform classical approaches, while being amenable to NISQ devices. The target application for this approach is finding approximate solutions to combinatorial optimization problems. Since real world combinatorial optimization problems almost always have hard constraint, the algorithm was generalized to the Quantum Alternating Operator Ansatz. This approach consists of two alternating operators. First the phase separation operator which stems from the original cost function and second, a suitable mixing operator which explores the whole feasible subspace while conserving the hard constraints.

In this work, we present a Quantum Alternating Operator Ansatz for the problem of optimal assignment of airplanes to gates in a large airport hub. This is a hard operational planning problem with real world impact. We investigate several problem variations and their different relationships to NP-hard graph coloring problems. Our primary contribution is the development of novel mixing operators for the different problem settings and facilitate efficient QAOA implementation. For each case we analyse the quantum resource requirements and discuss the feasibility of using real-world problem input data.