Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer

기술 요약: 게이트 기반 하드웨어 상의 QAOA를 통한 양자 보조 차량 경로 문제(VRP)

문제 정의
차량 경로 문제(Vehicle Routing Problem, VRP)는 물류 및 운송 분야의 핵심적인 NP-난해(NP-hard) 조합 최적화 과제로, 고객 방문, 차량 용량, 경로 연속성 등의 제약 조건을 만족하면서 비용(거리, 시간, 연료)을 최소화하는 것을 목표로 한다. 고전적 알고리즘은 지수적 스케일링으로 인해 규모가 다소 커지더라도 최적해를 찾는 데 어려움을 겪는다. 본 연구는 특히 회로 깊이(circuit depth), 큐비트 연결성, 하드웨어 노이즈에 의한 제약에 초점을 맞추어, NISQ(Noisy Intermediate-Scale Quantum) 시대의 게이트 기반 양자 컴퓨터에 VRP를 매핑하는 과제를 다룬다.

방법론
저자들은 양자 근사 최적화 알고리즘(QAOA)을 VRP의 링크 기반 정식화(link-based formulation)와 결합한 하드웨어 기반 프레임워크를 제안한다. 방법론은 다음 단계로 진행된다:

1. 문제 정식화: VRP는 노드 $i$와 $j$ 사이의 링크를 차량이 통과하는지 여부를 나타내는 방향성 에지 변수($x_{i,j}$)를 사용하여 모델링된다. 시간 확장(time-expanded) 방식이나 경로 순서(route-order) 방식과 달리, 이 접근법은 명시적인 순서 변수를 피한다.
2. 제약 조건 인코딩: 핵심 제약 조건인 흐름 보존(각 고객을 정확히 한 번 방문), 데포(depot) 진입/출입 횟수, 서브투어 제거(subtour elimination)는 페널티 항을 통해 비용 해밀토니안($H_C$)에 직접 인코딩된다. 이는 제약이 있는 문제를 이차 무제약 이진 최적화(QUBO) 문제로 변환한다.
3. 해밀토니안 매핑: QUBO는 QAOA에 적합한 이징 해밀토니안(Ising Hamiltonian)으로 매핑된다. 비용 해밀토니안은 선형 비용을 위한 파울리-Z 항($Z_i$)과 이차 페널티를 위한 파울리-Z 상호작용($Z_i Z_j$)으로 구성된다. 솔루션 공간을 탐색하기 위해 표준 혼합 해밀토니안($H_M = \sum X_i$)이 사용된다.
4. 회로 구현: 알고리즘은 IBM Quantum System One(Eagle r3, 127 큐비트)에서 구현된다. 워크플로우는 다음을 포함한다:
   • 트랜스파일링(Transpilation): 논리 큐비트를 물리적 헤비-헥스(heavy-hex) 격자 토폴로지에 매핑하며, 필요한 스왑 게이트(swap gates)를 도입한다.
   • 오류 완화(Error Mitigation): 유휴 큐비트의 결맞음(coherence)을 유지하기 위한 동적 디커플링(dynamic decoupling)과 노이즈 채널을 특정 시그니처로 변환하기 위한 파울리 트월링(Pauli twirling)을 적용한다.
   • 하이브리드 최적화: 고전적 최적화 도구인 COBYQA가 기대 비용 $\langle \psi | H_C | \psi \rangle$를 최소화하기 위해 변분 파라미터($\gamma, \beta$)를 반복적으로 조정한다.
5. 실험 파라미터: 본 연구는 페널티 스케일링(특히 페널티 계수를 에지 가중치의 합의 두 배로 설정)과 계수 정규화(파울리 항의 크기를 1로 제한)가 솔루션 타당성에 미치는 영향을 조사한다.

주요 기여

• 방향성 에지 기반 정식화: 저자들은 흐름 보존과 서브투어 제거를 비용 해밀토니안에 직접 내장하는 정식화를 개발했다. 이 접근법은 시간 확장 방식의 높은 큐비트 오버헤드와 경로 순서 방식의 계승(factorial) 복잡도를 피할 수 있어, 근미래 장치에 더 적합하다.
• 전체 하드웨어 파이프라인: 본 연구는 이상적인 시뮬레이션에만 의존하지 않고, 문제 인코딩 및 이징 매핑부터 회로 합성, 트랜스파일링, 실행에 이르는 전체 파이프라인을 실제 양자 하드웨어에서 실행한다.
• 병목 현상에 대한 경험적 분석: 본 연구는 VRP 정식화가 트랜스파일링 후 큐비트 수와 2-큐비트 게이트 깊이에 미치는 영향을 정량적으로 평가하여, 현재의 초전도 아키텍처에서 회로 깊이가 제약된 라우팅의 주요 병목임을 확인했다.
• 파라미터 민감도 통찰: 연구는 솔루션의 타당성이 페널티 파라미터 선택과 해밀토니안 계수 정규화에 결정적으로 의존함을 보여준다. 특히, 정규화는 정규화되지 않은 방식이 실패하는 더 큰 인스턴스(4 및 5개 노드)에서 실행 가능한 솔루션을 샘플링하는 능력을 크게 향상시킨다.

결과

• 소규모 규모의 성공: 3개 노드, 2대 차량 인스턴스의 경우, QAOA는 서브투어 제거를 포함한 모든 제약 조건을 만족하는 최적해(비트 문자열 111010)를 높은 확률로 찾아냈다.
• 확장성 과제: 문제 규모가 커짐에 따라(예: 4개 및 5개 노드 인스턴스) 필요한 게이트 수가 기하급급수적으로 증가했다. 4개 노드 문제는 14개 큐비트 회로와 3,000개 이상의 게이트를 필요로 하며 실행에 2시간 이상 소요되었으나, 실행 불가능한 솔루션을 생성했다. 5개 노드 문제는 30개 큐비트 회로와 약 30,000개의 게이트를 필요로 했다.
• 정규화의 영향: 계수 정규화 없이는 4 및 5개 노드 인스턴스의 고확률 영역에서 최적 경로를 일관되게 식별하는 데 실패했다. 정규화와 1.5~2.0의 페널티 승수를 적용했을 때, 상위 1,000개 샘플링된 비트 문자열의 타당성 비율이 크게 개선되었다.
• 하드웨어 한계: 본 연구는 현재의 하드웨어 노이즈와 제한된 결맞음 시간이 더 큰 VRP 인스턴스에 필요한 깊은 QAOA 회로의 실행을 방해함을 확인했다. 4개 노드 문제에 대해 샘플링된 상위 10개 상태는 세심한 파라미터 튜닝 없이는 모두 실행 불가능했다.

의의 및 주장
본 논문은 대규모 VRP에 대해 고전적 솔버보다 양자 우위를 입증하는 것이 아니라, 현재의 NISQ 시대의 한계를 명확히 하는 실질적인 하드웨어 실행 평가로서의 의의를 주장한다. 저자들은 QAOA가 이론적으로 VRP를 해결할 수 있지만, 회로 복잡성(특히 2-큐비트 게이트 깊이)의 급격한 증가와 노이즈 누적이 현재로서는 매우 작은 인스턴스로 적용을 제한하고 있다고 주장한다.

본 연구의 주요 가치는 향후 양자 최적화를 위한 구체적인 설계 통찰을 제공하는 데 있다:

1. 정식화 선택: 에지 기반 정식화는 낮은 큐비트 및 게이트 요구량 덕분에 현재 가용 하드웨어에서 시간 확장 또는 경로 순서 인코딩보다 더 실현 가능하다.
2. 파라미터 휴리스틱: 계수 정규화와 특정 페널티 스케일링(에지 가중치 합의 약 2배)은 더 큰 인스턴스에서 실행 가능한 솔루션을 회복하는 데 필수적이다.
3. 방법론적 방향: VRP를 위한 양자 최적화의 발전은 알고리즘적 개선뿐만 아니라, 노이즈와 깊이 제약을 완화하기 위한 하드웨어의 발전(높은 큐비트 수, 낮은 오류율)과 하이브리드 전략(예: 파라미터 전이 학습, 동적 회로)이 필요함을 제시한다.

저자들은 확장성 문제가 여전히 제약되어 있지만, 본 연구가 양자 하드웨어에 VRP를 구현하기 위한 실질적인 경로를 구축하고 근미래 양자 최적화의 발전에 필요한 구체적인 방법론적 방향을 식별했다고 결론짓는다.