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

개념 소개

조합 최적화 문제는 유한한 이산 해 공간에서 비용 함수를 최소(또는 최대)화하는 것으로, MaxCut·외판원 문제·포트폴리오 최적화 등이 대표적이다. 이 문제들 다수는 NP-난해로 분류되며, 해 공간의 크기가 지수적으로 증가한다.

QAOA는 이 문제를 양자컴퓨터로 다루기 위해 고안된 하이브리드 변분 알고리즘이다. 양자 회로가 기대값을 계산하는 역할을 맡고, 고전 컴퓨터가 회로 파라미터를 반복적으로 갱신한다. 순수 양자 알고리즘(쇼어, 그로버)과 달리, 얕은 회로로도 실행 가능하여 현재의 NISQ 장치에 적합하다.

---

핵심 원리

문제의 해밀토니안 인코딩

조합 최적화 문제의 이진 결정 변수 $z_i\in \{0,1\}$를 큐비트의 ${\hat{\sigma }}_i^z$ 고유값 $\pm 1$에 대응시킨다. 비용 함수 $C(z)$는 비용 해밀토니안으로 인코딩된다:

$${\hat{H}}_C=\sum _{\alpha }{c}_{\alpha }\prod _{i\in \alpha }{\hat{\sigma }}_i^z$$

여기서 $c_{\alpha }$는 문제별 계수이며, 상호작용 항의 구조가 문제의 제약·목적을 반영한다.

QAOA 앤새츠

깊이 파라미터 $p$를 고정하면 QAOA 상태는 다음과 같다:

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

각 층은 두 유니터리의 곱으로 구성된다.

• 초기 상태: $|+{⟩}^{\otimes n}$ — 아다마르 게이트로 균등 중첩 생성
• 비용 유니터리: $U_C({\gamma }_k)=e^{-i{\gamma }_k{\hat{H}}_C}$ — 비용 구조를 위상(phase)으로 각인
• 믹서 유니터리: $U_B({\beta }_k)=e^{-i{\beta }_k{\hat{H}}_B}$, ${\hat{H}}_B={\sum }_i{\hat{\sigma }}_i^x$ — 큐비트 간 위상 간섭을 통한 해 공간 탐색

총 $2p$개의 실수 파라미터 $(\mathbf{\gamma },\mathbf{\beta })\in {\mathbb{R}}^{2p}$가 최적화 대상이다.

변분 최적화 루프

고전 최적화기(COBYLA, SPSA, Adam 등)가 아래 기대값을 최대화하도록 파라미터를 갱신한다:

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

수렴 후 최적 파라미터로 회로를 반복 측정하여, 가장 높은 빈도로 출현하는 비트열을 근사 최적해로 채택한다.

이론적 한계 보장: $p=1$에서 MaxCut에 대해 최적값의 $\approx 0.6924$배 이상의 근사비(approximation ratio)를 달성하며, $p$가 증가할수록 단열 경로를 이산화한 것과 동일해져 정확해에 수렴한다.

---

예시·응용

MaxCut 문제

그래프 $G=(V,E)$에서 꼭짓점 집합을 두 부분으로 나누어 교차하는 간선 수를 최대화하는 문제의 비용 해밀토니안은:

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

${\hat{\sigma }}_i^z{\hat{\sigma }}_j^z$의 고유값이 $-1$이 되는(즉 두 큐비트가 다른 파티션에 속하는) 구성이 에너지를 낮추는 방향으로 작동한다.

아래는 Qiskit 기반의 $p=1$ QAOA 회로 구현이다:

from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler
import numpy as np

def qaoa_maxcut_p1(edges: list, n: int, gamma: float, beta: float) -> QuantumCircuit:
    """p=1 QAOA MaxCut 회로 구성"""
    qc = QuantumCircuit(n, n)

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

    # 비용 유니터리 U_C(gamma): ZZ 상호작용
    for (i, j) in edges:
        qc.cx(i, j)
        qc.rz(2 * gamma, j)
        qc.cx(i, j)

    # 믹서 유니터리 U_B(beta): X 회전
    for q in range(n):
        qc.rx(2 * beta, q)

    qc.measure(range(n), range(n))
    return qc

# 4-노드 고리 그래프: 이론적 최적 gamma=pi/4, beta=pi/8
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
qc = qaoa_maxcut_p1(edges, n=4, gamma=np.pi/4, beta=np.pi/8)
print(qc.draw("text"))

실제 최적화에서는 scipy.optimize.minimize 등으로 (gamma, beta)를 반복 탐색한다.

주요 응용 분야

분야	문제 유형
금융	포트폴리오 최적화, 리스크 최소화
물류	배송 경로, 작업 스케줄링
머신러닝	특징 선택, 클러스터링
통신	네트워크 자원 배분

모든 경우, 문제를 QUBO(Quadratic Unconstrained Binary Optimization) 형태로 변환한 뒤 Ising 해밀토니안에 매핑하는 것이 출발점이다.

---

정리

QAOA는 양자 위상 간섭과 변분 원리를 결합하여 조합 최적화를 다루는 알고리즘이다. 깊이 $p$를 늘릴수록 근사 품질은 개선되지만, 파라미터 수 증가에 따른 최적화 경관의 평탄화(barren plateau) 문제와 게이트 오류 누적이 핵심 장애물이다. 현재는 효율적인 파라미터 초기화 전략, 문제 특화 믹서 설계, 오류 완화 기법이 활발히 연구되고 있으며, QAOA의 양자 우위 달성 여부는 이론·실험 양면에서 열린 문제로 남아 있다.