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} = i = 1 \sum n X_{i}$

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

QAOA 앤사츠

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

$∣ γ, β ⟩ = e^{- i β_{p} H_{B}} e^{- i γ_{p} H_{C}} \dots e^{- i β_{1} H_{B}} e^{- i γ_{1} H_{C}} ∣ s ⟩$

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

알고리즘의 목적은 기댓값

$F_{p} (γ, β) = ⟨ γ, β ∣ H_{C} ∣ γ, β ⟩$

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

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

$(γ, β)$ 초기화
양자 회로 실행 → $F_{p}$ 측정
고전 최적화기(COBYLA, L-BFGS-B 등)로 매개변수 갱신
수렴 조건 충족 시 종료; 미충족 시 2로 복귀

예시·응용

Max-Cut 문제

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

$H_{C}^{MC} = \frac{1}{2} (i, j) \in E \sum (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 등 기울기-자유 최적화기로 $(γ, β)$ 를 탐색한 뒤, 가장 높은 확률로 측정되는 비트열을 최적 절단 후보로 채택한다.

근사 비율

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

정리

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

Exercises

연습문제

Q13-노드 완전 그래프 $K_3$ (간선: (0,1), (1,2), (0,2))에 대한 Max-Cut 비용 해밀토니안 $H_C$를 파울리 연산자로 명시적으로 작성하라.
힌트 보기
각 간선 $(i,j)$마다 $\frac{1}{2}(I - Z_i Z_j)$ 항을 더한다. 3개의 간선이 있으므로 항도 3개가 생긴다.
해설 보기
$$H_C = \frac{1}{2}(I - Z_0 Z_1) + \frac{1}{2}(I - Z_1 Z_2) + \frac{1}{2}(I - Z_0 Z_2)$$ 최적 절단은 세 정점을 두 그룹으로 나눌 때 반드시 두 간선만 절단되므로(홀수 사이클), 최댓값은 2이다. 따라서 $H_C$의 최대 고유값은 2이며, 최적 비트열은 $|001\rangle, |010\rangle, |100\rangle, |011\rangle, |101\rangle, |110\rangle$ 중 2-간선 절단 해가 해당된다.
Q2QAOA에서 혼합 해밀토니안 $H_B = \sum_i X_i$의 역할을 설명하고, 이것이 없을 경우(즉, $H_B = 0$으로 설정할 경우) 알고리즘에 어떤 문제가 발생하는지 논하라.
해설 보기
$H_B$는 서로 다른 계산 기저 상태 사이의 전이(transition)를 생성하는 역할을 한다. $e^{-i\beta H_B}$는 각 큐비트에 $R_X(2\beta)$ 회전을 적용하여 상태를 중첩시키고, 해 공간 전체를 탐색할 수 있게 한다. 만약 $H_B = 0$이면 회로는 비용 층만으로 구성되고, 균등 중첩 초기 상태 $|s\rangle$에 대각 유니타리만 작용하므로 각 기저 상태의 확률 진폭 크기가 변하지 않는다(위상만 바뀜). 결과적으로 측정 확률 분포가 균등 분포에 머물러 최적화 효과가 전혀 없다.
Q3QAOA 층수 $p$를 늘릴 때 이론적으로 근사 품질이 향상됨에도 불구하고, 현재 NISQ 하드웨어에서 무작정 $p$를 크게 설정하기 어려운 이유를 두 가지 이상 제시하라.
해설 보기
①**회로 깊이와 노이즈**: $p$가 증가하면 게이트 수가 $O(p \cdot |E|)$로 증가하고, 현재 NISQ 장치의 게이트 오류율(~0.1–1%)과 결맞음 시간(decoherence time) 한계 내에서 신뢰도 있는 연산을 보장하기 어렵다. ②**매개변수 최적화 난이도**: 매개변수 공간이 $2p$ 차원으로 확장되면 바레인 고원(Barren Plateau) 현상이 심해져 기울기 기반 최적화기가 수렴하기 어렵다. ③**측정 횟수**: 기댓값 $F_p$ 추정에 필요한 샘플 수가 분산에 따라 많이 필요하므로 실험 시간이 대폭 증가한다.