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

개념 소개

조합 최적화 문제는 유한한 이산 해 공간에서 목적 함수를 최대화·최소화하는 해를 찾는 문제다. 외판원 문제, 그래프 분할(MaxCut), 작업 스케줄링 등이 대표적이며, 다수는 NP-난해 복잡도를 지닌다. 해 공간이 변수 수 $n$에 대해 $2^n$으로 지수 성장하므로 고전 컴퓨터는 전수 탐색 대신 근사 알고리즘에 의존한다.

QAOA는 양자 중첩과 간섭을 활용해 이러한 문제를 근사 해결하는 **변분 양자 알고리즘(VQA)**이다. 매개변수화된 양자 회로와 고전 최적화기를 반복 호출하는 양자-고전 하이브리드 구조를 취하며, 현재의 NISQ 장치에서 실행 가능하도록 설계되었다.

---

핵심 원리

해밀토니안 인코딩

$n$비트 이진 목적 함수 $C(\mathbf{z})$를 $n$큐비트 비용 해밀토니안 $H_C$로 인코딩한다. $H_C$는 파울리 $Z$ 연산자의 함수로 대각 행렬을 이루며,

$$H_C=\sum _{\alpha }{c}_{\alpha }\prod _{j\in S_{\alpha }}{Z}_j$$

형태로 쓰인다. $H_C$의 최대 고유값에 대응하는 고유 상태가 곧 최적해다.

혼합(Mixer) 해밀토니안 $H_B$는 해 공간 탐색을 담당한다. 표준 선택은

$$H_B=\sum _{j=1}^n{X}_j$$

로, 모든 큐비트에 파울리 $X$를 합산한 형태다.

QAOA 회로 구조

깊이 $p$의 QAOA 회로는 다음 순서로 구성된다.

1. 초기 상태 준비 — 하다마르 변환으로 균등 중첩을 생성한다.

$$|{\psi }_0⟩=H^{\otimes n}|0{⟩}^{\otimes n}=\frac{1}{\sqrt{2^n}}\sum _{\mathbf{z}\in \{0,1{\}}^n}|\mathbf{z}⟩$$

2. $p$층 교대 유니터리 적용 — 각 층 $k=1,\dots ,p$에서

$$U_C({\gamma }_k)=e^{-i{\gamma }_k{H}_C},U_B({\beta }_k)=e^{-i{\beta }_k{H}_B}$$

를 순서대로 적용한다.

3. 최종 상태와 기댓값 측정

$$|\mathbf{\gamma },\mathbf{\beta }⟩=\prod _{k=1}^p{U}_B({\beta }_k)U_C({\gamma }_k)|{\psi }_0⟩$$

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

변분 최적화 루프

고전 최적화기(COBYLA, L-BFGS-B, Adam 등)가 $F_p$를 최대화하도록 $\mathbf{\gamma }=({\gamma }_1,\dots ,{\gamma }_p)$, $\mathbf{\beta }=({\beta }_1,\dots ,{\beta }_p)$를 반복 갱신한다. 층수 $p$가 커질수록 근사 비율(approximation ratio)이 향상되며, $p\to \infty$ 극한에서 양자 단열 알고리즘과 동치임이 이론적으로 알려져 있다.

---

예시·응용

MaxCut 문제

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

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

로 쓰인다. $Z_i{Z}_j=-1$이면 두 꼭짓점이 다른 집합에 속해 해당 간선이 절단된 것이다.

Qiskit을 이용한 $p=1$ MaxCut 구현 예시

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

edges = [(0, 1), (1, 2), (0, 2)]   # 3-노드 삼각 그래프
n = 3

def build_qaoa(gamma, beta):
    qc = QuantumCircuit(n)
    qc.h(range(n))                  # 균등 중첩
    for (i, j) in edges:            # U_C(gamma): ZZ 상호작용
        qc.cx(i, j)
        qc.rz(2 * gamma, j)
        qc.cx(i, j)
    for q in range(n):              # U_B(beta): X 회전
        qc.rx(2 * beta, q)
    qc.measure_all()
    return qc

def objective(params):
    qc = build_qaoa(*params)
    # 시뮬레이터로 샘플링 후 기댓값 추정 (스켈레톤)
    return -estimate_cut(qc)        # 최소화 → 부호 반전

res = minimize(objective, x0=[0.5, 0.5], method='COBYLA')
print("최적 (γ, β):", res.x)

$e^{-i\gamma Z_i{Z}_j}$ 항은 CNOT–$R_z$–CNOT 시퀀스로 분해되며, 이는 ZZ 상호작용의 표준 트로터화에 해당한다.

주요 응용 분야

분야	대표 문제
물류·교통	차량 경로 최적화, TSP
금융	포트폴리오 선택, 리스크 관리
약물 설계	분자 구조 탐색
반도체	회로 배치·배선 최적화

IBM Quantum, Google 등은 QAOA를 NISQ 시대 핵심 응용 후보로 지속 연구하고 있다.

---

정리

QAOA는 비용 해밀토니안 $H_C$와 혼합 해밀토니안 $H_B$를 교대 적용하는 $p$층 변분 회로로 조합 최적화를 근사 해결한다. 매개변수 $(\mathbf{\gamma },\mathbf{\beta })$는 고전 최적화기로 조율되며, $p$가 클수록 더 정밀한 근사가 가능하다. 잡음·배런 평원(barren plateau) 문제, 매개변수 훈련의 어려움이 현재 주요 연구 과제이며, 하드웨어 발전과 함께 실질적 양자 우위 달성 여부가 집중 탐구되고 있다.