Executive Summary
On May 2020, researchers at Chalmers University of Technology, Sweden, and Jeppesen Systems published a research article on quantum algorithms for the Tail Assignment Problem (TAP) . The latter is the problem of deciding which individual aircraft should operate each flight. Each flight’s route, a set of flights operated in sequence by the same aircraft, has to satisfy a number of constraints to be considered legal to operate. The goal is to minimise the total cost of route and unassigned flights
The authors simulate up to 25 qubits using a classical computer and employ the so-called Quantum Approximate Optimization Algorithms (QAOA) for a proof-of-concept experiment. The scaled-down setup involves up to 278 flights and 25 routes.
Our opinions
A quantum computer can find the global optimum of the TAP exponentially faster than a classical computer, using the so-called Grover’s algorithm. However, such algorithm would require a fault-tolerant quantum computer which is still in its infancy state. The authors therefore use QAOA, the hybrid quantum-classical algorithm designed for near-term noisy quantum devices. The drawback is that quantum speed up of QAOA when applying to the TAP is unclear compared to Grover’s algorithm.
In addition, the authors further simplify the optimisation problem to a problem of finding feasible solutions. Although the latter is still a hard problem for a classical computer, further modification on the QAOA protocol is needed to order to tackle a real-world TAP scenario.
