# Hybrid Quantum-Classical Multi-Agent Pathfinding

arXiv: https://arxiv.org/abs/2501.14568 · HTML: https://mlsanity.com/paper/2501.14568/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 45 references that are in the map.
- First posted on arXiv 24 Jan 2025.

## Builds on (most cited first, 12 of 12)

- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2305.03632/) (2023)
- [Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management](https://mlsanity.com/paper/1711.04889/) (2017)
- [Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks](https://mlsanity.com/paper/2110.08802/) (2021)
- [Testing Quantum and Simulated Annealers on the Drone Delivery Packing Problem](https://mlsanity.com/paper/2406.08430/) (2024)
- [Dynamic Range Reduction via Branch-and-Bound](https://mlsanity.com/paper/2409.10863/) (2024)
- [Quantum Algorithms for Drone Mission Planning](https://mlsanity.com/paper/2409.18631/) (2024)

## Built on by (most cited first, 1 of 1)

- [Kernel k-Medoids as General Vector Quantization](https://mlsanity.com/paper/2506.04786/) (2025)

## Abstract (arXiv)

Multi-Agent Path Finding (MAPF) focuses on determining conflict-free paths for multiple agents navigating through a shared space to reach specified goal locations. This problem becomes computationally challenging, particularly when handling large numbers of agents, as frequently encountered in practical applications like coordinating autonomous vehicles. Quantum Computing (QC) is a promising candidate in overcoming such limits. However, current quantum hardware is still in its infancy and thus limited in terms of computing power and error robustness. In this work, we present the first optimal hybrid quantum-classical MAPF algorithms which are based on branch-andcut-and-price. QC is integrated by iteratively solving QUBO problems, based on conflict graphs. Experiments on actual quantum hardware and results on benchmark data suggest that our approach dominates previous QUBO formulationsand state-of-the-art MAPF solvers.