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

개념 소개

QAOA는 Farhi, Goldstone, Gutmann이 제안한 변분 하이브리드(hybrid variational) 알고리즘으로, NP-난해 범주에 속하는 조합 최적화 문제를 근사적으로 해결하는 것을 목표로 한다. 핵심 아이디어는 최적화 목적함수를 양자 해밀토니안으로 번역하고, 매개변수화된 양자 회로를 통해 그 기댓값을 최소화하는 변분 원리에 있다.

고전 컴퓨터가 매개변수를 갱신하고, 양자 컴퓨터가 기댓값을 측정하는 루프를 반복한다는 점에서 VQE(Variational Quantum Eigensolver)와 구조적으로 유사하다. 그러나 QAOA는 단열 양자 계산(Adiabatic Quantum Computation)에서 직접 파생되었으며, 회로 깊이 $p\to \infty$ 극한에서 정확한 해로 수렴함이 이론적으로 증명되어 있다.

---

핵심 원리

문제의 해밀토니안 인코딩

$n$개의 이진 변수 $z_i\in \{0,1\}$로 정의된 조합 최적화 문제는 비용 함수 $C(\mathbf{z})$의 최대화(또는 최소화)로 표현된다. 이를 큐비트 $Z$ 연산자로 치환하면 비용 해밀토니안 $H_C$가 된다.

$$H_C=\sum _{\alpha }{c}_{\alpha }\prod _{i\in S_{\alpha }}{Z}_i$$

QAOA 앤사츠 구조

QAOA 상태는 두 종류의 유니터리를 교번 적용하여 구성된다.

• 비용 유니터리: $U_C(\gamma )=e^{-i\gamma H_C}$
• 믹서 유니터리: $U_B(\beta )=e^{-i\beta H_B}$, 여기서 $H_B={\sum }_{j=1}^n{X}_j$

깊이 $p$인 QAOA 앤사츠는 다음과 같다.

$$|\mathbf{\gamma },\mathbf{\beta }⟩=U_B({\beta }_p)U_C({\gamma }_p)\cdots U_B({\beta }_1)U_C({\gamma }_1)|+{⟩}^{\otimes n}$$

초기 상태 $|+{⟩}^{\otimes n}$은 아다마르 게이트를 전체 큐비트에 적용하여 준비한다. 목적은 변분 매개변수 $(\mathbf{\gamma },\mathbf{\beta })\in {\mathbb{R}}^{2p}$를 최적화하여

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

를 최대화하는 것이다. 이 기댓값의 계산은 양자 하드웨어에서, 매개변수 갱신은 고전 최적화기(COBYLA, ADAM 등)에서 담당한다.

근사비 보장

깊이 $p=1$일 때, MaxCut 문제에 대해 최소 $0.6924$의 근사비(approximation ratio)가 보장됨이 해석적으로 증명되어 있다. $p$가 증가할수록 근사비는 단조 비감소한다.

---

예시·응용

MaxCut 문제 (p=1)

그래프 $G=(V,E)$가 주어질 때, 정점을 두 집합으로 분할하여 잘리는 간선 수를 최대화하는 문제다. 비용 해밀토니안은 다음과 같다.

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

간선 $(i,j)$에 해당하는 비용 유니터리는 CNOT과 $R_z$ 게이트로 구현된다.

$$e^{-i\gamma \frac{1-Z_i{Z}_j}{2}}=e^{i\gamma /2}\cdot {\text{CNOT}}_{ij}\cdot R_z(2\gamma )\cdot {\text{CNOT}}_{ij}$$

믹서 유니터리는 각 큐비트에 독립적으로 $R_x(2\beta )$ 게이트를 적용한다.

from qiskit import QuantumCircuit
import numpy as np

def qaoa_maxcut_circuit(edges, n_qubits, gamma, beta):
    qc = QuantumCircuit(n_qubits)
    # 초기 상태: |+>^n
    qc.h(range(n_qubits))
    # 비용 유니터리
    for (i, j) in edges:
        qc.cx(i, j)
        qc.rz(2 * gamma, j)
        qc.cx(i, j)
    # 믹서 유니터리
    for q in range(n_qubits):
        qc.rx(2 * beta, q)
    qc.measure_all()
    return qc

edges = [(0,1), (1,2), (2,3), (3,0)]
n = 4
circuit = qaoa_maxcut_circuit(edges, n, gamma=0.4, beta=0.7)
print(circuit.draw())

고전 최적화 루프에서는 측정 결과로부터 $⟨H_C⟩$를 추정하고, COBYLA 등의 기울기-불필요(gradient-free) 최적화기로 $(\gamma ,\beta )$를 갱신한다.

기타 적용 분야

문제 유형	인코딩 방식
포트폴리오 최적화	2차 이진 최적화(QUBO)
외판원 문제(TSP)	페널티 항 추가 QUBO
그래프 색칠 문제	보조 큐비트 확장 인코딩

---

정리

QAOA는 비용 해밀토니안과 믹서 해밀토니안을 교번 적용하는 변분 회로로 조합 최적화를 수행한다. 회로 깊이 $p$는 해의 품질과 회로 복잡도 사이의 트레이드오프를 결정하는 핵심 하이퍼파라미터다. 현재의 NISQ(Noisy Intermediate-Scale Quantum) 장치에서는 낮은 $p$로 운용되며, 노이즈 저감 기법과 결합하여 실용적 이점을 탐색하는 연구가 활발하다. 고전 알고리즘 대비 양자 우위 입증은 아직 미해결 과제로 남아 있다.