QAOA: 조합 최적화를 위한 양자 근사 최적화 알고리즘

개념 소개

조합 최적화(combinatorial optimization)는 그래프 분할, 스케줄링, 포트폴리오 최적화 등 NP-난해 문제가 다수 포함된 광대한 분야다. QAOA는 이러한 이산 최적화 문제를 양자 회로로 근사 풀기 위해 제안된 변분(variational) 하이브리드 알고리즘이다. 양자 프로세서가 중첩 상태를 이용해 해 공간을 탐색하고, 고전 컴퓨터가 회로 파라미터를 반복적으로 갱신하는 협력 구조를 취한다.

---

핵심 원리

문제 인코딩: 비용 해밀토니안

이진 변수 $z_i\in \{0,1\}$로 표현되는 목적 함수 $C(z)$를 계산 기저(computational basis)에서 대각인 비용 해밀토니안(cost Hamiltonian) $H_C$로 매핑한다.

$$H_C|z⟩=C(z)|z⟩$$

이 대응 덕분에 $H_C$의 기저 상태를 측정할 때 확률이 높을수록 목적 함수 값이 좋은 해를 의미한다.

혼합 해밀토니안

해 공간 탐색은 혼합 해밀토니안(mixer Hamiltonian) $H_B$가 담당한다. 표준 선택은 각 큐비트에 파울리-$X$ 연산자를 적용하는 횡자기장 형태다.

$$H_B=\sum _{i=1}^n{X}_i$$

$H_B$는 서로 다른 계산 기저 상태 사이의 전이를 유도함으로써 알고리즘이 국소 최적해에 갇히지 않도록 돕는다.

QAOA 회로와 변분 파라미터

깊이(depth) $p$의 QAOA 회로는 균등 중첩 상태 $|+{⟩}^{\otimes n}$에서 출발해 비용 게이트와 혼합 게이트를 $p$회 교번 적용한다.

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

여기서 $\mathbf{\gamma }=({\gamma }_1,\dots ,{\gamma }_p)$, $\mathbf{\beta }=({\beta }_1,\dots ,{\beta }_p)$는 고전 옵티마이저가 조정하는 변분 파라미터다. 목적 함수는 기댓값

$$F_p(\mathbf{\gamma },\mathbf{\beta })=⟨\mathbf{\gamma },\mathbf{\beta }|H_C|\mathbf{\gamma },\mathbf{\beta }⟩$$

를 최대화(또는 최소화)하도록 설정한다. 이론적으로 $p\to \infty$ 극한에서 QAOA는 정확한 최적해에 수렴함이 보장되어 있다.

고전-양자 피드백 루프

1. 현재 파라미터 $(\mathbf{\gamma },\mathbf{\beta })$로 양자 회로를 실행해 $F_p$ 기댓값을 측정한다.
2. 고전 옵티마이저(COBYLA, SPSA, 경사 하강법 등)가 기댓값을 바탕으로 파라미터를 갱신한다.
3. 수렴 조건이 만족될 때까지 반복한다.

---

예시·응용

MaxCut 문제

MaxCut은 QAOA의 대표 벤치마크다. 그래프 $G=(V,E)$의 정점을 두 집합으로 나눌 때, 두 집합을 가로지르는 간선 수를 최대화하는 문제다. 비용 해밀토니안은

$$H_C=\frac{1}{2}\sum _{(i,j)\in E}(I-Z_i{Z}_j)$$

으로 표현된다. $Z_i{Z}_j=-1$이면 두 큐비트가 다른 집합에 속해 해당 간선이 잘린 것을 의미한다.

아래는 Qiskit을 이용한 4-노드 MaxCut QAOA의 개략적 구현이다.

import networkx as nx
from qiskit_optimization.applications import Maxcut
from qiskit_optimization.converters import QuadraticProgramToQubo
from qiskit_optimization.algorithms import MinimumEigenOptimizer
from qiskit_algorithms import QAOA
from qiskit_algorithms.optimizers import COBYLA
from qiskit.primitives import Sampler

G = nx.cycle_graph(4)                        # 4-노드 순환 그래프
qp = Maxcut(G).to_quadratic_program()
qubo = QuadraticProgramToQubo().convert(qp)

qaoa = QAOA(sampler=Sampler(),
            optimizer=COBYLA(maxiter=300),
            reps=2)                           # p = 2 레이어
result = MinimumEigenOptimizer(qaoa).solve(qubo)
print(result)

성능 보장과 한계

$p=1$ 단일 레이어 QAOA는 MaxCut에 대해 근사비(approximation ratio) $\ge 0.6924$임이 이론적으로 알려져 있다. 그러나 $p$가 커질수록 파라미터 최적화의 경관(landscape)이 평탄해지는 배럿 플래토(barren plateau) 문제와 노이즈 누적이 실질적인 장벽이 된다. NISQ 환경에서의 실제 양자 이점 존재 여부는 현재도 활발히 연구 중인 열린 문제다.

---

정리

QAOA는 비용 해밀토니안과 혼합 해밀토니안을 교번 적용하는 $p$-레이어 변분 회로를 핵심 구조로 삼는 하이브리드 최적화 알고리즘이다. 회로 깊이 $p$가 커질수록 이론적 근사 품질이 향상되지만, 노이즈와 최적화 비용도 함께 증가한다. MaxCut을 비롯한 이산 최적화 문제에서 NISQ 시대의 실용적 알고리즘 후보로 평가받으며, 혼합 해밀토니안 설계·파라미터 초기화 전략·오류 경감 기법 등이 현재의 핵심 연구 과제다.