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

먼저 읽으면 좋은 용어

개념 소개

조합 최적화(combinatorial optimization)는 이산적인 변수 집합에서 목적 함수를 최대·최소화하는 문제로, 그래프 최대 절단(MaxCut), 외판원 문제(TSP), 스케줄링 등 NP-난해(NP-hard) 문제를 다수 포함한다. 고전 알고리즘은 최악의 경우 탐색 공간이 지수적으로 증가한다.

QAOA는 Farhi, Goldstone, Gutmann이 제안한 알고리즘으로, 변분 양자 고유값 분해기(VQE)와 유사한 하이브리드 구조를 가진다. 핵심 아이디어는 문제를 양자 해밀토니안으로 인코딩하고, 파라미터화된 양자 회로를 통해 그 기저 상태(또는 저에너지 상태)를 근사적으로 탐색하는 것이다. 이 구조는 양자 단열 계산(quantum adiabatic computation)에서 직접적인 영감을 받았다.

핵심 원리

문제 인코딩

$n$ 개의 이진 변수 $z_{i} \in {0, 1}$ 로 표현되는 조합 최적화 문제를 파울리 Z 연산자 $\hat{Z}_{i}$ 를 이용해 비용 해밀토니안 $H_{C}$ 로 변환한다. MaxCut 문제에서 그래프 $G = (V, E)$ 의 비용 해밀토니안은 다음과 같이 쓴다:

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

$H_{C}$ 의 최대 고유값에 대응하는 고유 상태가 최적 분할을 나타낸다.

QAOA 안사츠(Ansatz)

깊이(depth) $p$ 를 가지는 파라미터화된 회로를 구성한다. 초기 상태로 균등 중첩 상태 $∣ + ⟩^{\otimes n}$ 를 준비한 뒤, 비용 유니타리 $U_{C} (γ_{k})$ 와 혼합 유니타리 $U_{B} (β_{k})$ 를 $p$ 회 교대 적용한다:

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

각 유니타리는 해밀토니안의 시간 발전으로 정의된다:

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

혼합 해밀토니안 $H_{B} = \sum_{i = 1}^{n} \hat{X}_{i}$ 는 모든 큐비트에 파울리 X를 적용하여 탐색 공간을 고르게 탐색하는 역할을 한다.

고전-양자 하이브리드 최적화

파라미터 $γ = (γ_{1}, \dots, γ_{p})$ , $β = (β_{1}, \dots, β_{p})$ 를 고전 최적화기(COBYLA, BFGS 등)로 반복 갱신하여 기댓값

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

를 최대화한다. $p \to \infty$ 극한에서 정확한 최적해에 수렴함이 이론적으로 보장된다.

예시·응용

MaxCut: 3-노드 삼각 그래프

노드 ${0, 1, 2}$ , 에지 ${(0, 1), (1, 2), (0, 2)}$ 의 삼각 그래프에서 $p = 1$ QAOA를 Qiskit으로 구성하는 예시이다.

from qiskit import QuantumCircuit
import numpy as np
from scipy.optimize import minimize

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

def build_qaoa(params):
    gamma, beta = params
    qc = QuantumCircuit(n)
    qc.h(range(n))                      # 균등 중첩 초기화
    # 비용 유니타리 U_C(gamma)
    for (i, j) in edges:
        qc.cx(i, j)
        qc.rz(2 * gamma, j)
        qc.cx(i, j)
    # 혼합 유니타리 U_B(beta)
    for q in range(n):
        qc.rx(2 * beta, q)
    return qc

# 고전 최적화기로 파라미터 탐색 (시뮬레이터 기댓값 함수 가정)
result = minimize(lambda p: -expectation_value(build_qaoa(p)),
                  x0=[0.5, 0.5], method='COBYLA')
print("최적 파라미터 γ, β:", result.x)

$p = 1$ 에서 MaxCut 근사비(approximation ratio)는 이론적으로 $\geq 0.6924$ 임이 증명되어 있다.

실용적 고려 사항

깊이 $p$ 와 성능: $p$ 가 클수록 근사비가 향상되나, 회로 깊이 증가로 NISQ 소자의 노이즈가 누적된다.
바렌 플래토(Barren Plateau): 파라미터 공간이 커질수록 기울기 소실이 발생해 최적화가 어려워진다. 레이어별 훈련(LAYER-BY-LAYER) 등의 완화 전략이 연구되고 있다.
QUBO 변환: 등호·부등호 제약 조건이 있는 문제는 패널티 항을 추가하여 비제약 이진 이차 최적화(QUBO) 형태로 변환한 뒤 인코딩한다.
응용 분야: 금융 포트폴리오 최적화, 물류 라우팅, 머신러닝 훈련, 분자 구조 최적화 등.

정리

QAOA는 비용 해밀토니안과 혼합 해밀토니안의 교대 적용이라는 단순한 구조로 NP-난해 조합 최적화 문제에 접근하는 알고리즘이다. 깊이 $p$ 를 늘릴수록 이론적 성능이 단조 향상되며, 고전-양자 하이브리드 루프를 통해 현재 NISQ 소자에서 실행 가능하다. 다만 바렌 플래토, 노이즈 민감성, 고전 최적화의 비볼록성 등 해결해야 할 과제가 남아 있으며, 이를 극복하기 위한 변형 알고리즘(ADAPT-QAOA, recursive QAOA 등)이 활발히 연구되고 있다.

Exercises

연습문제

Q1에지 집합이 $\{(0,1),(1,2)\}$인 경로 그래프(노드 3개)에 대해 MaxCut 비용 해밀토니안 $H_C$를 파울리 연산자로 명시적으로 작성하라.
힌트 보기
각 에지 $(i,j)$에 대해 $\frac{1}{2}(I - \hat{Z}_i\hat{Z}_j)$ 항을 합산한다. 에지가 2개이므로 항도 2개이다.
해설 보기
$$H_C = \frac{1}{2}(I - \hat{Z}_0\hat{Z}_1) + \frac{1}{2}(I - \hat{Z}_1\hat{Z}_2)$$ 전체 3-큐비트 연산자로 쓰면 각 항의 나머지 큐비트에 항등 연산자 $I$를 텐서곱한다. 최적해는 $|010\rangle$ 또는 $|101\rangle$로, 절단 수 2를 달성한다.
Q2QAOA 회로에서 혼합 해밀토니안 $H_B = \sum_i \hat{X}_i$가 필요한 이유를 양자 단열 계산의 관점에서 설명하라.
해설 보기
양자 단열 계산에서는 쉽게 준비할 수 있는 초기 해밀토니안(통상 $H_B$)에서 출발하여 서서히 목적 해밀토니안($H_C$)으로 변환한다. QAOA는 이 단열 경로를 유한한 $p$단계로 트로터(Trotter) 근사한 것이다. $H_B$는 $|+\rangle^{\otimes n}$ 상태를 기저 상태로 가지며, 탐색 공간 전체를 고르게 혼합(mixing)하는 역할을 함으로써 국소 최솟값 함정에서 탈출하는 구동력을 제공한다.
Q3동일한 조합 최적화 문제에 대해 QAOA 깊이 $p$를 1에서 5로 늘렸을 때 기대할 수 있는 장점과 단점을 각각 두 가지씩 서술하라.
해설 보기
**장점** ① 표현력이 증가하여 더 정확한 최적해에 근접할 수 있다(근사비 향상). ② 더 복잡한 상관관계를 포착할 수 있어 지역 최솟값 회피 가능성이 높아진다. **단점** ① 회로 깊이가 깊어질수록 NISQ 소자의 게이트 오류와 디코히어런스 누적이 심해진다. ② 파라미터 수가 $2p$로 증가하므로 고전 최적화의 비볼록성이 심화되고 바렌 플래토 발생 위험이 증가한다.