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

개념 소개

QAOA는 조합 최적화 문제를 이징(Ising) 해밀토니언으로 인코딩한 뒤, 파라미터화된 양자 회로로 바닥 상태(또는 고에너지 상태)를 근사 탐색하는 변분 알고리즘이다. 순회판매원 문제, 최대 컷(MaxCut), 그래프 색칠 등 광범위한 NP-난해 문제를 대상으로 한다.

알고리즘 구조는 두 요소로 이루어진다.

• 비용 해밀토니언 $H_C$: 풀고자 하는 목적함수를 $Z$ 연산자의 다항식으로 인코딩
• 믹서 해밀토니언 $H_B$: 해 공간 탐색을 위해 횡방향 자기장 역할을 수행

이 두 해밀토니언이 교대로 적용되는 양자 아디아바틱 발전(adiabatic evolution)의 트로터(Trotter) 근사로 이해할 수 있다.

---

핵심 원리

회로 구조

$n$큐비트를 균등 중첩 상태로 초기화한 뒤, $p$ 레이어만큼 비용·믹서 유니터리를 교대 적용한다.

$$|\mathbf{\gamma },\mathbf{\beta }⟩=U_B({\beta }_p)U_C({\gamma }_p)\cdots U_B({\beta }_1)U_C({\gamma }_1)|+{⟩}^{\otimes n}$$

각 유니터리는 해밀토니언의 시간 발전 연산자다.

$$U_C({\gamma }_k)=e^{-i{\gamma }_k{H}_C},U_B({\beta }_k)=e^{-i{\beta }_k{H}_B}$$

MaxCut 문제 인코딩

그래프 $G=(V,E)$의 MaxCut 비용 해밀토니언은

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

으로 정의된다. 인접 큐비트 스핀이 반대이면 $Z_i{Z}_j=-1$이므로 에너지 기여가 최대가 된다. 표준 믹서는

$$H_B=\sum _{i\in V}{X}_i$$

이며, $U_C$는 CNOT + $R_z$ 조합으로, $U_B$는 $R_x$ 게이트 층으로 구현된다.

고전 최적화 루프

파라미터 벡터 $(\mathbf{\gamma },\mathbf{\beta })\in {\mathbb{R}}^{2p}$에 대해 기댓값

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

을 최대화한다. 양자 장치에서 기댓값을 측정한 결과를 COBYLA, BFGS, 혹은 **파라미터 이동 규칙(parameter-shift rule)**을 활용한 해석적 경사도 기반 최적화기에 피드백한다.

$$\frac{\partial F}{\partial {\gamma }_k}=\frac{1}{2}[F({\gamma }_k+\frac{\pi }{2})-F({\gamma }_k-\frac{\pi }{2})]$$

근사비 보장

$p=1$ 단층 QAOA는 MaxCut에서 이론적 근사비 $\alpha \ge 0.6924$를 보장하며, 이는 고전 랜덤 2-분할 알고리즘의 $0.5$를 상회한다.

---

예시·응용

Qiskit 구현: 3-노드 삼각형 그래프

from qiskit.circuit import QuantumCircuit, Parameter
import numpy as np

gamma = Parameter('γ')
beta  = Parameter('β')

qc = QuantumCircuit(3)

# 초기 균등 중첩
qc.h([0, 1, 2])

# 비용 유니터리: 엣지 (0,1), (1,2), (0,2)
for i, j in [(0, 1), (1, 2), (0, 2)]:
    qc.cx(i, j)
    qc.rz(2 * gamma, j)
    qc.cx(i, j)

# 믹서 유니터리
qc.rx(2 * beta, [0, 1, 2])
qc.measure_all()

print(qc.draw('text'))

삼각형 그래프(홀수 사이클)의 최대 컷은 2이며, 최적 파라미터 근방에서 001, 010, 100, 011, 101, 110 등 비트 반전 쌍이 두드러진다.

실용 응용 분야

분야	대표 문제
금융	포트폴리오 최적화, 위험 분산
물류	경로 탐색, 작업 스케줄링
소재	분자 배치 최적화
통신	주파수 할당, 네트워크 라우팅

QAOA vs VQE 비교

두 알고리즘 모두 변분 원리를 공유하지만, QAOA는 이산 조합 문제에, VQE는 연속 에너지 최소화(분자 해밀토니언 등)에 주로 적용된다. QAOA 회로 구조는 문제에 의해 고정되는 반면, VQE는 임의 앤사츠(ansatz)를 허용한다.

---

정리

QAOA는 파라미터화 양자 회로와 고전 최적화기를 결합하여 NISQ 시대 조합 최적화에 접근하는 핵심 알고리즘이다. 레이어 수 $p$ 증가에 따라 근사 품질이 향상되나 회로 깊이도 커지므로, 하드웨어 노이즈와의 균형이 실제 구현에서 가장 중요한 과제다. 내결함성 양자 장치가 성숙하면 고전 솔버 대비 양자 우위가 본격적으로 검증될 전망이다.