Improving Feasibility in Quantum Approximate Optimization Algorithm for Vehicle Routing via Constraint-Aware Initialization and Hybrid XY-X Mixing

1. 연구 배경 및 문제 정의 (Problem)

• 배경: 양자 근사 최적화 알고리즘 (QAOA) 은 NP-난제인 조합 최적화 문제를 해결하기 위한 유망한 양자 알고리즘 프레임워크입니다. 특히 물류 및 운송 분야의 핵심 문제인 차량 경로 문제 (VRP) 는 QAOA 의 주요 적용 대상입니다.
• 핵심 문제: 표준 QAOA 를 VRP 에 적용할 때 가장 큰 병목 현상은 실현 가능성 (Feasibility) 문제입니다.
  • VRP 는 엄격한 제약 조건 (예: 각 노드를 한 번만 방문, 차량 수 제한 등) 을 가지며, 전체 이진 검색 공간 ($2^n$) 에서 실현 가능한 해는 극히 일부만 차지합니다.
  • 표준 QAOA 는 모든 가능한 비트 문자열에 균일한 중첩 상태 (Uniform Superposition) 로부터 시작하며, Pauli-X 믹서를 사용하여 비트를 독립적으로 뒤집습니다.
  • 이로 인해 알고리즘의 진화 과정에서 실현 가능한 해가 아닌 비실현 가능한 상태 (infeasible states) 로 확률 질량이 쉽게 이동하게 되어, 최적 해를 찾을 확률이 낮아지고 수렴 효율이 떨어집니다.
  • 기존에 제안된 제약 조건을 보존하는 XY 믹서는 해밀턴의 무게 (Hamming weight) 를 고정시키지만, 이는 초기 상태의 무게가 실현 가능한 해의 무게와 다를 경우 실현 가능 영역으로 진입할 수 없게 만드는 한계가 있습니다.

2. 제안된 방법론 (Methodology)

저자들은 QAOA 의 실현 가능성을 향상시키기 위해 제약 조건 인식 초기화 (Constraint-Aware Initialization) 와 하이브리드 XY-X 믹서 (Hybrid XY-X Mixer) 라는 두 가지 상호 보완적인 구성 요소를 제안합니다.

A. 제약 조건 인식 초기화 (Constraint-Aware Initialization)

• 개념: 모든 $2^n$ 비트 문자열에 대한 균일 중첩 대신, 문제의 구조적 정보를 반영한 선택된 부분 집합으로 초기 상태를 제한합니다.
• 구현: VRP 의 국소적 제약 조건 (예: 특정 노드에서 나가는 링크가 정확히 하나여야 하는 'one-hot' 제약) 을 초기 상태에 인코딩합니다.
  • 예를 들어, $x_i + x_j = 1$과 같은 제약 조건이 있다면, 초기 상태는 $|01\rangle$과 $|10\rangle$의 중첩만 포함하도록 설계하여 $|00\rangle$과 $|11\rangle$과 같은 비실현 가능한 상태를 초기부터 배제합니다.
• 효과: 전체 검색 공간의 크기를 줄이고, 실현 가능한 구조를 이미 만족하는 상태에 초기 확률 질량을 집중시킵니다. 이는 Grover 믹서 기반의 완전 실현 가능 초기화보다 구현이 용이하면서도 표준 균일 초기화보다 훨씬 유리한 시작점을 제공합니다.

B. 하이브리드 XY-X 믹서 (Hybrid XY-X Mixer)

• 개념: 초기화 단계에서 인코딩된 제약 조건 구조는 보존하되, 나머지 자유도는 탐색할 수 있도록 한 새로운 믹서 설계입니다.
• 구현:
  • XY 항: 초기화에서 제약된 비트 쌍 (예: $x_i + x_j = 1$을 만족하는 비트) 에 대해 XY 상호작용 ($X_i X_j + Y_i Y_j$) 을 적용하여 해당 부분의 Hamming 무게를 보존하고 구조를 유지합니다.
  • X 항: 제약이 적용되지 않은 비트나 전체 Hamming 무게를 변경해야 하는 경우에 표준 Pauli-X 연산자를 추가합니다.
  • 하이브리드 Hamiltonian: $H_{hyb} = H_{XY} + \lambda \sum X_k$ 형태로, $\lambda$는 탐색 유연성을 조절하는 가중치 파라미터입니다.
• 효과: XY 믹서만 사용할 때 발생할 수 있는 '무게 불일치'로 인한 실현 가능 영역 진입 불가 문제를 해결하면서도, 표준 X 믹서가 가진 구조 파괴 문제를 완화합니다.

3. 주요 기여 (Key Contributions)

1. 새로운 QAOA 프레임워크 제안: VRP 와 같은 제약 조건이 있는 조합 최적화 문제를 위해, 초기화와 믹서 설계를 동시에 개선한 새로운 QAOA 프레임워크를 제시했습니다.
2. 실현 가능성 병목 현상 해결: 실현 가능한 해가 희소하게 분포하는 문제에서, 초기 상태의 확률 분포를 실현 가능한 영역으로 편향시키고 진화 과정에서 구조를 보존함으로써 탐색 효율을 극대화했습니다.
3. 실용적인 타협점 도출: 완전한 실현 가능 부분 공간만 탐색하는 복잡한 방법 (Grover 믹서 등) 과 구조를 전혀 고려하지 않는 표준 QAOA 사이의 타협점을 제공하여, 현재 NISQ (Noisy Intermediate-Scale Quantum) 장치에서도 구현 가능한 수준의 복잡도를 유지했습니다.
4. 다양한 환경에서의 검증: 이상적인 상태 벡터 시뮬레이션, 유한 샷 (finite-shot) 샘플링, 그리고 노이즈가 포함된 유한 샷 환경 등 세 가지 시나리오에서 광범위한 실험을 수행했습니다.

4. 실험 결과 (Results)

논문은 3 노드 2 대 차량의 소규모 VRP 인스턴스를 사용하여 제안된 방법과 표준 QAOA 를 비교했습니다.

• 성능 지표: 최적 상태 확률 (Optimal-state probability), 기대 에너지 갭 (Expected energy gap), 샘플링 순위 (Sampling rank) 를 평가했습니다.
• 결과 요약:
  • 이상적 환경 (Regime I): 제안된 방법은 표준 QAOA 대비 최적 상태 확률이 약 0.6176 (표준은 0.5086) 으로 크게 향상되었으며, 기대 에너지 갭도 유의미하게 감소했습니다.
  • 유한 샷 환경 (Regime II): 측정 노이즈가 존재하는 상황에서도 제안된 방법이 일관되게 더 높은 최적 해 발견 확률과 더 낮은 비용 값을 보였습니다.
  • 노이즈 환경 (Regime III): 실제 하드웨어 수준의 게이트 및 판독 오류를 시뮬레이션한 환경에서는 두 방법 간의 격차가 줄어들었지만, 제안된 방법이 여전히 표준 QAOA 보다 우세한 성능을 유지했습니다.
• 파라미터 $\lambda$의 영향: 하이브리드 믹서의 가중치 $\lambda$가 너무 작으면 탐색이 제한되고, 너무 크면 초기화의 구조적 이점이 사라집니다. 실험 결과 $\lambda \approx 0.7 \sim 0.8$ 부근에서 최적의 성능을 발휘하는 비단조적 (non-monotonic) 패턴을 확인했습니다.

5. 의의 및 결론 (Significance)

• 알고리즘적 통찰: VRP 와 같은 제약 최적화 문제에서 '실현 가능성'은 단순한 모델링 세부 사항이 아니라 알고리즘 설계의 핵심 요소임을 강조했습니다.
• 하드웨어 발전과의 연계: 제안된 방법의 이점은 하드웨어의 노이즈가 감소할수록 더욱 커질 것으로 예상됩니다. 복잡한 회로 구조를 가진 믹서는 현재 하드웨어의 오류에 민감할 수 있으나, 양자 하드웨어의 정밀도가 향상되면 구조화된 믹서의 이점이 극대화될 것입니다.
• 미래 전망: 이 연구는 소규모 VRP 에서 유효함을 입증했으나, 향후 용량 제약 (CVRP), 시간 창 (VRPTW) 등 더 복잡한 변형 문제에 적용하고, 하드웨어 특유의 결합 맵 및 노이즈 모델을 고려한 최적화가 필요함을 지적했습니다.

결론적으로, 본 논문은 제약 조건을 알고리즘의 초기 단계와 진화 과정에 체계적으로 통합함으로써, 양자 최적화 알고리즘이 실제 물류 문제와 같은 복잡한 조합 최적화 문제에서 더 효과적으로 작동할 수 있는 길을 제시했습니다.