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

개념 소개

조합 최적화 문제는 유한한 후보 집합에서 비용 함수를 최소(또는 최대)화하는 해를 찾는 문제다. 변수 수 $n$이 커질수록 탐색 공간이 $2^n$으로 팽창하므로, 고전 알고리즘으로 최적해를 보장하기 어렵다. QAOA는 이 탐색 공간을 양자 중첩으로 동시에 표현하고, 양자 간섭을 통해 좋은 해의 확률 진폭을 증폭하는 전략을 취한다.

알고리즘은 두 구성 요소로 이루어진다.

1. 양자 회로: 매개변수화된 게이트 층을 $p$회 반복 적용해 변분 상태 $|\mathbf{\gamma },\mathbf{\beta }⟩$를 준비한다.
2. 고전 최적화기: 측정에서 추정한 비용 기댓값 $⟨H_C⟩$를 고전 루프에서 최소화한다.

이 구조는 VQE와 동일한 변분 양자 알고리즘(VQA) 패러다임에 속하며, NISQ 시대의 핵심 응용 후보로 꼽힌다.

---

핵심 원리

비용 해밀토니안

이진 변수 $z_i\in \{0,1\}$로 표현되는 비용 함수 $C(\mathbf{z})$를 파울리 $Z$ 연산자로 매핑한다. 일반적인 QUBO(Quadratic Unconstrained Binary Optimization) 형식에서

$$H_C=\sum _{⟨i,j⟩}{J}_{ij}{Z}_i{Z}_j+\sum _i{h}_i{Z}_i$$

로 쓴다. $H_C$의 최소 고유벡터가 최적해에 대응한다.

믹서 해밀토니안

믹서는 탐색 공간 전체를 고르게 탐색하도록 섞는 역할을 한다. 표준 선택은

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

이며, $X_i$는 큐비트 $i$에 작용하는 파울리 $X$다.

회로 구성 및 변분 최적화

초기 상태를 균일 중첩

$$|s⟩=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 }⟩=\prod _{k=1}^p{e}^{-i{\beta }_k{H}_B}{e}^{-i{\gamma }_k{H}_C}|s⟩$$

매개변수 벡터 $\mathbf{\gamma },\mathbf{\beta }\in {\mathbb{R}}^p$를 고전 최적화기(COBYLA, L-BFGS-B 등)로 튜닝해

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

를 구한다. 수렴 후 최적 회로를 반복 측정해 가장 빈번한 비트열을 근사 최적해로 채택한다.

근사율과 $p$의 역할

$p=1$일 때 MaxCut 문제에 대해 근사율 $\alpha \ge 0.6924$ 이상이 수학적으로 증명된다. $p$가 커질수록 QAOA는 단열 양자 계산(AQC)의 트로터 근사에 수렴하며, $p\to \infty$ 극한에서 정확해를 보장한다. 그러나 NISQ 장치에서는 회로 깊이 증가가 잡음 누적을 초래하므로 실용적 $p$는 수 십 이하로 제한된다.

---

예시·응용

MaxCut 문제

그래프 $G=(V,E)$에서 정점 집합을 두 부분 $S,\bar{S}$로 나눌 때, 두 집합을 연결하는 간선 수를 최대화하는 MaxCut은 QAOA의 표준 벤치마크다.

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

$p=1$, 3-정규 그래프에서 최적 매개변수는 ${\gamma }^{\ast }=\pi /8$, ${\beta }^{\ast }=\pi /8$으로 해석적으로 알려져 있다.

Qiskit을 활용한 $p=1$ 구현

from qiskit import QuantumCircuit
import numpy as np

def qaoa_maxcut_p1(edges, n, gamma, beta):
    qc = QuantumCircuit(n)
    qc.h(range(n))                       # 균일 중첩 초기화
    for (i, j) in edges:                 # 비용 유니터리
        qc.cx(i, j)
        qc.rz(2 * gamma, j)
        qc.cx(i, j)
    for i in range(n):                   # 믹서 유니터리
        qc.rx(2 * beta, i)
    qc.measure_all()
    return qc

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

cx–rz–cx 패턴이 $e^{-i\gamma Z_i{Z}_j}$ 게이트를 구현하며, rx가 믹서를 담당한다.

다른 응용 분야

문제 유형	핵심 QUBO 구조
포트폴리오 최적화	분산 최소화 + 수익률 제약
작업 스케줄링	자원 충돌 페널티 항
정수 인수분해	곱 오차의 이차 이진 전개
약물 분자 도킹	접촉 에너지 이진 매핑

어떤 조합 최적화 문제든 QUBO 형식으로 변환하면 QAOA를 바로 적용할 수 있다.

---

정리

QAOA는 비용·믹서 해밀토니안의 교대 적용으로 문제 구조를 양자 회로에 인코딩하고, 고전 최적화 루프로 변분 매개변수를 탐색한다. 깊이 $p$를 높이면 해의 품질이 향상되나, NISQ 잡음과의 균형이 현실적 제약이다. 현재 연구는 잡음 강건 매개변수 초기화, 워밍스타트(warm-starting), 문제 특화 믹서 설계 등을 통해 실용적 양자 우위 확보를 목표로 하고 있다.