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

먼저 읽으면 좋은 용어

개념 소개

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

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

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

핵심 원리

문제의 해밀토니안 인코딩

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

$\hat{C} = α \sum w_{α} j \in α \prod Z_{j}$

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

혼합 해밀토니안

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

$\hat{B} = j = 1 \sum n X_{j}$

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

QAOA 변분 상태

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

$∣ γ, β ⟩ = U_{B} (β_{p}) U_{C} (γ_{p}) \dots U_{B} (β_{1}) U_{C} (γ_{1}) ∣ + ⟩^{\otimes n}$

여기서:

$U_{C} (γ_{k}) = e^{- i γ_{k} \hat{C}}, U_{B} (β_{k}) = e^{- i β_{k} \hat{B}}$

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

변분 최적화 루프

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

$(γ^{*}, β^{*}) = ar g γ, β max ⟨ γ, β ∣ \hat{C} ∣ γ, β ⟩$

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

성능 보장

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

예시·응용

MaxCut 문제

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

$\hat{C}_{MaxCut} = \frac{1}{2} (i, j) \in E \sum (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 환경에서의 실용적 이점 입증이 주요 연구 과제로 남아 있으며, 문제 구조를 반영한 혼합기 설계, 파라미터 초기화 전략 등이 활발히 개발되고 있다.

Exercises

연습문제

Q14개 정점과 4개 간선(사이클 그래프 $C_4$)으로 이루어진 MaxCut 문제를 QAOA로 풀 때, $p=1$에서의 비용 해밀토니안 $\hat{C}$를 파울리 연산자로 명시적으로 표현하라.
힌트 보기
각 간선 $(i,j)$에 대해 $\frac{1}{2}(1 - Z_i Z_j)$ 항이 생성된다. 간선이 4개이므로 항도 4개다.
해설 보기
간선 집합 $E = \{(0,1),(1,2),(2,3),(3,0)\}$에 대해 $\hat{C} = \frac{1}{2}[(1-Z_0Z_1)+(1-Z_1Z_2)+(1-Z_2Z_3)+(1-Z_3Z_0)]$이다. 이를 전개하면 $\hat{C} = 2\,I - \frac{1}{2}(Z_0Z_1 + Z_1Z_2 + Z_2Z_3 + Z_3Z_0)$으로 쓸 수 있다.
Q2QAOA에서 혼합 해밀토니안 $\hat{B} = \sum_j X_j$를 선택하는 이유를 대칭성과 탐색 관점에서 설명하라.
해설 보기
$X_j$ 연산자는 큐비트 $j$를 $\ket{0} \leftrightarrow \ket{1}$ 사이에서 전환시켜 인접한 비트 문자열 간의 전이를 가능하게 한다. 균등 중첩 $\ket{+}^{\otimes n}$은 $\hat{B}$의 최대 고유값에 대응하는 고유상태이므로, 이 상태로 초기화하면 모든 해 공간에 동등하게 접근할 수 있다. 또한 $\hat{B}$는 비트 치환 대칭(permutation symmetry)을 가져 초기 상태와 비용 함수 구조에 bias를 주지 않는 중립적 탐색자 역할을 한다.
Q3회로 깊이 $p$를 두 배로 늘리면 파라미터의 수는 어떻게 변하며, 이것이 고전 최적화 단계에 미치는 영향을 설명하라.
해설 보기
깊이 $p$에서 파라미터는 $\boldsymbol{\gamma} = (\gamma_1,\ldots,\gamma_p)$와 $\boldsymbol{\beta} = (\beta_1,\ldots,\beta_p)$로 총 $2p$개다. $p$를 두 배로 늘리면 파라미터 수도 두 배인 $4p$개가 된다. 파라미터 공간의 차원이 증가하므로 고전 최적화기의 탐색 비용이 증가하고, 바렌 플래토(Barren Plateau) 현상 — 그래디언트가 지수적으로 소멸하는 현상 — 이 심화될 수 있다. 따라서 좋은 초기화 전략(예: warm-starting, 재귀적 파라미터 전달)이 중요해진다.