본 논문은 다수 에이전트 경로 찾기(MAPF) 문제에 대한 최초의 최적 하이브리드 양자-고전 알고리즘을 제시한다. MAPF는 여러 에이전트가 공유 공간에서 충돌 없이 목표 위치에 도달하는 경로를 결정하는 문제로, 특히 많은 수의 에이전트를 다룰 때 계산적으로 어려워진다. 본 논문에서는 분기-절단-가격(branch-and-cut-and-price) 기반의 하이브리드 알고리즘을 제시하며, 양자 컴퓨팅(QC)을 충돌 그래프에 기반한 QUBO 문제를 반복적으로 풀이하는 데 통합한다. 실제 양자 하드웨어 실험과 벤치마크 데이터 결과를 통해 기존 QUBO 공식 및 최첨단 MAPF 솔버보다 우수한 성능을 보임을 입증한다.
