Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem: part 2*

We investigate the Quantum Approximate Optimization Algorithm (QAOA) applied to the Exact Cover and Set Partitioning problem with multiple feasible solutions. The problem instances have been extracted from real world aircraft assignment problems. For the Exact Cover problem our numerical results indicate that for a given success probability of finding a feasible solution the required algorithm depth decreases with the number of feasible solutions. For the Set Partitioning problem on the other hand, we find that for a given success probability of finding the optimal solution the required algorithm depth can increase with the number of feasible solutions, which in the worst case is exponential in the problem size. We also address the importance of properly weighting the objective and constraint parts of the Hamiltonian when solving the Set Partitioning problem since these weights have a significant impact on the QAOA performance.