양자 근사 최적화 알고리즘

직관적 비유

복잡한 산악 지형에서 가장 낮은 골짜기(최적해)를 찾는 탐색에 비유할 수 있다. 양자 중첩으로 여러 경로를 동시에 탐색하고, 간섭 효과로 좋은 해의 확률 진폭을 강화하면서 나쁜 해를 억제한다.

엄밀한 정의

깊이 $p$의 양자 회로에서 문제 해밀토니안 $H_C$와 혼합 해밀토니안 $H_B$를 교대 적용한다. $$|\mathbf{\gamma },\mathbf{\beta }⟩=e^{-i{\beta }_p{H}_B}{e}^{-i{\gamma }_p{H}_C}\cdots e^{-i{\beta }_1{H}_B}{e}^{-i{\gamma }_1{H}_C}|+{⟩}^{\otimes n}$$ 고전 최적화기가 파라미터 $(\mathbf{\gamma },\mathbf{\beta })$를 조정하여 기댓값 $⟨H_C⟩$를 최소화한다. $p\to \infty$ 극한에서 정확한 최적해로 수렴함이 이론적으로 보장된다.

중요성·응용

Max-Cut, 스케줄링, 외판원 문제 등 NP-난해 조합 최적화에 적용 가능하며, NISQ 시대의 대표적 응용 알고리즘으로 주목받는다. 물류 최적화·금융 포트폴리오 최적화 등 산업 분야 연구도 활발히 진행 중이다.