Qubit-Efficient Quantum Optimization Algorithms for Multi-Drone Routing and Path Planning

Coordinating multiple drone delivery routes under realistic industrial constraints presents a complex optimization challenge, often modeled as a Vehicle Routing Problem (VRP). This involves managing the paths of multiple drones to minimize travel distance or time while satisfying logistical requirements. Classical methods like mixed-integer programming and heuristics often struggle with scalability due to the combinatorial explosion in multi-drone VRPs. In this work, we develop qubit-efficient variational quantum algorithms for a multi-drone path-planning problem, leveraging quantum computing on Noisy Intermediate-Scale Quantum (NISQ) devices. The encoding scheme, initially developed by Tan et al. [1], has succeeded in applications like LNG-vehicle routing [2] and financial transaction settlement [3]. Building on this foundation, we adapt these techniques to multi-drone path-planning, formulating the problem as a Quadratic Unconstrained Binary Optimization (QUBO) model. Our approach seeks high-quality approximate solutions using fewer quantum resources, potentially outperforming classical methods in scalability and quality. We benchmark our algorithms against standard Quantum Approximate Optimization Algorithm (QAOA) implementations on both simulators and real quantum hardware. Preliminary results indicate this qubit-efficient encoding is promising for real-world applications, though further work is needed to scale to larger instances.