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

개념 소개

조합 최적화 문제는 유한한 이산 해 공간에서 목적 함수를 극대화·극소화하는 해를 찾는 문제다. 최대 절단(Max-Cut), 외판원 문제(TSP), 포트폴리오 최적화 등 많은 실용 사례가 NP-난해 복잡도 클래스에 속하며, 변수 수가 증가할수록 고전 컴퓨터로는 정확한 해를 구하기 어렵다.

QAOA는 이러한 문제를 양자컴퓨터로 근사적으로 푸는 변분(variational) 알고리즘이다. 매개변수화된 양자 회로가 후보 상태를 준비하고, 고전 최적화기가 측정된 기댓값을 기반으로 매개변수를 갱신하는 하이브리드 루프를 반복한다. NISQ 시대에 현실적으로 실행 가능한 알고리즘으로 주목받고 있다.

---

핵심 원리

문제의 해밀토니안 인코딩

조합 최적화 문제는 $n$-큐비트 계의 비용 해밀토니안(Cost Hamiltonian) $H_C$로 인코딩된다. 비트열 $z\in \{0,1{\}}^n$에 대한 목적 함수값 $C(z)$가 $H_C$의 고유값이 되도록, 대부분 파울리 $Z$ 연산자의 텐서곱 형태로 구성한다.

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

혼합 해밀토니안

해 공간 전체를 균등하게 탐색하기 위한 **혼합 해밀토니안(Mixer Hamiltonian)**은 표준적으로 다음과 같이 정의된다.

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

$H_B$는 기저 상태 간 전이를 생성하여 최적화가 국소 최솟값에 갇히는 것을 방지한다.

QAOA 앤사츠

깊이 $p$의 QAOA 상태는 비용 층과 혼합 층을 교대로 $p$회 적용하여 만든다.

$$|\vec{\gamma },\vec{\beta }⟩=e^{-i{\beta }_p{H}_B}{e}^{-i{\gamma }_p{H}_C}\cdots e^{-i{\beta }_1{H}_B}{e}^{-i{\gamma }_1{H}_C}|s⟩$$

여기서 $|s⟩=H^{\otimes n}|0{⟩}^{\otimes n}$은 균등 중첩 초기 상태이며, $\vec{\gamma },\vec{\beta }\in {\mathbb{R}}^p$는 학습 가능한 실수 매개변수 벡터다.

알고리즘의 목적은 기댓값

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

을 최대화하는 최적 매개변수 $({\vec{\gamma }}^{\ast },{\vec{\beta }}^{\ast })$를 찾는 것이다. $p\to \infty$ 극한에서 정확한 최적해로 수렴함이 이론적으로 보장된다.

고전-양자 하이브리드 루프

1. $(\vec{\gamma },\vec{\beta })$ 초기화
2. 양자 회로 실행 → $F_p$ 측정
3. 고전 최적화기(COBYLA, L-BFGS-B 등)로 매개변수 갱신
4. 수렴 조건 충족 시 종료; 미충족 시 2로 복귀

---

예시·응용

Max-Cut 문제

그래프 $G=(V,E)$의 정점 집합을 두 그룹으로 분할할 때 그룹 간 간선 수를 최대화하는 문제다. 비용 해밀토니안은 다음과 같이 표현된다.

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

간선으로 연결된 두 큐비트가 서로 다른 상태($|01⟩$ 또는 $|10⟩$)일 때 기여값 1을 얻는 구조다.

Qiskit 구현 예시 ($p=1$, 3-노드 그래프)

from qiskit import QuantumCircuit
from qiskit.circuit import ParameterVector

n = 3
edges = [(0, 1), (1, 2)]

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

qc = QuantumCircuit(n)

# 초기 균등 중첩 상태
qc.h(range(n))

# Cost layer: e^{-i γ H_C}
for (i, j) in edges:
    qc.cx(i, j)
    qc.rz(2 * gamma[0], j)
    qc.cx(i, j)

# Mixer layer: e^{-i β H_B}
for i in range(n):
    qc.rx(2 * beta[0], i)

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

COBYLA 등 기울기-자유 최적화기로 $(\gamma ,\beta )$를 탐색한 뒤, 가장 높은 확률로 측정되는 비트열을 최적 절단 후보로 채택한다.

근사 비율

$p=1$ QAOA는 3-정규 그래프 Max-Cut에 대해 근사 비율 0.6924 이상을 이론적으로 보장한다. $p$ 증가에 따라 이 비율은 단조 향상된다.

---

정리

QAOA는 조합 최적화 문제를 양자 해밀토니안으로 인코딩하고, 비용·혼합 층을 교대로 적용하는 $p$-층 변분 회로를 통해 근사해를 탐색한다. 층수 $p$가 클수록 해의 질이 향상되지만 회로 깊이도 커지므로, 현재 NISQ 하드웨어의 노이즈 한계 안에서 최적 $p$를 선택하는 것이 실용적 핵심 과제다. 고전 최적화기와의 하이브리드 구조 덕분에 QAOA는 근미래 양자 하드웨어에서 가장 유력한 응용 경로 중 하나로 자리매김하고 있다.