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

개념 소개

조합 최적화 문제는 유한한 이진 변수들의 조합에서 특정 목적 함수를 최대화(혹은 최소화)하는 해를 찾는 문제다. 대표적으로 MaxCut, 외판원 문제(TSP), 포트폴리오 최적화 등이 있으며, 일반적으로 NP-난해 복잡도 클래스에 속한다.

고전 컴퓨터에서는 문제 크기가 커질수록 탐색 공간이 지수적으로 증가해 정확한 풀이가 어렵다. QAOA는 이 탐색 공간을 양자 중첩으로 동시에 탐색하고, 변분 최적화로 좋은 근사해를 이끌어내는 하이브리드 양자-고전 알고리즘이다.

QAOA는 Edward Farhi 등이 2014년에 제안했으며, 변분 양자 고유값 분해기(VQE)와 함께 NISQ 장치에 적합한 알고리즘으로 분류된다.

---

핵심 원리

문제의 해밀토니안 인코딩

$n$개의 이진 변수 $z_i\in \{0,1\}$로 표현되는 비용 함수 $C(z)$를 파울리 $Z$ 연산자로 인코딩한다.

$$\hat{C}=\sum _{\alpha }{w}_{\alpha }\prod _{j\in \alpha }{Z}_j$$

각 큐비트의 $|0⟩$, $|1⟩$ 상태가 이진 변수 값 0, 1에 대응된다.

혼합 해밀토니안

탐색 공간 전체를 순회하도록 혼합 해밀토니안(Mixer Hamiltonian) $\hat{B}$를 정의한다. 표준 형태는:

$$\hat{B}=\sum _{j=1}^n{X}_j$$

$X_j$는 $j$번째 큐비트에 작용하는 파울리 $X$ 연산자다.

QAOA 변분 상태

깊이 $p$의 QAOA 상태는 비용 유니터리 $U_C$와 혼합 유니터리 $U_B$를 교대로 적용해 구성한다.

$$|\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\hat{C}},U_B({\beta }_k)=e^{-i{\beta }_k\hat{B}}$$

초기 상태 ${|+⟩}^{\otimes n}$은 모든 비트 문자열에 대한 균등 중첩이다.

변분 최적화 루프

양자 장치에서 기댓값 $⟨\hat{C}⟩$를 측정하고, 고전 최적화기(COBYLA, L-BFGS-B 등)가 파라미터 $(\mathbf{\gamma },\mathbf{\beta })$를 갱신한다.

$$({\mathbf{\gamma }}^{\ast },{\mathbf{\beta }}^{\ast })=\arg \underset{\mathbf{\gamma },\mathbf{\beta }}{\max }⟨\mathbf{\gamma },\mathbf{\beta }|\hat{C}|\mathbf{\gamma },\mathbf{\beta }⟩$$

최적화가 수렴하면 최종 상태를 측정해 근사 최적 비트 문자열을 얻는다.

성능 보장

$p\to \infty$ 극한에서 QAOA는 정확한 최적해로 수렴함이 증명되어 있다. $p=1$인 MaxCut 문제에서는 근사비(approximation ratio) $\ge 0.6924$가 보장된다. 단, 회로 깊이가 증가할수록 NISQ 장치에서의 노이즈 영향도 커진다.

---

예시·응용

MaxCut 문제

그래프 $G=(V,E)$에서 정점을 두 집합으로 분할했을 때 절단되는 간선 수를 최대화하는 문제다. 비용 해밀토니안:

$${\hat{C}}_{\text{MaxCut}}=\frac{1}{2}\sum _{(i,j)\in E}(1-Z_i{Z}_j)$$

Qiskit을 이용한 QAOA 구현 예시

from qiskit_algorithms import QAOA
from qiskit_algorithms.optimizers import COBYLA
from qiskit.primitives import Sampler
from qiskit_optimization import QuadraticProgram
from qiskit_optimization.algorithms import MinimumEigenOptimizer
from qiskit_optimization.converters import QuadraticProgramToQubo

# MaxCut 문제 정의 (4-정점 그래프)
qp = QuadraticProgram()
for i in range(4):
    qp.binary_var(f'x{i}')

# 간선 (0,1), (1,2), (2,3), (3,0) 정의
edges = [(0,1),(1,2),(2,3),(3,0)]
linear = {f'x{i}': 0 for i in range(4)}
quadratic = {(f'x{u}', f'x{v}'): -1 for u, v in edges}
qp.maximize(linear=linear, quadratic=quadratic)

# QUBO 변환 및 QAOA 실행
converter = QuadraticProgramToQubo()
qubo = converter.convert(qp)

qaoa = QAOA(sampler=Sampler(), optimizer=COBYLA(), reps=2)
optimizer = MinimumEigenOptimizer(qaoa)
result = optimizer.solve(qubo)
print("최적 비트 문자열:", result.x)
print("목적 함수값:", result.fval)

주요 응용 분야

분야	문제 예시
물류	차량 경로 최적화(VRP)
금융	포트폴리오 선택, 위험 분산
통신	네트워크 채널 할당
화학	분자 구조 최적화

---

정리

QAOA는 비용 해밀토니안과 혼합 해밀토니안의 교대 적용이라는 단순한 구조 위에서, 변분 파라미터 최적화를 통해 조합 최적화 문제의 근사해를 탐색한다. 회로 깊이 $p$는 해의 품질과 하드웨어 요구 사이의 트레이드오프를 결정한다. 현재는 $p$가 작은 NISQ 환경에서의 실용적 이점 입증이 주요 연구 과제로 남아 있으며, 문제 구조를 반영한 혼합기 설계, 파라미터 초기화 전략 등이 활발히 개발되고 있다.