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

개념 소개

조합 최적화 문제는 유한한 이진 변수 집합 위에서 목적 함수를 최대화(혹은 최소화)하는 해를 탐색한다. 대표적으로 MaxCut, 외판원 문제(TSP), 정수 선형 계획 등이 있으며, 대부분이 NP-난해 범주에 속한다. 고전 컴퓨터에서는 지수적 탐색 공간을 완전 탐색하기 어려워 다양한 휴리스틱이 사용된다.

QAOA는 Farhi, Goldstone, Gutmann(2014)이 제안한 알고리즘으로, 양자 중첩과 얽힘을 통해 해 공간을 병렬 탐색하는 아이디어를 변분 원리와 결합한다. 핵심 구조는 문제 해밀토니안 $H_C$와 혼합 해밀토니안 $H_B$를 교대로 적용하는 층(layer) $p$개짜리 파라미터화 유니타리이다.

---

핵심 원리

문제의 해밀토니안 인코딩

이진 변수 $z_i \in {0, 1}$를 파울리 $Z$ 연산자 $\frac{I - Z_i}{2}$로 대응하면, 고전 목적 함수 $C(\mathbf{z})$를 대각 해밀토니안으로 표현할 수 있다.

MaxCut을 예로 들면, 그래프 $G=(V,E)$에서

$$H_C = \frac{1}{2}\sum_{(i,j)\in E}(I - Z_i Z_j)$$

의 기댓값을 최대화하는 것이 목표다.

QAOA 회로

초기 상태를 균등 중첩으로 설정한다.

$$|\psi_0\rangle = H^{\otimes n}|0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}}\sum_{\mathbf{z} \in {0,1}^n}|\mathbf{z}\rangle$$

이후 깊이 $p$의 변분 회로를 적용한다.

$$|\boldsymbol{\gamma}, \boldsymbol{\beta}\rangle = \prod_{k=1}^{p} e^{-i\beta_k H_B}, e^{-i\gamma_k H_C},|\psi_0\rangle$$

혼합 해밀토니안은 통상적으로 $H_B = \sum_i X_i$를 사용하며, 이는 전체 큐비트에 $R_X(2\beta_k)$ 회전을 부여한다. 매개변수 벡터 $\boldsymbol{\gamma} = (\gamma_1,\ldots,\gamma_p)$, $\boldsymbol{\beta} = (\beta_1,\ldots,\beta_p)$는 고전 최적화기로 조율된다.

변분 목적 함수와 최적화

목적은 다음 기댓값을 최대화하는 매개변수를 찾는 것이다.

$$F_p(\boldsymbol{\gamma}, \boldsymbol{\beta}) = \langle \boldsymbol{\gamma}, \boldsymbol{\beta} | H_C | \boldsymbol{\gamma}, \boldsymbol{\beta} \rangle$$

최적화에는 COBYLA, Nelder-Mead, 혹은 기울기 기반의 Adam 계열 옵티마이저가 사용된다. 양자 회로에서 기울기는 **매개변수 이동 규칙(parameter-shift rule)**으로 해석적으로 계산할 수 있다.

$$\frac{\partial F}{\partial \gamma_k} = \frac{F(\gamma_k + \frac{\pi}{2}) - F(\gamma_k - \frac{\pi}{2})}{2}$$

근사 비율

QAOA의 해 품질은 근사 비율(approximation ratio) $r = F_p / C_{\max}$로 평가한다. $p=1$에서도 MaxCut 문제에 대해 Goemans-Williamson 경계(0.878)에 근접하거나 능가하는 경우가 있으며, $p$가 커질수록 $r \to 1$로 수렴한다.

---

예시·응용

MaxCut (4-노드 예시) — Qiskit 구현

from qiskit import QuantumCircuit
from qiskit.circuit import ParameterVector
import numpy as np

def build_qaoa_maxcut(edges, p=1):
    n = max(max(e) for e in edges) + 1
    gamma = ParameterVector('γ', p)
    beta  = ParameterVector('β', p)

    qc = QuantumCircuit(n)
    # 초기 균등 중첩
    qc.h(range(n))

    for layer in range(p):
        # 문제 유니타리: e^{-i γ H_C}
        for (i, j) in edges:
            qc.cx(i, j)
            qc.rz(2 * gamma[layer], j)
            qc.cx(i, j)
        # 혼합 유니타리: e^{-i β H_B}
        for i in range(n):
            qc.rx(2 * beta[layer], i)

    return qc

edges = [(0,1), (1,2), (2,3), (3,0)]
qc = build_qaoa_maxcut(edges, p=2)
print(qc.draw('text'))

고전 최적화 루프 골격

from scipy.optimize import minimize

def cost_function(params, qc, edges, backend):
    p = len(params) // 2
    gamma_vals = params[:p]
    beta_vals  = params[p:]
    bound = qc.assign_parameters(
        {**dict(zip(qc.parameters[:p], gamma_vals)),
         **dict(zip(qc.parameters[p:], beta_vals))}
    )
    counts = backend.run(bound, shots=2048).result().get_counts()
    # MaxCut 기댓값 계산
    total = 0
    for bitstring, cnt in counts.items():
        z = [int(b) for b in bitstring]
        cut = sum(z[i] ^ z[j] for (i, j) in edges)
        total += cut * cnt
    return -total / 2048   # 최소화이므로 음수 반환

x0 = np.random.uniform(0, 2*np.pi, 4)   # p=2이므로 4개 매개변수
result = minimize(cost_function, x0, method='COBYLA',
                  args=(qc, edges, backend))

실용 적용 분야

분야	문제 유형
물류·공급망	차량 경로 최적화(VRP)
금융	포트폴리오 최적화
반도체 설계	회로 배치·라우팅
머신러닝	클러스터링(QUBO 변환)

모든 문제는 이진 이차 무제약 최적화(QUBO) 형식으로 변환 후 QAOA에 투입된다.

---

정리

QAOA는 변분 양자 고유값 분해기(VQE)의 조합 최적화 특화 형태로, 문제 구조를 해밀토니안에 직접 인코딩한다는 점이 차별점이다. 현재의 NISQ 장치에서 $p$가 작을 때 노이즈 한계 내에서 실행 가능하지만, 충분한 근사 비율을 얻으려면 오류 완화 기법과 결합이 필요하다. 장기적으로 오류 정정 양자 컴퓨터에서 $p$를 대폭 늘릴 경우, 고전 알고리즘 대비 양자 우위의 실증 가능성이 주목받고 있다.