먼저 읽으면 좋은 용어
개념 소개
QAOA는 조합 최적화 문제의 근사 해를 양자 컴퓨터에서 탐색하는 변분형 하이브리드 알고리즘이다. 이진 변수로 정의된 목적함수를 해밀토니안으로 인코딩하고, 파라미터화된 양자 회로가 해 공간을 탐색하는 동안 고전 최적화기가 파라미터를 반복 갱신한다.
이 알고리즘은 아디아배틱 양자 계산(Adiabatic Quantum Computation)의 게이트 모델 대응물로 이해할 수 있다. MaxCut, 포트폴리오 최적화, 스케줄링처럼 NP-난해(NP-hard)에 속하는 문제들이 주요 적용 대상이며, 단기 잡음 허용 양자 장치(NISQ)에서 실행 가능한 현실적인 후보 알고리즘으로 주목받는다.
핵심 원리
비용 해밀토니안
목적함수 를 파울리 Z 연산자로 인코딩한 해밀토니안이다. 개의 이진 변수 를 스핀 로 매핑하면 일반적인 QUBO 형태는 다음과 같다.
의 기저 상태(ground state)가 곧 최적해에 대응하므로, 문제는 기저 상태 탐색으로 환원된다.
믹서 해밀토니안
각 큐비트에 X 회전을 가해 해 공간 전체를 균등하게 탐색하도록 유도하는 역할을 한다.
QAOA 회로 구조
깊이 파라미터 에 따라 두 유니터리를 교대 적용한다.
초기 상태 에서 출발해 QAOA 상태를 구성한다.
파라미터 벡터 는 기대값
를 최대화하도록 고전 최적화기가 반복 갱신한다. 극한에서는 아디아배틱 정리에 의해 정확한 최적해 수렴이 보장된다.
근사 비율
에서 MaxCut 문제에 대해 QAOA는 근사 비율 를 이론적으로 달성함이 증명되어 있다. 고전 Goemans-Williamson SDP 알고리즘()보다 낮지만, 양자 하드웨어에서 직접 실행 가능한 근사 보장이라는 점에서 의미를 갖는다.
예시·응용
MaxCut 비용 해밀토니안
그래프 에서 정점 집합을 두 부분으로 나눠 경계 간선 수를 최대화하는 문제의 비용 해밀토니안은 다음과 같다.
간선 에 대응하는 는 ZZ 결합 게이트 로 구현된다.
Qiskit 구현 예시 (p=1, 4-노드 링)
from qiskit import QuantumCircuit
from qiskit.circuit import Parameter
def qaoa_maxcut_p1(edges, n_qubits):
gamma = Parameter('γ')
beta = Parameter('β')
qc = QuantumCircuit(n_qubits)
# 초기 상태 |+>^n
qc.h(range(n_qubits))
# Cost unitary: exp(-i γ H_C)
for (i, j) in edges:
qc.cx(i, j)
qc.rz(2 * gamma, j)
qc.cx(i, j)
# Mixer unitary: exp(-i β H_B)
qc.rx(2 * beta, range(n_qubits))
qc.measure_all()
return qc
edges = [(0,1), (1,2), (2,3), (3,0)] # 4-노드 링
qc = qaoa_maxcut_p1(edges, n_qubits=4)
고전 최적화기(예: COBYLA, BFGS)로 γ, β를 탐색한 뒤 측정값 분포에서 최빈 비트열을 근사 해로 채택한다.
응용 분야
- 포트폴리오 최적화: 자산 선택을 QUBO로 변환해 QAOA 적용
- 물류·스케줄링: 경로 배정, 작업 할당의 이진 최적화
- 머신러닝: 클러스터링, 특성 선택의 조합 탐색
실용적 도전 과제
현재 NISQ 장치에서 QAOA의 실용성은 다음 요인에 의해 제한된다. 첫째, 파라미터 랜드스케이프의 평탄화(barren plateau) 문제로 경사 기반 최적화가 어려워진다. 둘째, 가 커질수록 회로 깊이가 증가해 잡음 축적이 심화된다. 셋째, 고전 최적화기와 양자 회로 간 반복 통신 오버헤드가 실행 시간을 늘린다.
정리
QAOA는 비용 해밀토니안 와 믹서 해밀토니안 를 교대 적용하는 층 변분 회로로 조합 최적화 문제를 근사 해결한다. 층수 가 증가할수록 근사 품질이 향상되고 에서 정확해 수렴이 보장되지만, 현실 장치에서는 잡음과 barren plateau가 주요 병목이다. NISQ 시대의 대표적 변분 하이브리드 알고리즘으로서, 양자 우위 가능성과 실용적 한계에 대한 연구가 지속되고 있다.
Exercises
연습문제
Q1QAOA 회로에서 초기 상태로 $|+\rangle^{\otimes n}$을 선택하는 이유를 설명하고, 만약 $|0\rangle^{\otimes n}$을 초기 상태로 사용하면 어떤 문제가 발생하는지 논하라.
힌트 보기
믹서 해밀토니안 $H_B = \sum_i \sigma_i^x$의 기저 상태가 무엇인지 생각해 보라. 또한 $p=1$에서 cost unitary만 적용했을 때 $|0\rangle^{\otimes n}$이 어떻게 변화하는지 추적해 보라.
해설 보기
$|+\rangle^{\otimes n}$은 $H_B$의 기저 상태이자 모든 계산 기저 상태의 균등 중첩이다. 이 상태에서 출발해야 $U(H_C,\gamma)$가 모든 후보 해에 위상을 고르게 부여하고, 이후 $U(H_B,\beta)$가 의미 있는 간섭을 만들어낸다. $|0\rangle^{\otimes n}$에서 시작하면 $U(H_C,\gamma)|0\rangle^{\otimes n} = e^{-i\gamma C(0\cdots0)}|0\rangle^{\otimes n}$으로 전역 위상만 변하며, 이후 믹서가 일부 상태를 탐색하겠지만 초기 편향이 최적화 효율을 크게 저하시킨다.
Q24개의 노드와 간선 집합 $E=\{(0,1),(1,2),(2,3),(3,0)\}$로 이루어진 링 그래프에 대해 MaxCut 비용 해밀토니안 $H_C$를 파울리 연산자로 명시적으로 표현하라. (단, $\sigma_i^z$를 $Z_i$로 표기한다.)
해설 보기
MaxCut 비용 해밀토니안은 $H_C = \frac{1}{2}\sum_{(i,j)\in E}(1 - Z_iZ_j)$이므로, $$H_C = \frac{1}{2}\bigl[(1-Z_0Z_1)+(1-Z_1Z_2)+(1-Z_2Z_3)+(1-Z_3Z_0)\bigr] = 2\,I - \frac{1}{2}(Z_0Z_1+Z_1Z_2+Z_2Z_3+Z_3Z_0).$$ 최대 절단값은 4(모든 간선 절단)이며, 예를 들어 $|0101\rangle$ 또는 $|1010\rangle$이 최적 해다. 해당 비트열에서 $H_C$의 기대값을 계산하면 고유값 4를 얻음을 확인할 수 있다.
Q3QAOA의 층수 $p$를 무한히 늘리면 이론적으로 정확한 최적해가 보장된다. 그렇다면 현실적으로 $p$를 크게 설정하기 어려운 이유를 하드웨어 관점에서 두 가지 이상 서술하라.
해설 보기
(1) **회로 깊이와 잡음**: $p$가 증가하면 게이트 수가 $O(p \cdot |E|)$로 선형 증가한다. 현재 NISQ 장치의 게이트 오류율(~0.1–1%)로 인해 회로 깊이가 늘어날수록 오류가 누적되어 측정 결과의 신뢰도가 급락한다. (2) **디코히어런스**: 양자 상태의 결맞음 시간(coherence time)이 유한하므로, 회로 실행 시간이 이를 초과하면 상태가 붕괴된다. (3) **파라미터 최적화 어려움**: 파라미터 공간 $\mathbb{R}^{2p}$의 차원이 커질수록 경사 기반 탐색이 barren plateau에 빠질 가능성이 높아지고, 고전 최적화의 수렴이 느려진다.
관련 용어
