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

개념 소개

조합 최적화 문제—그래프 최대 절단(MaxCut), 여행 판매원, 포트폴리오 배분 등—는 가능한 해의 수가 입력 크기에 대해 지수적으로 증가하여 고전 알고리즘으로는 정확한 해를 찾기 매우 어렵다. QAOA는 이러한 문제를 양자회로로 근사하는 변분 알고리즘이다.

핵심 아이디어는 두 종류의 유니터리 연산을 교대로 적용하는 것이다. 첫째는 문제의 비용 함수를 인코딩한 비용 해밀토니안 $H_C$, 둘째는 해 공간을 균등하게 탐색하도록 돕는 혼합 해밀토니안 $H_B$이다. 두 연산의 각도 매개변수 $\mathbf{\gamma }$, $\mathbf{\beta }$를 고전 최적화기로 반복 조율하면서 비용 기댓값을 최대화한다.

QAOA는 양자 단열 계산(Quantum Adiabatic Computation)의 이산화(Trotterization)로 이해할 수 있다. 회로 깊이 $p\to \infty$ 극한에서 이론적으로 정확한 최적해에 수렴함이 알려져 있다.

---

핵심 원리

문제 인코딩

조합 최적화 문제는 이진 문자열 $z\in \{0,1{\}}^n$ 위의 목적 함수 $C(z)$를 최대화하는 형태로 정형화된다. 이를 계산 기저에서 대각인 해밀토니안으로 변환하면:

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

표준 혼합 해밀토니안은 각 큐비트에 파울리 $X$ 연산자를 적용한다:

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

QAOA 앤사츠

모든 큐비트를 아다마르 게이트로 균일 중첩 상태에 초기화한다:

$$|s⟩=H^{\otimes n}|0{⟩}^{\otimes n}=\frac{1}{\sqrt{2^n}}\sum _z|z⟩$$

이후 비용 유니터리 $U(H_C,{\gamma }_k)=e^{-i{\gamma }_k{H}_C}$와 혼합 유니터리 $U(H_B,{\beta }_k)=e^{-i{\beta }_k{H}_B}$를 교대로 $p$회 적용한다:

$$|\mathbf{\gamma },\mathbf{\beta }⟩=U(H_B,{\beta }_p)U(H_C,{\gamma }_p)\cdots U(H_B,{\beta }_1)U(H_C,{\gamma }_1)|s⟩$$

고전 최적화기는 다음 기댓값을 최대화하도록 매개변수를 갱신한다:

$$({\mathbf{\gamma }}^{\ast },{\mathbf{\beta }}^{\ast })=\arg \underset{\mathbf{\gamma },\mathbf{\beta }}{\max }⟨\mathbf{\gamma },\mathbf{\beta }|H_C|\mathbf{\gamma },\mathbf{\beta }⟩$$

근사 비율

$p$층 QAOA의 근사 비율 $r_p$는 기댓값과 최적값의 비로 정의된다:

$$r_p=\frac{⟨H_C{⟩}_{\text{opt}}}{{\max }_{z}C(z)}$$

MaxCut 문제에 대해 $p=1$에서 $r_1\ge 0.6924$임이 이론적으로 증명되어 있다. 비교 기준으로, 고전 무작위 알고리즘의 근사 비율은 $0.5$이며, Goemans-Williamson SDP 알고리즘은 $\approx 0.8785$를 달성한다.

---

예시·응용

MaxCut: 비용 해밀토니안 구성

그래프 $G=(V,E)$의 MaxCut은 정점 집합을 두 부분으로 나누어 두 부분 사이의 간선 수를 최대화하는 문제다. 간선 $(i,j)$에 대해 두 끝점이 다른 그룹에 속할 때 기여값이 1이므로:

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

$Z_i{Z}_j=+1$ (같은 상태) 이면 기여 0, $Z_i{Z}_j=-1$ (다른 상태) 이면 기여 1이 된다.

Qiskit 구현 예시 ($p=1$, 4정점 고리 그래프)

from qiskit import QuantumCircuit
from qiskit.circuit import Parameter

def maxcut_qaoa_p1(edges, n):
    gamma = Parameter('γ')
    beta  = Parameter('β')
    qc = QuantumCircuit(n)

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

    # 비용 유니터리: e^{-i γ H_C}
    for (u, v) in edges:
        qc.cx(u, v)
        qc.rz(2 * gamma, v)
        qc.cx(u, v)

    # 혼합 유니터리: e^{-i β H_B}
    qc.rx(2 * beta, range(n))

    qc.measure_all()
    return qc

# 4정점 고리: 0-1-2-3-0
edges = [(0,1),(1,2),(2,3),(3,0)]
qc = maxcut_qaoa_p1(edges, n=4)
print(qc.draw())

비용 유니터리의 간선 항 $e^{-i\gamma (I-Z_i{Z}_j)/2}$는 CNOT-$R_z$-CNOT 구조로 분해된다.

고전 최적화 루프

매개변수 최적화에는 두 가지 접근이 주로 쓰인다.

• 경사도 없는 방법: COBYLA, Nelder-Mead — 측정 횟수를 줄이는 데 유리하다.
• 매개변수 이동 규칙(parameter-shift rule): 경사도를 양자회로 측정만으로 계산할 수 있어 역전파 없이도 경사 하강법을 적용할 수 있다.

$$\frac{\partial ⟨H_C⟩}{\partial {\gamma }_k}=\frac{1}{2}\left[⟨H_C{⟩}_{{\gamma }_k+\pi /2}-⟨H_C{⟩}_{{\gamma }_k-\pi /2}\right]$$

확장: 제약 있는 문제

등식 제약 ${\sum }_i{z}_i=k$가 있는 문제에서는 표준 $X$-mixer 대신 XY-mixer를 사용하면 제약을 항상 만족하는 부분 공간 내에서만 탐색이 이루어진다. 또는 제약 위반에 페널티 항을 비용 해밀토니안에 추가하는 방법도 흔히 쓰인다.

---

정리

QAOA는 변분 원리·중첩·얽힘을 결합해 조합 최적화에 접근하는 하이브리드 양자-고전 알고리즘이다. 회로 깊이 $p$와 고전 최적화기의 성능이 근사 품질을 결정하며, 현재 NISQ 장치에서 실행 가능한 수준의 회로를 유지할 수 있다. 특정 문제 구조에서 고전 알고리즘 대비 양자 우위를 보일 가능성은 아직 열린 연구 문제이지만, QAOA는 근미래 양자 하드웨어의 실용적 기준점으로 폭넓게 연구되고 있다.