Quantum Variational Algorithms for the Aircraft Deconfliction Problem

Tactical deconfliction problem involves resolving conflicts between aircraft to ensure safety while maintaining efficient trajectories. Several techniques exist to safely adjust aircraft parameters such as speed, heading angle, or flight level, with many relying on mixed-integer linear or nonlinear programming. These techniques, however, often encounter challenges in real-world applications due to computational complexity and scalability issues. This paper proposes a new quantum approach that applies the Quantum Approximate Optimization Algorithm (QAOA) and the Quantum Alternating Operator Ansatz (QAOAnsatz) to address the aircraft deconfliction problem. We present a formula for designing quantum Hamiltonians capable of handling a broad range of discretized maneuvers, with the aim of minimizing changes to original flight schedules while safely resolving conflicts. Our experiments show that a higher number of aircraft poses fewer challenges than a larger number of maneuvers. Additionally, we benchmark the newest IBM quantum processor and show that it successfully solves four out of five instances considered. Finally, we demonstrate that incorporating hard constraints into the mixer Hamiltonian makes QAOAnsatz superior to QAOA. These findings suggest quantum algorithms could be a valuable algorithmic candidate for addressing complex optimization problems in various domains, with implications for enhancing operational efficiency and safety in aviation and other sectors.