Definition
선형 연립방정식 Ax = b의 해를 양자 컴퓨터로 지수적으로 빠르게 구하는 알고리즘. 2009년 Harrow, Hassidim, Lloyd가 제안했으며 양자 머신러닝·최적화 분야의 핵심 서브루틴으로 활용된다.
HHL 알고리즘
(1) 직관적 비유
고전 컴퓨터가 복잡한 방정식 시스템을 풀 때 '모든 방정식을 하나씩 순서대로 처리하는 계산원'이라면, HHL은 양자 중첩을 이용해 모든 방정식을 동시에 처리하는 병렬 계산원 집단에 비유할 수 있다. 단, 최종 답은 '전체 해 벡터'가 아니라 특정 기댓값 형태로만 읽어낼 수 있다는 점이 핵심 제약이다.
(2) 엄밀한 정의
$N \times N$ 희소(sparse) 행렬 $A$와 벡터 $|b\rangle$이 주어질 때, 해 $|x\rangle \propto A^{-1}|b\rangle$을 준비하는 알고리즘이다. 주요 단계:
- 양자 위상 추정(QPE) — $A$의 고유값 $\lambda_j$를 보조 레지스터에 인코딩
- 조건부 회전 — 보조 큐비트에 $\lambda_j^{-1}$에 비례하는 회전 적용
- 비측정 소거(uncompute) — 보조 레지스터 초기화 후 해 상태 추출
고전 알고리즘의 복잡도 $O(N\kappa)$ 대비, HHL은 $O(\log N \cdot \kappa^2 / \epsilon)$을 달성한다. 여기서 $\kappa$는 조건수, $\epsilon$은 허용 오차이다.
(3) 중요성·응용
- 양자 머신러닝: 최소제곱 회귀, SVM 커널 연산의 서브루틴
- 유한요소법(FEM): 대규모 물리 시뮬레이션의 선형계 풀기
- 포트폴리오 최적화: 금융 최적화 문제의 양자 가속
HHL은 '양자 우위 가능성'을 이론적으로 입증한 대표 알고리즘으로, 양자 선형 대수 전반의 이정표로 평가받는다.
