Towards Quantum Gate-Model Heuristics for Real-World Planning Problems

Many challenging scheduling, planning, and resource allocation problems come with real-world input data and hard problem constraints, and reduce to optimizing a cost function over a combinatorially-defined feasible set, such as colorings of a graph. Towards tackling such problems with quantum computers using quantum approximate optimization algorithms,
we present novel efficient quantum alternating operator ansatz (QAOA) constructions for optimization problems over proper colorings of chordal graphs. As our primary application we consider the Flight-Gate Assignment problem, where flights are assigned to airport gates as to minimize the total transit time of all passengers, and feasible assignments correspond to proper graph colorings of a conflict graph derived instance-wise from the input data. We leverage ideas from classical algorithms and graph theory to show our constructions have the desirable properties of restricting quantum state evolution to the feasible subspace, and satisfying a particular reachability condition for most problem parameter regimes. In addition, we show our constructions in detail, including explicit decompositions to basic quantum gates, which we use to bound the required resource scaling as low-degree polynomials of the input parameters.