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

개념 소개

조합 최적화(combinatorial optimization)는 이산 변수의 조합 중에서 목적 함수를 최대화·최소화하는 해를 찾는 문제다. 최대 절단(MaxCut), 외판원 문제(TSP), 포트폴리오 최적화가 대표적이며, 변수 수가 늘어날수록 탐색 공간이 지수적으로 증가해 고전 컴퓨터로는 엄밀한 풀이가 어렵다.

QAOA는 Farhi, Goldstone, Gutmann이 제안한 알고리즘으로, 양자 단열 계산(quantum adiabatic computation)에서 영감을 받아 설계되었다. 얕은 양자 회로와 고전 최적화기를 결합하는 하이브리드 변분 구조 덕분에 NISQ(Noisy Intermediate-Scale Quantum) 기기에서 실행 가능한 현실적인 후보로 주목받는다.

---

핵심 원리

두 해밀토니안의 역할

QAOA는 두 가지 해밀토니안을 교대로 적용한다.

• 비용 해밀토니안 $H_C$: 목적 함수를 파울리 연산자로 인코딩한다. 계산 기저 상태 $|z⟩$에 대해 $H_C|z⟩=C(z)|z⟩$ 이 성립하도록 구성하며, $C(z)$는 최적화 대상 함수다.
• 믹서 해밀토니안 $H_B$: 해 공간을 탐색(mixing)한다. 표준 선택은 단일 큐비트 $X$ 게이트의 합이다.

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

QAOA 회로 구조

깊이 $p$의 QAOA 회로는 다음 순서로 구성된다.

1단계: 초기 상태 준비

$$|s⟩=H^{\otimes n}|0{⟩}^{\otimes n}=|+{⟩}^{\otimes n}$$

아다마르 변환으로 모든 계산 기저 상태의 균등 중첩을 만든다.

2단계: $p$개 레이어 반복

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

여기서 두 유니타리 연산자는 해밀토니안의 지수로 정의된다.

$$U_C({\gamma }_k)=e^{-i{\gamma }_k{H}_C},U_B({\beta }_k)=e^{-i{\beta }_k{H}_B}$$

3단계: 기댓값 최대화 (고전 루프)

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

이 기댓값을 최대화하는 최적 파라미터 $({\mathbf{\gamma }}^{\ast },{\mathbf{\beta }}^{\ast })$를 COBYLA, BFGS 등의 고전 최적화기로 탐색한다. $p\to \infty$ 극한에서 양자 단열 정리에 의해 최적해로 수렴한다.

근사 보장

$p=1$에서 MaxCut 문제에 대해 QAOA는 근사비(approximation ratio) 0.6924 이상을 달성함이 이론적으로 증명되어 있다. 고전 Goemans-Williamson 알고리즘의 0.8786보다 낮지만, 양자 하드웨어에서 직접 실행 가능한 다항 깊이 회로로 구현된다는 점이 차별화된다. $p$가 커질수록 근사 품질이 단조 향상됨도 알려져 있다.

---

예시·응용

MaxCut 비용 해밀토니안 구성

그래프 $G=(V,E)$에서 MaxCut의 목적 함수는 이진 변수 $z_i\in \{-1,+1\}$로 다음과 같이 쓸 수 있다.

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

$z_i$를 파울리 $Z$ 연산자로 치환하면 비용 해밀토니안은:

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

각 간선 $(i,j)$에 대해 $e^{-i\gamma \frac{1-Z_i{Z}_j}{2}}$는 $\text{CNOT}$과 $R_z$ 게이트의 조합인 ZZ 회전 게이트 $R_{ZZ}(2\gamma )$로 구현된다.

Qiskit 구현 예시 ($p=1$, 3-노드 삼각형 그래프)

import numpy as np
from qiskit import QuantumCircuit
from scipy.optimize import minimize

edges = [(0, 1), (1, 2), (0, 2)]
n = 3

def build_qaoa_circuit(gamma: float, beta: float) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    qc.h(range(n))                       # 균등 중첩 초기화
    for (u, v) in edges:
        qc.rzz(2 * gamma, u, v)          # U_C(gamma): ZZ 회전
    qc.rx(2 * beta, range(n))            # U_B(beta): X 회전
    qc.measure_all()
    return qc

def cost_from_bitstring(bitstring: str) -> float:
    z = [1 - 2 * int(b) for b in bitstring]  # {0,1} → {+1,-1}
    return sum((1 - z[u] * z[v]) / 2 for u, v in edges)

# 실제 실행 시 Sampler 프리미티브로 기댓값 계산
# 여기서는 최적화 루프 구조만 예시로 표현
def objective(params):
    gamma, beta = params
    qc = build_qaoa_circuit(gamma, beta)
    # ... 샘플링 후 가중 평균 반환 (생략)
    return 0.0   # 플레이스홀더

result = minimize(objective, x0=[0.5, 0.5], method='COBYLA',
                  options={'maxiter': 300})
print(f"최적 파라미터: γ={result.x[0]:.4f}, β={result.x[1]:.4f}")

주요 응용 및 변형

문제 유형	QAOA 적용 방식
MaxCut	표준 $H_C={\sum }_{(i,j)}\frac{1-Z_i{Z}_j}{2}$
포트폴리오 최적화	이진 자산 선택을 이차 목적함수로 인코딩
제약 만족 (SAT)	페널티 항을 $H_C$에 추가한 페널티 QAOA
그래프 색칠	XY 믹서를 사용한 제약 보존 QAOA

---

정리

QAOA는 비용 해밀토니안과 믹서 해밀토니안을 $p$회 교대 적용하는 변분 양자 알고리즘이다. 레이어 수 $p$가 증가할수록 근사 품질이 향상되며, $p\to \infty$ 에서 최적해로 수렴한다. 고전 최적화기와의 하이브리드 구조로 NISQ 기기에서의 실용성을 확보하지만, 보리 오류(barren plateau), 측정 잡음, 고전 파라미터 최적화의 수렴 문제가 실용적 성능 향상의 주요 과제로 남아 있다. 믹서 해밀토니안의 다양화, 워밍 스타트(warm-start) 초기화, 재귀적 QAOA(RQAOA) 등의 변형이 이러한 한계를 극복하기 위해 활발히 연구되고 있다.