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

개념 소개

QAOA는 조합 최적화 문제의 근사 해를 양자 컴퓨터에서 탐색하는 변분형 하이브리드 알고리즘이다. 이진 변수로 정의된 목적함수를 해밀토니안으로 인코딩하고, 파라미터화된 양자 회로가 해 공간을 탐색하는 동안 고전 최적화기가 파라미터를 반복 갱신한다.

이 알고리즘은 아디아배틱 양자 계산(Adiabatic Quantum Computation)의 게이트 모델 대응물로 이해할 수 있다. MaxCut, 포트폴리오 최적화, 스케줄링처럼 NP-난해(NP-hard)에 속하는 문제들이 주요 적용 대상이며, 단기 잡음 허용 양자 장치(NISQ)에서 실행 가능한 현실적인 후보 알고리즘으로 주목받는다.

핵심 원리

비용 해밀토니안 $H_C$

목적함수 $C(z)$를 파울리 Z 연산자로 인코딩한 해밀토니안이다. $n$개의 이진 변수 $z_i\in \{0,1\}$를 스핀 ${\sigma }_i^z\in \{+1,-1\}$로 매핑하면 일반적인 QUBO 형태는 다음과 같다.

$$H_C=\sum _{⟨i,j⟩}{J}_{ij}{\sigma }_i^z{\sigma }_j^z+\sum _i{h}_i{\sigma }_i^z$$

$H_C$의 기저 상태(ground state)가 곧 최적해에 대응하므로, 문제는 기저 상태 탐색으로 환원된다.

믹서 해밀토니안 $H_B$

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

각 큐비트에 X 회전을 가해 해 공간 전체를 균등하게 탐색하도록 유도하는 역할을 한다.

QAOA 회로 구조

깊이 파라미터 $p$에 따라 두 유니터리를 교대 적용한다.

$$U(H_C,\gamma )=e^{-i\gamma H_C},U(H_B,\beta )=e^{-i\beta H_B}$$

초기 상태 $|+{⟩}^{\otimes n}=H^{\otimes n}|0{⟩}^{\otimes n}$에서 출발해 QAOA 상태를 구성한다.

$$|\mathbf{\gamma },\mathbf{\beta }⟩=\prod _{k=p}^{1}U(H_B,{\beta }_k)U(H_C,{\gamma }_k)|+{⟩}^{\otimes n}$$

파라미터 벡터 $(\mathbf{\gamma },\mathbf{\beta })\in {\mathbb{R}}^{2p}$는 기대값

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

를 최대화하도록 고전 최적화기가 반복 갱신한다. $p\to \infty$ 극한에서는 아디아배틱 정리에 의해 정확한 최적해 수렴이 보장된다.

근사 비율

$p=1$에서 MaxCut 문제에 대해 QAOA는 근사 비율 $\alpha \ge 0.6924$를 이론적으로 달성함이 증명되어 있다. 고전 Goemans-Williamson SDP 알고리즘($\approx 0.878$)보다 낮지만, 양자 하드웨어에서 직접 실행 가능한 근사 보장이라는 점에서 의미를 갖는다.

예시·응용

MaxCut 비용 해밀토니안

그래프 $G=(V,E)$에서 정점 집합을 두 부분으로 나눠 경계 간선 수를 최대화하는 문제의 비용 해밀토니안은 다음과 같다.

$$H_C^{\text{MaxCut}}=\frac{1}{2}\sum _{(i,j)\in E}(1-{\sigma }_i^z{\sigma }_j^z)$$

간선 $(i,j)$에 대응하는 $U(H_C,\gamma )$는 ZZ 결합 게이트 $\text{CNOT}\cdot R_z(2\gamma )\cdot \text{CNOT}$로 구현된다.

Qiskit 구현 예시 (p=1, 4-노드 링)

from qiskit import QuantumCircuit
from qiskit.circuit import Parameter

def qaoa_maxcut_p1(edges, n_qubits):
    gamma = Parameter('γ')
    beta  = Parameter('β')
    qc = QuantumCircuit(n_qubits)

    # 초기 상태 |+>^n
    qc.h(range(n_qubits))

    # Cost unitary: exp(-i γ H_C)
    for (i, j) in edges:
        qc.cx(i, j)
        qc.rz(2 * gamma, j)
        qc.cx(i, j)

    # Mixer unitary: exp(-i β H_B)
    qc.rx(2 * beta, range(n_qubits))

    qc.measure_all()
    return qc

edges = [(0,1), (1,2), (2,3), (3,0)]  # 4-노드 링
qc = qaoa_maxcut_p1(edges, n_qubits=4)

고전 최적화기(예: COBYLA, BFGS)로 γ, β를 탐색한 뒤 측정값 분포에서 최빈 비트열을 근사 해로 채택한다.

응용 분야

• 포트폴리오 최적화: 자산 선택을 QUBO로 변환해 QAOA 적용
• 물류·스케줄링: 경로 배정, 작업 할당의 이진 최적화
• 머신러닝: 클러스터링, 특성 선택의 조합 탐색

실용적 도전 과제

현재 NISQ 장치에서 QAOA의 실용성은 다음 요인에 의해 제한된다. 첫째, 파라미터 랜드스케이프의 평탄화(barren plateau) 문제로 경사 기반 최적화가 어려워진다. 둘째, $p$가 커질수록 회로 깊이가 증가해 잡음 축적이 심화된다. 셋째, 고전 최적화기와 양자 회로 간 반복 통신 오버헤드가 실행 시간을 늘린다.

정리

QAOA는 비용 해밀토니안 $H_C$와 믹서 해밀토니안 $H_B$를 교대 적용하는 $p$층 변분 회로로 조합 최적화 문제를 근사 해결한다. 층수 $p$가 증가할수록 근사 품질이 향상되고 $p\to \infty$에서 정확해 수렴이 보장되지만, 현실 장치에서는 잡음과 barren plateau가 주요 병목이다. NISQ 시대의 대표적 변분 하이브리드 알고리즘으로서, 양자 우위 가능성과 실용적 한계에 대한 연구가 지속되고 있다.