양자 근사 최적화 알고리즘 (QAOA)

직관적 비유

복잡한 산악 지형에서 가장 낮은 계곡을 찾는 등산가를 상상해 보자. 고전 알고리즘이 한 발씩 내딛으며 탐색하는 것과 달리, QAOA는 양자 중첩으로 수많은 경로를 동시에 탐색하고, 간섭 효과를 통해 좋은 해 쪽으로 확률 진폭을 집중시킨다.

엄밀한 정의

QAOA는 깊이 $p$의 매개변수화된 양자 회로를 사용한다. 문제 해밀토니언 $H_C$와 혼합 해밀토니언 $H_B={\sum }_i{X}_i$를 교대로 적용하여 상태를 구성한다:

$$|\mathbf{\gamma },\mathbf{\beta }⟩=\prod _{k=1}^p{e}^{-i{\beta }_k{H}_B}{e}^{-i{\gamma }_k{H}_C}|+{⟩}^{\otimes n}$$

고전 최적화기가 기댓값 $⟨H_C⟩$를 최소화하도록 매개변수 $(\mathbf{\gamma },\mathbf{\beta })$를 반복 갱신한다. $p\to \infty$ 극한에서는 양자 단열 정리에 의해 정확한 최적해로 수렴함이 보장된다.

중요성 및 응용

2014년 Farhi, Goldstone, Gutmann이 제안한 QAOA는 NISQ 시대를 대표하는 알고리즘으로, 오류 보정 없이도 현재 양자 하드웨어에서 실행 가능하다. Max-Cut, 그래프 색칠, 포트폴리오 최적화, 물류 스케줄링 등 NP-난해 조합 최적화 문제에 폭넓게 적용되며, 변분 양자 알고리즘(VQA) 계열의 핵심 사례로 꼽힌다.