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

개념 소개

조합 최적화 문제는 유한한 이진 변수 집합 위에서 목적 함수를 최대화(또는 최소화)하는 해를 찾는 문제다. 외판원 문제, 그래프 분할, 포트폴리오 최적화 등 다수가 NP-난해(NP-hard) 범주에 속한다. QAOA는 이러한 문제를 파울리 연산자로 인코딩된 해밀토니안 형태로 변환하고, 매개변수화된 양자 회로를 반복 실행해 고전 최적화기와 결합하는 방식으로 근사 해를 추구한다.

핵심 아이디어는 두 해밀토니안의 교대 적용이다. 하나는 문제의 목적 함수를 인코딩한 비용 해밀토니안 $H_C$, 다른 하나는 해 공간 전체를 탐색하도록 돕는 혼합 해밀토니안 $H_B$다. 이 구조는 단열 양자 계산의 이산화(discretization)로 해석할 수 있으며, VQE(변분 양자 고유값 분해기)와 같은 변분 패밀리에 속한다.

---

핵심 원리

문제 인코딩 — Ising 형식

$n$개의 이진 변수 $z_i\in \{0,1\}$로 구성된 목적 함수 $C(\mathbf{z})$를 파울리 $Z$ 연산자($Z_i$의 고유값 $\pm 1$)로 치환하면 비용 해밀토니안을 구성할 수 있다. MaxCut 문제(그래프의 에지를 최대한 많이 자르는 이분할 탐색)를 예로 들면:

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

두 노드가 서로 다른 파티션에 속할 때 $Z_i{Z}_j=-1$이 되어 해당 항이 1을 기여한다. 이를 일반화한 형태인 QUBO(Quadratic Unconstrained Binary Optimization)도 동일하게 이징 해밀토니안으로 변환된다.

QAOA 안사츠

깊이 $p$의 QAOA 상태는 균등 중첩 초기 상태 $|+{⟩}^{\otimes n}$에 비용 유니터리와 혼합 유니터리를 교대 적용하여 생성된다:

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

여기서 혼합 해밀토니안은 표준 선택으로

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

를 사용하며, $(\mathbf{\gamma },\mathbf{\beta })\in {\mathbb{R}}^{2p}$가 훈련 가능한 매개변수다.

고전-양자 최적화 루프

목표는 비용 해밀토니안의 기댓값을 최대화하는 매개변수를 찾는 것이다:

$$({\mathbf{\gamma }}^{\ast },{\mathbf{\beta }}^{\ast })=\underset{\mathbf{\gamma },\mathbf{\beta }}{\mathrm{argmax}}⟨\mathbf{\gamma },\mathbf{\beta }|H_C|\mathbf{\gamma },\mathbf{\beta }⟩$$

양자 장치는 회로를 실행하여 기댓값을 측정하고, 고전 최적화기(COBYLA, L-BFGS-B 등)가 이를 바탕으로 매개변수를 갱신한다. 이 루프를 수렴 조건이 충족될 때까지 반복한다.

근사 비율과 깊이 $p$

$p=1$의 경우 MaxCut에 대해 근사 비율(approximation ratio) $\alpha \ge 0.6924$가 이론적으로 보장된다. 깊이 $p$가 증가할수록 해의 품질은 향상되지만, 매개변수 수($2p$)와 회로 깊이가 늘어나 NISQ 장치에서 노이즈 영향이 커지는 트레이드오프가 존재한다. $p\to \infty$에서는 단열 양자 컴퓨팅과 등가가 됨이 알려져 있다.

---

예시·응용

MaxCut 구현 (Qiskit 의사 코드)

from qiskit import QuantumCircuit
import numpy as np

def build_qaoa_circuit(n_qubits, edges, p, gamma, beta):
    qc = QuantumCircuit(n_qubits)
    # 초기 상태: 균등 중첩
    qc.h(range(n_qubits))
    for k in range(p):
        # 비용 유니터리: e^{-i gamma_k H_C}
        for (i, j) in edges:
            qc.rzz(2 * gamma[k], i, j)   # RZZ = e^{-i theta/2 Z⊗Z}
        # 혼합 유니터리: e^{-i beta_k H_B}
        for q in range(n_qubits):
            qc.rx(2 * beta[k], q)
    qc.measure_all()
    return qc

# 4-노드 사이클 그래프, p=1 예시
edges  = [(0,1), (1,2), (2,3), (3,0)]
gamma  = [0.5]
beta   = [0.3]
qc = build_qaoa_circuit(4, edges, p=1, gamma=gamma, beta=beta)

RZZ 게이트는 하드웨어 구현 시 CNOT + RZ 게이트로 분해된다.

응용 분야

분야	대표 문제
물류·교통	차량 경로 최적화(VRP)
금융	포트폴리오 리스크 최적화
네트워크	최대 독립 집합, 그래프 분할
제조	작업 스케줄링

실용적 고려사항

• Barren Plateau: 매개변수 공간의 기울기가 시스템 크기에 지수적으로 소멸하는 현상. INTERP·FOURIER 전략이나 레이어별 훈련으로 완화 가능하다.
• 매개변수 초기화: 무작위 초기화보다 단열 경로에서 영감을 받은 초기값이나 이전 $p-1$ 레이어의 해를 재사용하는 방식이 효과적이다.
• 샷 잡음: 유한한 측정 횟수에서 기댓값 추정 분산이 발생하므로, 충분한 샷 수 확보가 필요하다.

---

정리

QAOA는 조합 최적화 문제를 이징 해밀토니안으로 인코딩하고, 비용-혼합 유니터리의 교대 구조를 가진 안사츠와 고전 최적화기를 결합하는 대표적인 변분 하이브리드 알고리즘이다. 회로 깊이 $p$는 해의 품질과 회로 복잡도 사이의 균형을 결정하는 핵심 설계 변수이며, 이론적으로는 단열 양자 계산의 이산화 한계와 연결된다. NISQ 환경에서는 노이즈, barren plateau, 샷 잡음이 실질적 장벽이지만, 오류 내성 양자 컴퓨터가 실현될 경우 높은 $p$에서의 양자 이점이 기대된다.