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

먼저 읽으면 좋은 용어

개념 소개

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

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

양자 회로: 매개변수화된 게이트 층을 $p$ 회 반복 적용해 변분 상태 $∣ γ, β ⟩$ 를 준비한다.
고전 최적화기: 측정에서 추정한 비용 기댓값 $⟨ H_{C} ⟩$ 를 고전 루프에서 최소화한다.

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

핵심 원리

비용 해밀토니안

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

$H_{C} = ⟨ i, j ⟩ \sum J_{ij} Z_{i} Z_{j} + i \sum h_{i} Z_{i}$

로 쓴다. $H_{C}$ 의 최소 고유벡터가 최적해에 대응한다.

믹서 해밀토니안

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

$H_{B} = i = 1 \sum n X_{i}$

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

회로 구성 및 변분 최적화

초기 상태를 균일 중첩

$∣ s ⟩ = H^{\otimes n} ∣0 ⟩^{\otimes n} = \frac{1}{2 ^{n}} z \in {0, 1}^{n} \sum ∣ z ⟩$

으로 설정한 뒤, 깊이 $p$ 의 교대 유니터리 층을 적용한다.

$∣ γ, β ⟩ = k = 1 \prod p e^{- i β_{k} H_{B}} e^{- i γ_{k} H_{C}} ∣ s ⟩$

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

$(γ^{*}, β^{*}) = ar g γ, β min ⟨ γ, β ∣ H_{C} ∣ γ, β ⟩$

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

근사율과 $p$ 의 역할

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

예시·응용

MaxCut 문제

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

$H_{C}^{MaxCut} = \frac{1}{2} (i, j) \in E \sum (I - Z_{i} Z_{j})$

$p = 1$ , 3-정규 그래프에서 최적 매개변수는 $γ^{*} = π /8$ , $β^{*} = π /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γ Z_{i} Z_{j}}$ 게이트를 구현하며, rx가 믹서를 담당한다.

다른 응용 분야

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

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

정리

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

Summary

핵심 정리

01QAOA는 비용 해밀토니안 $H_C$와 믹서 해밀토니안 $H_B$를 교대로 적용하는 변분 양자 알고리즘이다.
02초기 상태는 균일 중첩 $|s\rangle = H^{\otimes n}|0\rangle^{\otimes n}$이며, 매개변수 $(\boldsymbol{\gamma}, \boldsymbol{\beta})$를 고전 최적화기로 튜닝한다.
03회로 깊이 $p=1$에서 MaxCut의 근사율 $\geq 0.6924$이 수학적으로 보장되며, $p \to \infty$에서 정확해에 수렴한다.
04대부분의 조합 최적화 문제는 QUBO 형식으로 변환해 QAOA에 적용할 수 있다.
05NISQ 장치에서는 회로 깊이 증가에 따른 잡음 누적이 실용적 $p$ 선택의 핵심 제약이다.
06`cx–rz–cx` 구조가 $e^{-i\gamma Z_i Z_j}$ 게이트를 구현하며, `rx`가 표준 믹서를 담당한다.

Exercises

연습문제

Q1삼각형 그래프 $G = (\{0,1,2\},\, \{(0,1),(1,2),(0,2)\})$에 대해 $p=1$ QAOA의 비용 해밀토니안 $H_C^{\text{MaxCut}}$을 파울리 연산자로 명시적으로 써라.
힌트 보기
MaxCut 비용 해밀토니안 공식 $H_C = \frac{1}{2}\sum_{(i,j)\in E}(I - Z_iZ_j)$에 세 간선을 대입한다.
해설 보기
$$H_C = \frac{1}{2}\bigl[(I - Z_0 Z_1) + (I - Z_1 Z_2) + (I - Z_0 Z_2)\bigr]$$ $= \frac{3}{2}I - \frac{1}{2}(Z_0Z_1 + Z_1Z_2 + Z_0Z_2)$. 최대 컷 크기는 2(세 간선 중 두 개)이므로 이 $H_C$의 최솟값은 $-1$, 최댓값은 $+1$이고, 정확한 MaxCut 값은 $\langle H_C \rangle_{\max} = 1$에 대응한다.
Q2QAOA에서 믹서 해밀토니안 $H_B = \sum_i X_i$를 사용하는 이유를 대칭성 관점에서 설명하라.
해설 보기
표준 $H_B$는 모든 큐비트에 $X$ 회전을 균등하게 적용해, 초기 균일 중첩 $|s\rangle$을 $H_C$의 고유벡터 기저와 비가환(non-commuting) 상태로 유지한다. 이 비가환성이 비용 지형을 가로지르는 양자 터널링 역할을 하며, $H_B$와 $H_C$가 가환이면 중첩 탐색이 불가능해 알고리즘이 퇴화한다. 또한 $H_B$는 문제 해밀토니안에 무관하므로 범용 믹서로 사용하기 편리하다.
Q3동일한 조합 최적화 문제를 QAOA($p=1$)와 고전 무작위 알고리즘(무작위 이분할)으로 풀 때, MaxCut에서 각각의 기대 근사율을 비교하고, QAOA의 우위가 명확히 드러나지 않는 이유를 논하라.
해설 보기
무작위 이분할은 각 정점을 독립적으로 확률 1/2로 분류하므로 기대 컷 크기가 $|E|/2$, 즉 근사율 0.5다. QAOA $p=1$은 최악 경우 0.6924를 보장해 수학적으로 우위다. 그러나 실제 NISQ 장치에서는 (1) 게이트 잡음이 기댓값 추정을 오염시키고, (2) 매개변수 최적화에 수백~수천 번의 회로 실행이 필요해 총 연산 비용이 커지며, (3) Goemans-Williamson SDP 알고리즘이 동일 문제에 근사율 0.878을 달성하므로 고전 방법 대비 양자 우위가 아직 명확하지 않다.