Hybrid quantum-classical end-to-end pipeline for solving MILPs: a vehicle routing case study

기술 요약: MILP 해결을 위한 하이브리드 양자-고전 엔드 투 엔드 파이프라인

문제 정의
혼합 정수 선형 계획법(Mixed-Integer Linear Programming, MILP) 문제는 물류 및 공급망 관리와 같은 산업 분야에서 중요한 의사결정의 중심이지만, 조합론적 특성으로 인해 계산적으로 매우 까agt습니다. 벤더스 분해(Benders Decomposition, BD)와 같은 분해 기법은 문제를 마스터 문제(MP)와 부문제(SP)로 분리하여 대규모 MILP를 해결하는 데 널리 사용되지만, 수렴 속도가 느려지는 경우가 많습니다. 이러한 수렴은 마스터 문제에 추가할 정보가 풍부한 "컷(cut)"(제약 조건)을 선택하는 과정에 결정적으로 의존합니다. 이전 연구인 Paterakis [1]는 이 컷 선택 단계를 가속화하기 위해 양자 어닐링을 사용하는 방식을 제안했습니다. 그러나 양자 어닐링은 확장 시 상당한 오버헤드를 유발하는 비용이 많이 드는 마이너 임베딩(minor-embedding) 절차를 필요로 합니다.

방법론
본 논문은 다중 솔루션을 통한 다중 컷(Multiple Cuts via Multiple Solutions, MCMS) 벤더스 분해 접근 방식을 확장한 엔드 투 엔드 하이브리드 양자-고전 최적화 프레임워크를 제시합니다. 핵심 혁신은 양자 어닐링 단계를 게이트 기반 양자 근사 최적화 알고리즘(Quantum Approximate Optimization Algorithm, QAOA) 구현으로 대체하는 것입니다.

프레임워크의 작동 방식은 다음과 같습니다:

1. MCMS 벤더스 분해: 알고리즘은 매 반복마다 여러 개의 후보 솔루션을 생성하며, 여러 부문제를 병렬로 해결하여 후보 컷 풀(pool)을 생성합니다.
2. QUBO로서의 컷 선택: 과도한 수의 컷으로 인해 마스터 문제가 계산적으로 무거워지는 것을 방지하기 위해, 정보가 풍부한 컷의 부분 집합을 선택합니다. 이는 최소 집합 커버(Minimum Set Cover) 문제로 정식화되며, 이후 이차 무제약 이진 최적화(Quadratic Unconstrained Binary Optimization, QUBO) 인스턴스로 매핑됩니다.
3. QAOA 통합: 기존의 어닐링 기반 접근 방식과 달리, 본 프레임워크는 QAOA를 사용하여 QUBO를 해결합니다. 이 파이프라인은 세 가지 서로 다른 솔버와 인터페이스합니다:
   • Fermioniq의 Ava: 텐서 네트워크 회로 에뮬레이터.
   • MPS-JuliQAOA: Julia로 구축된 오픈 소스 행렬 곱 상태(Matrix Product State, MPS) 에뮬레이터.
   • IBM Quantum: 초전도 양자 하드웨어(IBM Eagle 프로세서)에서의 직접 실행.
4. 사례 연구: 프레임워크는 전형적인 물류 최적화 문제인 차량 경로 문제(Vehicle Routing Problem, VRP)에 대해 평가됩니다. 본 연구는 파이프라인의 타당성을 테스트하기 위해 QOptLib의 표준 벤치마크(고객 20명, 차량 4대)와 랜덤 토이 인스턴스(고객 5명)를 활용합니다.

주요 기여

• 게이트 기반 확장: 본 논문은 기존 HQC-MCMS 프레임워크를 양자 어닐링에서 게이트 기반 양자 컴퓨팅으로 확장하여, 텐서 네트워크 에뮬레이터와 초전도 양자 프로세서 모두에서 실행할 수 있도록 했습니다.
• 엔드 투 엔드 구현: 저자들은 QAOA 서브루틴을 고전적인 벤더스 분해 루프에 통합하는 완전하게 기능하는 파이프라인을 성공적으로 입증했습니다.
• 경험적 벤치마킹: 본 연구는 VRP 인스턴스에 대해 다양한 솔버 백엔드(고전적 Cbc, MPS-JuliQAOA, Fermioniq, IBM Quantum) 간의 파이프라인 성능에 대한 비교 분석을 제공합니다.

결과
실험 결과는 이 특정 맥락에서 현재 양자 우위의 실효성에 관한 몇 가지 중요한 통찰을 제공합니다:

• 고전적 성능: 완전히 고전적인 설정(컷 선택에 Cbc 사용)에서, 파이프라인은 20개 고객 VRP 인스턴스에 대해 실행 가능한 솔루션을 성공적으로 찾아냈으며, 반복이 진행됨에 따라 최적성 격차(optimality gap)가 감소했습니다. 다중 컷(Multi-Cut) 방식(더 많은 부문제를 사용)은 더 적은 반복 횟수로 실행 가능한 솔루션을 도출했습니다.
• 런타임 병목 현상: 고전적 파이프라인 분석 결과, 컷 선택 단계는 전체 반복 시간의 극히 일부만을 차지했습니다. 대부분의 계산 시간은 마스터 문제를 해결하는 데 소비되었습니다.
• 양자 성능: 토이 문제에 대해 QAOA를 사용하여 컷 선택 단계를 대체했을 때(MPS-JuliQAOA 사용), 전체 런타임은 고전적 접근 방식에 비해 크게 증가했습니다. 연구에 따르면, 이 규모에서 MPS-JuliQAOA는 최소 집합 커버 문제에 대해 고전적 솔버인 Cbc보다 훨씬 비효률적입니다.
• QAOA 출력: 양자 하드웨어 및 에뮬레이터에서의 실험 결과, 테스트된 구성들에 대해 대부분의 QAOA 샘플은 실행 불가능한 솔루션(즉, 유효한 집합 커버를 형성하지 않음)을 생성했습니다. 더 깊은 회로($p=3$)가 더 얕은 회로($p=1$)보다 더 최적인 비용 샘플을 생성하기는 했으나, 전반적인 성능이 고전적 방법을 능가하지는 못했습니다.

의의 및 주장
본 논문은 프레임워크의 현재 상태에 대해 겸허한 평가를 내리며 마무리됩니다. 저자들은 테스트된 문제 크기와 구성에 대해 양자 우위가 나타날 가능성이 낮다고 명시적으로 밝힙니다. 주요 이유는 두 가지입니다:

1. 양자 가속의 대상인 컷 선택 단계가 현재의 고전적 MCMS 파이프라인에서 계산적 병목 현상이 아닙니다. 즉, 마스터 문제를 해결하는 과정이 런타임을 지배합니다.
2. 고전적 솔버(Cbc)가 해당 규모의 특정 최소 집합 커버 인스턴스에 대해 QAOA 구현체보다 압도적으로 뛰어납니다.

저자들은 본 파이프라인이 기술적으로 기능하며 양자 강화 최적화를 향한 재현 가능한 단계임을 입증하지만, 집합 커버 문제를 QUBO로 변환하는 과정에서 상당한 오버헤드가 발생한다는 점을 강조합니다. 그들은 향-연구가 컷 선택 단계가 더 중요한 병목 현상이 될 수 있는 더 큰 규모의 벤치마킹과, 더 강력한 양자 처리 장치(QPU)가 잠재적으로 가치를 제공할 수 있는 방향으로 진행되어야 한다고 주장합니다. 본 연구는 실질적인 중소규모 인스턴스의 특정 분해 단계에서 현재의 양자 방법이 아직 속도 향상을 제공하지 못함을 보여주는 경험적 분석으로서의 역할을 합니다.