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

개념 소개

조합 최적화 문제—최대 컷(MaxCut), 외판원 문제, 포트폴리오 최적화 등—는 가능한 해의 수가 지수적으로 증가해 고전 컴퓨터로 정확 해를 구하기 어렵다. QAOA는 이 어려움을 양자 중첩과 얽힘을 활용해 우회하려는 접근이다.

QAOA는 **변분 양자 고유값 분해기(VQE)**와 구조적으로 유사하지만, 목적 함수가 이진 문자열 최적화 문제의 비용 함수라는 점이 다르다. 핵심 아이디어는 최적화 문제를 해밀토니안으로 인코딩한 뒤, 파라미터화된 양자 회로의 기댓값을 고전 루프로 반복 최소화하는 것이다.

---

핵심 원리

비용 해밀토니안과 믹서 해밀토니안

이진 변수 $z_i\in \{0,1\}$에 대한 비용 함수 $C(z)$를 파울리 $Z$ 연산자로 대각화한 연산자를 비용 해밀토니안 ${\hat{H}}_C$라 한다.

$${\hat{H}}_C=\sum _{\alpha }{c}_{\alpha }\prod _{i\in S_{\alpha }}{Z}_i$$

믹서 해밀토니안 ${\hat{H}}_B$는 계산 기저 상태 사이를 전이시켜 탐색 공간을 이동시킨다. 가장 표준적인 선택은

$${\hat{H}}_B=\sum _{i=1}^n{X}_i$$

이다.

QAOA 회로 구조

깊이 $p$인 QAOA 회로는 초기 상태 $|s⟩=|+{⟩}^{\otimes n}$에서 출발해 두 종류의 유니터리를 교대로 적용한다.

$$|\mathbf{\gamma },\mathbf{\beta }⟩=\prod _{k=1}^p{e}^{-i{\beta }_k{\hat{H}}_B}{e}^{-i{\gamma }_k{\hat{H}}_C}|s⟩$$

여기서 $\mathbf{\gamma }=({\gamma }_1,\dots ,{\gamma }_p)$, $\mathbf{\beta }=({\beta }_1,\dots ,{\beta }_p)$는 고전 최적화기가 조정하는 $2p$개의 연속 파라미터다.

목적 함수 최대화

측정으로 추정한 기댓값

$$F_p(\mathbf{\gamma },\mathbf{\beta })=⟨\mathbf{\gamma },\mathbf{\beta }|{\hat{H}}_C|\mathbf{\gamma },\mathbf{\beta }⟩$$

를 최대화(비용 함수 최대화) 혹은 최소화하도록 파라미터를 갱신한다. $p\to \infty$ 극한에서 QAOA는 단열 양자 계산(AQC)으로 수렴하며, 이론적으로 최적 해에 도달한다.

근사 비율

$p=1$ QAOA가 MaxCut 문제에서 보장하는 근사 비율은

$$\alpha \ge \frac{0.6924\dots }{1}$$

으로, 고전 Goemans-Williamson SDP 알고리즘의 $\approx 0.878$보다 낮다. 그러나 $p$를 증가시키면 근사 비율이 향상되며, 특정 문제 구조에서 QAOA가 이점을 보일 가능성이 연구되고 있다.

---

예시·응용

MaxCut 문제

그래프 $G=(V,E)$에서 정점 집합을 두 부분으로 나누어 두 집합 사이를 가로지르는 에지 수를 최대화하는 문제다.

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

$p=1$일 때 $e^{-i\gamma {\hat{H}}_C}$ 게이트는 각 에지에 대한 2-큐비트 $ZZ$ 회전으로 분해되며, $e^{-i\beta {\hat{H}}_B}$는 각 큐비트에 대한 $R_X(2\beta )$ 게이트로 구현된다.

Qiskit을 이용한 간단한 골격 코드

from qiskit.circuit import QuantumCircuit, Parameter
import numpy as np

def qaoa_maxcut_p1(edges, n_qubits):
    gamma = Parameter('γ')
    beta  = Parameter('β')
    qc = QuantumCircuit(n_qubits)
    qc.h(range(n_qubits))           # 균등 중첩 초기화
    for (i, j) in edges:            # 비용 유니터리
        qc.cx(i, j)
        qc.rz(2 * gamma, j)
        qc.cx(i, j)
    qc.rx(2 * beta, range(n_qubits))  # 믹서 유니터리
    return qc

고전 루프에서 COBYLA, SPSA, Adam 등의 기울기-없는(gradient-free) 최적화기 또는 파라미터-이동 규칙(parameter-shift rule)을 사용해 $(\gamma ,\beta )$를 갱신한다.

현실적 한계와 발전 방향

• 파라미터 최적 경관: $2p$차원 경관에서 지역 최솟값(local minima) 문제가 발생한다.
• 노이즈 민감도: 현세대 NISQ 장치에서 $p\ge 5$ 이상이면 노이즈가 이점을 상쇄하는 경향이 있다.
• 워밍 스타트(warm-start): 고전 이완 해를 초기 상태에 인코딩해 수렴을 가속하는 연구가 활발하다.

---

정리

QAOA는 조합 최적화를 양자 회로로 표현하는 가장 체계적인 프레임워크 중 하나다. 층 수 $p$를 늘릴수록 표현력이 증가하지만, 파라미터 최적화 비용과 회로 깊이도 함께 증가한다. 현재는 NISQ 환경에서의 실질적 우위를 실험적으로 증명하는 것이 주요 과제이며, 문제별 맞춤 믹서 설계 및 파라미터 전략이 핵심 연구 방향이다.