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

먼저 읽으면 좋은 용어

개념 소개

조합 최적화(combinatorial optimization)는 그래프 분할, 스케줄링, 포트폴리오 최적화 등 NP-난해 문제가 다수 포함된 광대한 분야다. QAOA는 이러한 이산 최적화 문제를 양자 회로로 근사 풀기 위해 제안된 변분(variational) 하이브리드 알고리즘이다. 양자 프로세서가 중첩 상태를 이용해 해 공간을 탐색하고, 고전 컴퓨터가 회로 파라미터를 반복적으로 갱신하는 협력 구조를 취한다.

핵심 원리

문제 인코딩: 비용 해밀토니안

이진 변수 $z_{i} \in {0, 1}$ 로 표현되는 목적 함수 $C (z)$ 를 계산 기저(computational basis)에서 대각인 비용 해밀토니안(cost Hamiltonian) $H_{C}$ 로 매핑한다.

$H_{C} ∣ z ⟩ = C (z) ∣ z ⟩$

이 대응 덕분에 $H_{C}$ 의 기저 상태를 측정할 때 확률이 높을수록 목적 함수 값이 좋은 해를 의미한다.

혼합 해밀토니안

해 공간 탐색은 혼합 해밀토니안(mixer Hamiltonian) $H_{B}$ 가 담당한다. 표준 선택은 각 큐비트에 파울리- $X$ 연산자를 적용하는 횡자기장 형태다.

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

$H_{B}$ 는 서로 다른 계산 기저 상태 사이의 전이를 유도함으로써 알고리즘이 국소 최적해에 갇히지 않도록 돕는다.

QAOA 회로와 변분 파라미터

깊이(depth) $p$ 의 QAOA 회로는 균등 중첩 상태 $∣ + ⟩^{\otimes n}$ 에서 출발해 비용 게이트와 혼합 게이트를 $p$ 회 교번 적용한다.

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

여기서 $γ = (γ_{1}, \dots, γ_{p})$ , $β = (β_{1}, \dots, β_{p})$ 는 고전 옵티마이저가 조정하는 변분 파라미터다. 목적 함수는 기댓값

$F_{p} (γ, β) = ⟨ γ, β ∣ H_{C} ∣ γ, β ⟩$

를 최대화(또는 최소화)하도록 설정한다. 이론적으로 $p \to \infty$ 극한에서 QAOA는 정확한 최적해에 수렴함이 보장되어 있다.

고전-양자 피드백 루프

현재 파라미터 $(γ, β)$ 로 양자 회로를 실행해 $F_{p}$ 기댓값을 측정한다.
고전 옵티마이저(COBYLA, SPSA, 경사 하강법 등)가 기댓값을 바탕으로 파라미터를 갱신한다.
수렴 조건이 만족될 때까지 반복한다.

예시·응용

MaxCut 문제

MaxCut은 QAOA의 대표 벤치마크다. 그래프 $G = (V, E)$ 의 정점을 두 집합으로 나눌 때, 두 집합을 가로지르는 간선 수를 최대화하는 문제다. 비용 해밀토니안은

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

으로 표현된다. $Z_{i} Z_{j} = - 1$ 이면 두 큐비트가 다른 집합에 속해 해당 간선이 잘린 것을 의미한다.

아래는 Qiskit을 이용한 4-노드 MaxCut QAOA의 개략적 구현이다.

import networkx as nx
from qiskit_optimization.applications import Maxcut
from qiskit_optimization.converters import QuadraticProgramToQubo
from qiskit_optimization.algorithms import MinimumEigenOptimizer
from qiskit_algorithms import QAOA
from qiskit_algorithms.optimizers import COBYLA
from qiskit.primitives import Sampler

G = nx.cycle_graph(4)                        # 4-노드 순환 그래프
qp = Maxcut(G).to_quadratic_program()
qubo = QuadraticProgramToQubo().convert(qp)

qaoa = QAOA(sampler=Sampler(),
            optimizer=COBYLA(maxiter=300),
            reps=2)                           # p = 2 레이어
result = MinimumEigenOptimizer(qaoa).solve(qubo)
print(result)

성능 보장과 한계

$p = 1$ 단일 레이어 QAOA는 MaxCut에 대해 근사비(approximation ratio) $\geq 0.6924$ 임이 이론적으로 알려져 있다. 그러나 $p$ 가 커질수록 파라미터 최적화의 경관(landscape)이 평탄해지는 배럿 플래토(barren plateau) 문제와 노이즈 누적이 실질적인 장벽이 된다. NISQ 환경에서의 실제 양자 이점 존재 여부는 현재도 활발히 연구 중인 열린 문제다.

정리

QAOA는 비용 해밀토니안과 혼합 해밀토니안을 교번 적용하는 $p$ -레이어 변분 회로를 핵심 구조로 삼는 하이브리드 최적화 알고리즘이다. 회로 깊이 $p$ 가 커질수록 이론적 근사 품질이 향상되지만, 노이즈와 최적화 비용도 함께 증가한다. MaxCut을 비롯한 이산 최적화 문제에서 NISQ 시대의 실용적 알고리즘 후보로 평가받으며, 혼합 해밀토니안 설계·파라미터 초기화 전략·오류 경감 기법 등이 현재의 핵심 연구 과제다.

Exercises

연습문제

Q13개의 정점과 3개의 간선으로 이루어진 완전 그래프 $K_3$(삼각형)에 대해 MaxCut 비용 해밀토니안 $H_C$를 파울리 연산자로 명시적으로 적어라.
힌트 보기
각 간선 $(i,j)$에 대해 $\frac{1}{2}(I - Z_i Z_j)$를 합산하면 된다. 정점 인덱스 0, 1, 2로 간선 세 개를 나열해 보라.
해설 보기
간선 집합 $E = \{(0,1),(1,2),(0,2)\}$이므로 $$H_C = \frac{1}{2}(I - Z_0 Z_1) + \frac{1}{2}(I - Z_1 Z_2) + \frac{1}{2}(I - Z_0 Z_2)$$이다. 최대 분할은 정점 하나를 한 집합에, 나머지 둘을 반대 집합에 놓을 때이며 MaxCut 값은 2이다.
Q2QAOA에서 혼합 해밀토니안 $H_B = \sum_i X_i$가 필요한 이유를 비용 해밀토니안의 구조적 특성과 연관지어 설명하라.
해설 보기
$H_C$는 계산 기저 $\{|0\rangle, |1\rangle\}^{\otimes n}$에서 대각 행렬이므로, $e^{-i\gamma H_C}$만으로는 서로 다른 기저 상태 사이의 확률 진폭을 섞을 수 없다. 즉 초기 균등 중첩에서 출발해도 모든 기저 상태의 위상만 바뀔 뿐, 확률 분포가 변하지 않는다. $H_B$는 $X$ 연산자로 기저 상태 간 전이(transition)를 유도해 회로가 다양한 해 후보를 탐색하도록 만든다.
Q3QAOA 회로의 깊이 $p$를 늘리면 이론적 성능은 향상되지만 실용적으로는 문제가 발생할 수 있다. 그 두 가지 대표적 이유를 설명하라.
해설 보기
① **배럿 플래토(barren plateau)**: $p$가 커지면 파라미터 공간에서 기댓값의 경사(gradient)가 지수적으로 작아져 고전 옵티마이저가 최적 방향을 찾기 어려워진다. ② **노이즈 누적**: NISQ 하드웨어에서는 게이트 오류와 결잃음(decoherence)이 레이어가 깊어질수록 누적되어 회로 출력 신뢰도가 급격히 저하된다. 두 효과 모두 얕은 회로($p$가 작은 경우)를 선호하게 만드는 현실적 제약이다.