Applying the Quantum Approximate Optimization Algorithm to the UAV Collision Avoidance Problem

• Kalleb C. Santos UFSC
• Maria Eduarda W. M. Vianna UFSC
• Mateus K. de Oliveira UFSC
• Evandro Chagas Ribeiro da Rosa UFSC
• Alison R. Panisson UFSC
• Luiz F. Bittencourt UNICAMP
• Roberto Rodrigues-Filho UnB

DOI: https://doi.org/10.5753/sbccq.2026.22455

Resumo

The increasing availability of quantum hardware has stimulated interest in applying quantum algorithms to combinatorial optimization problems. Collision avoidance for unmanned aerial vehicles (UAVs) is one such challenge due to the computational complexity of coordinating multiple agents in shared airspace. In this paper, we formulate the problem as a Quadratic Unconstrained Binary Optimization (QUBO) model that captures route selection and collision constraints, enabling the use of the Quantum Approximate Optimization Algorithm (QAOA). To improve efficiency, we introduce a constrained QAOA Ansatz employing an XY-mixer that preserves one-hot route assignment constraints and restricts the search space to valid solutions. We evaluate the approach through noiseless simulations and device-based noise models, analyzing its behavior under realistic conditions and highlighting the opportunities and limitations of near-term quantum hardware for multi-agent routing problems.

Referências

Clark, J., West, T., Zammit, J., Guo, X., Mason, L., and Russell, D. (2019). Towards real time multi-robot routing using quantum computing technologies. In Proc. Int. Conf. on High Performance Computing in Asia-Pacific Region, HPCAsia ’19. ACM.

Da Rosa, E. C. R. and De Santiago, R. (2022). Ket quantum programming. ACM Journal on Emerging Technologies in Computing Systems, 18(1):1–25.

de Oliveira, F. M. C., Bittencourt, L. F., Bianchi, R. A. C., and Kamienski, C. A. (2024). Drones in the big city: Autonomous collision avoidance for aerial delivery services. IEEE Transactions on Intelligent Transportation Systems, 25(5):4657–4674.

Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.

Haba, R., Mano, T., Ueda, R., Ebe, G., Takeda, K., Terabe, M., and Ohzeki, M. (2025). Routing and scheduling optimization for urban air mobility fleet management using quantum annealing. Scientific Reports, 15(1):4326.

Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., and Biswas, R. (2019). From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12(2):34.

Huang, Z., Li, Q., Zhao, J., and Song, M. (2022). Variational quantum algorithm applied to collision avoidance of unmanned aerial vehicles. Entropy, 24(11):1685.

Rezaee, M. R., Hamid, N. A. W. A., Hussin, M., and Zukarnain, Z. A. (2024). Comprehensive review of drones collision avoidance schemes: Challenges and open issues. IEEE Transactions on Intelligent Transportation Systems, 25(7):6397–6426.

Tang, J., Lao, S., and Wan, Y. (2022). Systematic review of collision-avoidance approaches for unmanned aerial vehicles. IEEE Systems Journal, 16(3):4356–4367.

Valavanis, K. P. and Vachtsevanos, G. J. (2014). Handbook of unmanned aerial vehicles. Springer Publishing Company, Incorporated.

Vianna, M. E. W. M., Panisson, A. R., and Rodrigues-Filho, R. (2025). Quantum computing for drone collision detection and avoidance: A systematic mapping study. In VIII ⟨WECIQ|WCQ⟩, Florianópolis, SC, Brasil. UFSC.

Wang, Z., Rubin, N. C., Dominy, J. M., and Rieffel, E. G. (2020). XY-mixers: analytical and numerical results for QAOA. Physical Review A, 101(1):012320.