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

개념 소개

조합 최적화란 유한한 이산 공간에서 목적 함수를 최대화·최소화하는 해를 찾는 문제다. MaxCut, 외판원 문제(TSP), 그래프 색칠 등이 대표적이며, 변수 수가 늘어날수록 탐색 공간이 지수적으로 증가해 고전 알고리즘에 한계가 생긴다.

QAOA는 2014년 Farhi, Goldstone, Gutmann이 제안한 알고리즘으로, 변분 양자 고유값 분해기(VQE)의 아이디어를 조합 최적화에 특화한 형태다. 핵심 아이디어는 다음과 같다.

문제의 비용 함수를 양자 해밀토니안 $\hat{C}$로 인코딩하고, 파라미터화된 양자 회로 $U(\mathbf{\gamma },\mathbf{\beta })$로 바닥 상태를 근사 준비한 뒤, 기댓값 $⟨\hat{C}⟩$을 고전 최적화기로 최대화한다.

---

핵심 원리

문제 해밀토니안 인코딩

$n$개의 이진 변수 $z_i\in \{0,1\}$로 정의된 목적 함수 $C(\mathbf{z})$를 파울리-Z 연산자로 치환한다. 예를 들어 MaxCut 문제의 에지 $(i,j)$에 대해

$$\hat{C}=\frac{1}{2}\sum _{(i,j)\in E}\left(1-{\hat{Z}}_i{\hat{Z}}_j\right)$$

이 해밀토니안의 최대 고유값에 해당하는 고유벡터가 곧 최적 절단(cut)이다.

믹서 해밀토니안

탐색 공간 전역을 넘나들기 위한 믹서(mixer)로 통상 횡자기장 항을 사용한다.

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

이 연산자는 각 큐비트를 $|0⟩\leftrightarrow |1⟩$ 방향으로 회전시켜 탐색 다양성을 보장한다.

QAOA 회로 구조 (깊이 $p$)

초기 상태 $|s⟩=H^{\otimes n}|0{⟩}^{\otimes n}$(균등 중첩)에서 출발하여 두 유니타리를 $p$회 교대 적용한다.

$$|\mathbf{\gamma },\mathbf{\beta }⟩=\prod _{k=1}^p{e}^{-i{\beta }_k\hat{B}}{e}^{-i{\gamma }_k\hat{C}}|s⟩$$

파라미터 벡터 $\mathbf{\gamma }=({\gamma }_1,\dots ,{\gamma }_p)$, $\mathbf{\beta }=({\beta }_1,\dots ,{\beta }_p)$는 고전 최적화기(COBYLA, BFGS, Adam 등)로 갱신된다.

$$\underset{\mathbf{\gamma },\mathbf{\beta }}{\mathrm{argmax}}⟨\mathbf{\gamma },\mathbf{\beta }|\hat{C}|\mathbf{\gamma },\mathbf{\beta }⟩$$

$p=1$은 가장 얕은 근사이며, $p\to \infty$ 극한에서 단열 양자 계산(AQC)과 동치가 됨이 증명되어 있다.

게이트 분해

$e^{-i\gamma \hat{C}}$는 각 에지 항이 교환 가능하면 CNOT + RZ 게이트 쌍으로 컴파일된다.

$$e^{-i\gamma {\hat{Z}}_i{\hat{Z}}_j/2}⟶{\text{CNOT}}_{i\to j}\cdot R_Z(2\gamma {)}_j\cdot {\text{CNOT}}_{i\to j}$$

$e^{-i\beta \hat{B}}$는 각 큐비트에 독립적인 $R_X(2\beta )$ 게이트로 분해된다.

---

예시·응용

MaxCut 예제 (4노드 그래프, $p=1$)

from qiskit import QuantumCircuit
from qiskit.circuit import ParameterVector
import numpy as np

# 그래프 에지: (0,1), (1,2), (2,3), (3,0)
edges = [(0,1),(1,2),(2,3),(3,0)]
n = 4

gamma = ParameterVector('γ', 1)
beta  = ParameterVector('β', 1)

qc = QuantumCircuit(n)
qc.h(range(n))                          # 균등 중첩

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

# 믹서 유니타리
for i in range(n):
    qc.rx(2 * beta[0], i)

qc.measure_all()
print(qc.draw('text'))

고전 최적화 루프 (Qiskit Estimator 기반)

from scipy.optimize import minimize
from qiskit.primitives import StatevectorEstimator
from qiskit.quantum_info import SparsePauliOp

# MaxCut 해밀토니안 (4노드 링 그래프)
terms = ['ZZII','IZZI','IIZZ','ZIIZ']
coeffs = [-0.5] * 4
cost_op = SparsePauliOp(terms, coeffs=coeffs) + SparsePauliOp('IIII', coeffs=[2.0])

estimator = StatevectorEstimator()

def objective(params):
    g, b = params[0], params[1]
    bound = qc.assign_parameters({gamma[0]: g, beta[0]: b})
    job = estimator.run([(bound, cost_op)])
    return -job.result()[0].data.evs   # 최대화 → 부호 반전

result = minimize(objective, x0=[0.5, 0.5], method='COBYLA')
print(f"최적 파라미터: γ={result.x[0]:.4f}, β={result.x[1]:.4f}")
print(f"근사 MaxCut 값: {-result.fun:.4f}")

실용적 고려 사항

항목	내용
회로 깊이	현재 NISQ 장치에서 $p\le 3$ 수준이 현실적
노이즈 민감도	깊이 증가 시 오류 누적 → 오류 경감 기법 병행 필요
파라미터 초기화	무작위 초기화보다 단열 경로 기반 휴리스틱이 수렴 가속
고전 최적화기	바리언스가 큰 기울기 소실(Barren Plateau)에 주의

---

정리

QAOA는 이산 최적화 문제를 양자-고전 하이브리드 루프로 다루는 가장 체계화된 알고리즘 중 하나다. 회로 구조가 문제의 그래프 구조를 직접 반영하며, 레이어 수 $p$가 정밀도와 회로 복잡도 사이의 핵심 트레이드오프를 결정한다. NISQ 시대에는 얕은 깊이의 $p=1,2$ 설정과 오류 경감 기법의 조합이 현실적 선택이다. 장기적으로는 오류 정정이 가능한 하드웨어에서 $p$를 충분히 키워 양자 우위를 달성하는 방향이 탐구되고 있다.