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

개념 소개

조합 최적화 문제는 유한한 이진 결정 변수의 조합 중 목적함수를 최대화·최소화하는 해를 찾는 문제다. MaxCut, 외판원 문제(TSP), 포트폴리오 최적화 등이 대표 예시이며, 변수 수가 늘수록 고전 탐색 공간이 지수적으로 증가한다.

QAOA는 양자 단열 계산(quantum adiabatic computation)을 이산화한 구조에서 출발한 변분 알고리즘이다. 양자 회로가 파라미터를 받아 기댓값을 계산하면, 고전 옵티마이저가 그 파라미터를 갱신하는 하이브리드 루프를 형성한다. 회로 깊이 $p$를 늘릴수록 해의 질이 향상되며, $p\to \infty$ 극한에서 전역 최적해에 수렴함이 이론적으로 보장된다.

---

핵심 원리

비용 해밀토니안과 혼합 해밀토니안

$n$개의 이진 변수 $z_i\in \{0,1\}$로 정의되는 목적함수 $C(\mathbf{z})$를 파울리 $Z$ 연산자로 인코딩한 비용 해밀토니안 $H_C$를 구성한다. MaxCut 문제의 경우 그래프의 각 에지 $(i,j)$에 대해

$$H_C=\sum _{⟨i,j⟩}{w}_{ij}\frac{I-Z_i{Z}_j}{2}$$

$H_C$의 최대 고유상태가 그래프를 최대로 절단하는 분할에 해당한다.

혼합 해밀토니안 $H_B$는 탐색 공간을 골고루 탐색하도록 상태를 뒤섞는 역할을 하며, 기본형으로 가로방향 자기장 항을 사용한다.

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

QAOA 회로 구조

깊이 $p$의 QAOA는 $2p$개의 각도 파라미터 $\mathbf{\gamma }=({\gamma }_1,\dots ,{\gamma }_p)$, $\mathbf{\beta }=({\beta }_1,\dots ,{\beta }_p)$를 갖는다. 초기 상태로 균등 중첩

$$|s⟩=H^{\otimes n}|0{⟩}^{\otimes n}$$

을 준비한 뒤, 비용 유니터리와 혼합 유니터리를 $p$회 교대 적용한다.

$$|\mathbf{\gamma },\mathbf{\beta }⟩=U_B({\beta }_p)U_C({\gamma }_p)\cdots U_B({\beta }_1)U_C({\gamma }_1)|s⟩$$

여기서 두 유니터리는 각 해밀토니안의 시간 발전 연산자다.

$$U_C({\gamma }_k)=e^{-i{\gamma }_k{H}_C},U_B({\beta }_k)=e^{-i{\beta }_k{H}_B}$$

파라미터 최적화

목표는 비용 해밀토니안의 기댓값을 최대화하는 파라미터를 찾는 것이다.

$$F_p(\mathbf{\gamma },\mathbf{\beta })=⟨\mathbf{\gamma },\mathbf{\beta }|H_C|\mathbf{\gamma },\mathbf{\beta }⟩⟶\max$$

고전 옵티마이저(COBYLA, BFGS, Adam 등)가 양자 측정 결과를 피드백 받아 파라미터를 반복 갱신한다. 이 하이브리드 루프가 QAOA의 핵심이다.

---

예시·응용

MaxCut (3-노드 그래프, $p=1$)

노드 {0, 1, 2}와 에지 {(0,1), (1,2)}를 갖는 그래프의 QAOA 회로를 Qiskit으로 구현한다.

from qiskit import QuantumCircuit
from qiskit.circuit import Parameter
from qiskit.primitives import StatevectorSampler
import numpy as np

gamma = Parameter('γ')
beta  = Parameter('β')
n = 3
edges = [(0, 1), (1, 2)]

qc = QuantumCircuit(n)

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

# 비용 유니터리 U_C(γ): 각 에지에 ZZ 결합
for i, j in edges:
    qc.cx(i, j)
    qc.rz(2 * gamma, j)
    qc.cx(i, j)

# 혼합 유니터리 U_B(β): 각 큐비트에 RX
for i in range(n):
    qc.rx(2 * beta, i)

qc.measure_all()

# γ=π/4, β=π/8 으로 바인딩 후 실행
bound = qc.assign_parameters({gamma: np.pi/4, beta: np.pi/8})
print(bound.draw())

파라미터 최적화 후 측정에서 가장 높은 확률을 보이는 비트열이 근사 최적해가 된다. 이 예시의 이론적 최적 절단 값은 2이며, $p=1$에서도 높은 근사비를 달성한다.

실제 응용 분야

분야	문제 예시
물류·스케줄링	차량 경로 최적화, 작업 배정
금융	포트폴리오 리밸런싱, 리스크 분산
통신	네트워크 분할, 주파수 할당
재료 과학	분자 구조 에너지 최소화

IBM Quantum, Google Quantum AI 등에서 다양한 규모의 QAOA 벤치마킹 실험이 수행되고 있다.

---

정리

QAOA는 비용 해밀토니안과 혼합 해밀토니안의 교대 적용으로 조합 최적화의 해 공간을 탐색하는 변분 알고리즘이다. 회로 깊이 $p$를 높일수록 해의 질이 향상되고 이론적으로 전역 최적해에 수렴하지만, NISQ 기기의 잡음, 파라미터 최적화의 barren plateau 문제, 고전 시뮬레이션과의 우위 입증 등이 실용화의 주요 과제로 남아 있다. 오류 경감 기법, 더 나은 초기화 전략, 문제별 특화 혼합 연산자 설계를 통해 지속적으로 발전 중인 분야다.