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

먼저 읽으면 좋은 용어

개념 소개

조합 최적화 문제는 유한한 이진 변수 공간에서 비용 함수를 최소화(또는 최대화)하는 해를 찾는 문제군이다. 그래프 최대 절단(MaxCut), 정수 계획법, 외판원 문제 등이 대표적이며 대부분 NP-난해 클래스에 속한다. 고전 근사 알고리즘은 일정한 근사 비율을 보장하지만, 문제 규모가 커질수록 탐색 공간이 지수적으로 증가하는 한계가 있다.

**양자 근사 최적화 알고리즘(QAOA)**은 변분 회로와 고전 최적화기를 결합한 하이브리드 알고리즘이다. 비용 함수를 파울리 연산자로 인코딩한 해밀토니언을 회로에 직접 새겨 넣고, 파라미터를 고전적으로 최적화함으로써 근사 해를 산출한다.

핵심 원리

두 해밀토니언의 교대 구조

QAOA 회로는 두 유니터리를 $p$ 회 교대 적용하는 구조를 갖는다.

비용 유니터리 $U_{C} (γ_{k}) = e^{- i γ_{k} C}$
$C$ 는 최적화 목적 함수를 이징(Ising) 형태로 인코딩한 대각 연산자다.
혼합 유니터리 $U_{B} (β_{k}) = e^{- i β_{k} B}$ , $B = \sum_{i = 1}^{n} X_{i}$
탐색 공간 전반에 걸친 양자 확산 역할을 한다.

초기 상태를 균일 중첩 $∣ s ⟩ = H^{\otimes n} ∣0 ⟩^{\otimes n}$ 으로 설정하면, $p$ 층 회로의 출력 상태는 다음과 같다:

$∣ γ, β ⟩ = U_{B} (β_{p}) U_{C} (γ_{p}) \dots U_{B} (β_{1}) U_{C} (γ_{1}) ∣ s ⟩$

변분 최적화 목적 함수

고전 최적화기가 최대화하는 목적 함수는 비용 연산자의 기댓값이다:

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

파라미터 벡터 $(γ, β) \in R^{2 p}$ 는 COBYLA, SPSA, Adam 등 고전 최적화 기법으로 반복 갱신된다. $p \to \infty$ 극한에서는 정확한 최적해 수렴이 이론적으로 보장되며, $p = 1$ 에서도 MaxCut 문제에 대해 **근사 비율 $\geq 0.6924$ **가 해석적으로 유도된다.

QUBO와 이징 해밀토니언 변환

이진 변수 $z_{i} \in {0, 1}$ 을 스핀 변수 $s_{i} = 1 - 2 z_{i} \in {- 1, + 1}$ 로 치환하면, 대부분의 이진 이차 최적화(QUBO) 문제는 이징 모델 형태로 변환된다:

$C = i < j \sum J_{ij} Z_{i} Z_{j} + i \sum h_{i} Z_{i}$

예시·응용

MaxCut 문제 ( $p = 1$ )

3-노드 완전 그래프 $G$ 의 MaxCut 비용 해밀토니언은 다음과 같다:

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

Qiskit으로 구현한 $p = 1$ QAOA 회로 예시:

from qiskit import QuantumCircuit
import numpy as np

def qaoa_maxcut_p1(gamma: float, beta: float) -> QuantumCircuit:
    qc = QuantumCircuit(3)
    # 균일 중첩 초기화
    qc.h([0, 1, 2])
    # 비용 유니터리: e^{-i gamma C}
    for u, v in [(0, 1), (1, 2), (0, 2)]:
        qc.cx(u, v)
        qc.rz(2 * gamma, v)
        qc.cx(u, v)
    # 혼합 유니터리: e^{-i beta B}
    qc.rx(2 * beta, [0, 1, 2])
    qc.measure_all()
    return qc

# 고전 최적화기와 연동 시 scipy.optimize.minimize 등을 활용
qc = qaoa_maxcut_p1(gamma=0.5, beta=0.3)

실용 응용 분야

분야	문제 예시
물류	배송 경로 최적화, 작업 배정
금융	포트폴리오 선택, 위험 최소화
반도체 설계	회로 배선, 플로어플래닝
머신러닝	클러스터링, 특징 선택

IBM Quantum 및 Google Quantum AI의 초전도 큐비트 프로세서에서 소규모 QAOA 실험이 수행되었으며, 현재는 노이즈 내성과 파라미터 초기화 전략(warm-starting)이 활발히 연구되고 있다.

정리

QAOA는 비용·혼합 해밀토니언의 교대 적용과 변분 파라미터 최적화를 결합한 하이브리드 알고리즘이다. 층수 $p$ 를 증가시킬수록 해의 품질이 향상되지만 회로 깊이도 비례하여 증가하므로, NISQ 하드웨어의 노이즈 임계 내에서 $p$ 와 근사 정확도의 균형을 설계하는 것이 핵심 실용 과제다. 변분 회로의 표현력 한계(barren plateau)와 고전 최적화기의 수렴 안정성은 여전히 열린 연구 문제다.

Summary

핵심 정리

01QAOA는 비용 유니터리 $e^{-i\gamma C}$와 혼합 유니터리 $e^{-i\beta B}$를 $p$회 교대 적용하는 변분 회로 구조를 갖는다.
02초기 상태는 균일 중첩 $|+\rangle^{\otimes n}$이며, 고전 최적화기가 파라미터 $(\boldsymbol{\gamma}, \boldsymbol{\beta})$를 반복 갱신하여 비용 기댓값을 최대화한다.
03층수 $p \to \infty$ 극한에서 정확한 최적해 수렴이 보장되고, $p=1$에서도 MaxCut에 대해 0.6924 이상의 이론적 근사 비율이 성립한다.
04QUBO 형식의 조합 최적화 문제는 이징 해밀토니언으로 변환하여 QAOA에 직접 적용할 수 있다.
05barren plateau 문제와 파라미터 초기화 전략이 실용적 성능을 결정하는 중요 요인이다.
06물류, 금융, 반도체 설계 등 다양한 산업 최적화 문제에 적용 가능하다.

Exercises

연습문제

Q1MaxCut 문제에서 간선 집합 $E = \{(0,1), (1,2)\}$인 2-간선 그래프의 비용 해밀토니언 $C$를 파울리 연산자로 명시적으로 쓰시오.
힌트 보기
각 간선 $(i,j)$에 대해 $\frac{1}{2}(I - Z_i Z_j)$ 항을 구성하고 합산한다.
해설 보기
$$C = \frac{1}{2}(I \otimes I - Z_0 Z_1) + \frac{1}{2}(I \otimes I - Z_1 Z_2) = I - \frac{1}{2}Z_0 Z_1 - \frac{1}{2}Z_1 Z_2$$ 단, $Z_i$는 $i$번째 큐비트에 작용하는 파울리 $Z$ 연산자이다.
Q2QAOA의 층수 $p$를 늘릴 때 얻는 이점과 그에 따른 하드웨어 상의 비용을 설명하시오.
해설 보기
$p$가 증가하면 파라미터 공간이 풍부해져 비용 함수의 기댓값이 최적해에 가까워지고, 이론적으로는 $p \to \infty$ 에서 정확한 최적해에 수렴한다. 그러나 회로 깊이가 $O(p)$로 증가하므로 게이트 오류와 디코히런스 누적이 심화되어, 현재 NISQ 프로세서에서는 낮은 $p$ 값으로 실험이 제한된다.
Q3표준 혼합 해밀토니언 $B = \sum_i X_i$ 대신 다른 혼합 연산자를 선택해야 하는 경우를 예를 들어 설명하시오.
힌트 보기
페르미온 문제나 제약 조건이 있는 최적화 문제를 생각해보라.
해설 보기
문제에 등식 제약 조건(예: 비트 수의 합이 고정)이 있는 경우, 표준 $X$ 혼합기는 실행 가능한 해 공간(feasible subspace) 밖으로 탐색 경로를 이탈시킨다. 이때는 실행 가능 부분 공간을 보존하는 XY-혼합기나 Grover 혼합기 같은 제약 보존 혼합 연산자(constraint-preserving mixer)를 설계해야 하며, 이를 XY-QAOA 또는 Grover Mixer QAOA라 부른다.

개념 소개

핵심 원리

두 해밀토니언의 교대 구조

변분 최적화 목적 함수

QUBO와 이징 해밀토니언 변환

예시·응용

MaxCut 문제 ( $p = 1$ )

실용 응용 분야

정리

연습문제

다음으로 볼 튜토리얼

포스트양자암호(PQC) 기초: 양자 시대를 대비하는 암호 설계

PQC(포스트양자암호) 기초: 양자 시대의 암호 보안

변분 양자 고유값 계산(VQE): 원리와 구현