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

개념 소개

조합 최적화 문제는 유한한 이진 변수 공간에서 비용 함수를 최소화(또는 최대화)하는 해를 찾는 문제군이다. 그래프 최대 절단(MaxCut), 정수 계획법, 외판원 문제 등이 대표적이며 대부분 NP-난해 클래스에 속한다. 고전 근사 알고리즘은 일정한 근사 비율을 보장하지만, 문제 규모가 커질수록 탐색 공간이 지수적으로 증가하는 한계가 있다.

**양자 근사 최적화 알고리즘(QAOA)**은 변분 회로와 고전 최적화기를 결합한 하이브리드 알고리즘이다. 비용 함수를 파울리 연산자로 인코딩한 해밀토니언을 회로에 직접 새겨 넣고, 파라미터를 고전적으로 최적화함으로써 근사 해를 산출한다.

---

핵심 원리

두 해밀토니언의 교대 구조

QAOA 회로는 두 유니터리를 $p$회 교대 적용하는 구조를 갖는다.

• 비용 유니터리 $U_C({\gamma }_k)=e^{-i{\gamma }_{k}C}$
  $C$는 최적화 목적 함수를 이징(Ising) 형태로 인코딩한 대각 연산자다.
• 혼합 유니터리 $U_B({\beta }_k)=e^{-i{\beta }_{k}B}$, $B={\sum }_{i=1}^n{X}_i$
  탐색 공간 전반에 걸친 양자 확산 역할을 한다.

초기 상태를 균일 중첩 $|s⟩=H^{\otimes n}|0{⟩}^{\otimes n}$으로 설정하면, $p$층 회로의 출력 상태는 다음과 같다:

$$|\mathbf{\gamma },\mathbf{\beta }⟩=U_B({\beta }_p)U_C({\gamma }_p)\cdots U_B({\beta }_1)U_C({\gamma }_1)|s⟩$$

변분 최적화 목적 함수

고전 최적화기가 최대화하는 목적 함수는 비용 연산자의 기댓값이다:

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

파라미터 벡터 $(\mathbf{\gamma },\mathbf{\beta })\in {\mathbb{R}}^{2p}$는 COBYLA, SPSA, Adam 등 고전 최적화 기법으로 반복 갱신된다. $p\to \infty$ 극한에서는 정확한 최적해 수렴이 이론적으로 보장되며, $p=1$에서도 MaxCut 문제에 대해 **근사 비율 $\ge 0.6924$**가 해석적으로 유도된다.

QUBO와 이징 해밀토니언 변환

이진 변수 $z_i\in \{0,1\}$을 스핀 변수 $s_i=1-2z_i\in \{-1,+1\}$로 치환하면, 대부분의 이진 이차 최적화(QUBO) 문제는 이징 모델 형태로 변환된다:

$$C=\sum _{i<j}{J}_{ij}{Z}_i{Z}_j+\sum _i{h}_i{Z}_i$$

---

예시·응용

MaxCut 문제 ($p=1$)

3-노드 완전 그래프 $G$의 MaxCut 비용 해밀토니언은 다음과 같다:

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

Qiskit으로 구현한 $p=1$ QAOA 회로 예시:

from qiskit import QuantumCircuit
import numpy as np

def qaoa_maxcut_p1(gamma: float, beta: float) -> QuantumCircuit:
    qc = QuantumCircuit(3)
    # 균일 중첩 초기화
    qc.h([0, 1, 2])
    # 비용 유니터리: e^{-i gamma C}
    for u, v in [(0, 1), (1, 2), (0, 2)]:
        qc.cx(u, v)
        qc.rz(2 * gamma, v)
        qc.cx(u, v)
    # 혼합 유니터리: e^{-i beta B}
    qc.rx(2 * beta, [0, 1, 2])
    qc.measure_all()
    return qc

# 고전 최적화기와 연동 시 scipy.optimize.minimize 등을 활용
qc = qaoa_maxcut_p1(gamma=0.5, beta=0.3)

실용 응용 분야

분야	문제 예시
물류	배송 경로 최적화, 작업 배정
금융	포트폴리오 선택, 위험 최소화
반도체 설계	회로 배선, 플로어플래닝
머신러닝	클러스터링, 특징 선택

IBM Quantum 및 Google Quantum AI의 초전도 큐비트 프로세서에서 소규모 QAOA 실험이 수행되었으며, 현재는 노이즈 내성과 파라미터 초기화 전략(warm-starting)이 활발히 연구되고 있다.

---

정리

QAOA는 비용·혼합 해밀토니언의 교대 적용과 변분 파라미터 최적화를 결합한 하이브리드 알고리즘이다. 층수 $p$를 증가시킬수록 해의 품질이 향상되지만 회로 깊이도 비례하여 증가하므로, NISQ 하드웨어의 노이즈 임계 내에서 $p$와 근사 정확도의 균형을 설계하는 것이 핵심 실용 과제다. 변분 회로의 표현력 한계(barren plateau)와 고전 최적화기의 수렴 안정성은 여전히 열린 연구 문제다.