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

개념 소개

조합 최적화(combinatorial optimization)란 유한한 이산 선택지 집합에서 목적 함수를 최대화하거나 최소화하는 해를 찾는 문제다. 그래프 분할, 스케줄링, 포트폴리오 배분, 최단 경로 탐색 등이 대표적이며, 이 중 상당수가 NP-난해(NP-hard)에 속한다. 입력 크기가 증가할수록 고전 알고리즘의 정확 해 탐색에 지수적 자원이 필요해진다.

QAOA(Quantum Approximate Optimization Algorithm)는 이 문제 구조를 양자 회로에 직접 인코딩한 뒤, 고전 최적화기가 회로 파라미터를 반복 조정하는 양자-고전 하이브리드 루프를 통해 근사해를 구한다. 정확한 최적해 대신 "충분히 좋은" 해를 빠르게 찾는다는 점에서, 현재의 잡음 중규모 양자(NISQ) 장치에 적합하게 설계된 변분 알고리즘이다.

---

핵심 원리

문제의 해밀토니안 인코딩

조합 최적화 문제의 이진 변수 $z_i\in \{0,1\}$는 큐비트의 파울리 $Z$ 연산자 고유값 $\{+1,-1\}$에 대응된다. 목적 함수 $C(\mathbf{z})$를 최대화하는 문제는 비용 해밀토니안

$$H_C=\sum _{\alpha }{C}_{\alpha }$$

로 표현되며, 각 항 $C_{\alpha }$는 파울리 $Z$ 연산자들의 텐서곱으로 구성된다. 최적해는 $H_C$의 최대 고유값에 대응하는 고유벡터다.

탐색 공간을 균일하게 탐색하기 위한 믹서 해밀토니안으로는 표준적으로

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

를 사용한다. $H_B$의 역할은 해 후보들 사이의 전이를 가능하게 하는 것이다.

QAOA 회로 구조

깊이 $p$의 QAOA 회로는 두 유니터리를 교대로 $p$회 적용한다:

$$U(H_C,{\gamma }_k)=e^{-i{\gamma }_k{H}_C},U(H_B,{\beta }_k)=e^{-i{\beta }_k{H}_B}$$

초기 상태는 모든 큐비트에 아다마르 게이트를 적용한 균등 중첩이다:

$$|{\psi }_0⟩=H^{\otimes n}|0{⟩}^{\otimes n}=\frac{1}{\sqrt{2^n}}\sum _{\mathbf{z}\in \{0,1{\}}^n}|\mathbf{z}⟩$$

$p$층 적용 후 최종 상태는

$$|\mathbf{\gamma },\mathbf{\beta }⟩=U(H_B,{\beta }_p)U(H_C,{\gamma }_p)\cdots U(H_B,{\beta }_1)U(H_C,{\gamma }_1)|{\psi }_0⟩$$

이며, 목적 함수의 기댓값

$$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$ 극한에서 QAOA는 단열 양자 계산(adiabatic quantum computation)과 동치가 되어 최적해로 수렴한다. 유한 $p$에서의 근사율(approximation ratio)은 문제 구조와 $p$에 의존하며, $p$를 늘릴수록 단조 비감소한다.

---

예시·응용

MaxCut: 대표 벤치마크

그래프 $G=(V,E)$에서 꼭짓점 집합을 두 부분집합 $S$, $\bar{S}$로 분할할 때, 두 집합을 잇는 절단 간선 수를 최대화하는 MaxCut 문제가 QAOA의 표준 예제다.

비용 해밀토니안은

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

이다. 간선 $(i,j)$가 서로 다른 부분집합에 있을 때($z_i\ne z_j$) 기여값이 1이 된다. 각 간선에 대응하는 유니터리 $e^{-i\gamma Z_i{Z}_j/2}$는 CNOT + $R_Z$ 조합으로 구현된다.

from qiskit import QuantumCircuit
import numpy as np

def qaoa_maxcut_p1(edges, n, gamma, beta):
    """p=1 QAOA MaxCut 회로"""
    qc = QuantumCircuit(n)
    # 균등 중첩 초기화
    qc.h(range(n))
    # 비용 유니터리: e^{-i gamma Z_i Z_j / 2}
    for (i, j) in edges:
        qc.cx(i, j)
        qc.rz(2 * gamma, j)
        qc.cx(i, j)
    # 믹서 유니터리: e^{-i beta X_k}
    for k in range(n):
        qc.rx(2 * beta, k)
    qc.measure_all()
    return qc

# 4-꼭짓점 사이클 그래프
edges = [(0,1), (1,2), (2,3), (3,0)]
qc = qaoa_maxcut_p1(edges, n=4, gamma=np.pi/4, beta=np.pi/8)

실용 응용 분야

분야	문제 유형
물류·운송	차량 경로 최적화(VRP)
금융	포트폴리오 배분, 리스크 최소화
재료 과학	분자 구조·에너지 최적화
머신러닝	클러스터링, 피처 선택

IBM, Google 등의 초전도 양자 프로세서에서 낮은 $p$의 QAOA 회로가 실험적으로 실행되고 있다.

---

정리

QAOA는 비용 해밀토니안 $H_C$와 믹서 해밀토니안 $H_B$를 교대 적용하는 파라미터화 양자 회로로, 조합 최적화 문제의 근사해를 변분적으로 탐색한다. 층수 $p$를 늘릴수록 해의 질이 향상되지만, 파라미터 수 증가와 함께 바렌 고원(barren plateau) — 기울기가 지수적으로 소실되는 현상 — 이 발생할 수 있어 파라미터 초기화 전략이 중요하다. NISQ 환경에서의 실질적 양자 이점은 현재 활발히 연구 중이며, 변분 양자 알고리즘 전체의 핵심 사례로 이론·실험 양면에서 주목받고 있다.