HHL은 선형방정식 $A x=b$를 양자상태 수준에서 푸는 알고리즘입니다. 유명하지만 조건이 까다롭고, 결과 전체 벡터를 읽는 알고리즘이 아니라는 점을 분명히 해야 합니다.
## 목표 {#goal}
Hermitian 행렬 $A$와 정규화된 입력 상태 $|b\rangle$가 있을 때, 목표는 아래 상태를 준비하는 것입니다.
$$
|x\rangle
\propto
A^{-1}|b\rangle
$$
고전적인 해 벡터 $x$의 모든 성분을 출력하는 것이 아닙니다. HHL이 주는 것은 해를 진폭으로 담은 양자상태입니다. 따라서 전체 해를 모두 읽으려면 tomography 비용이 들어가고, 이 경우 장점이 사라질 수 있습니다.
말로 풀면 HHL은 “큰 연립방정식의 해 벡터를 종이에 쭉 출력하는 알고리즘”이 아니라, 해 벡터의 방향을 양자상태로 만들어서 그 상태에 대한 특정 질문을 빠르게 묻는 알고리즘입니다. 그래서 특이 케이스입니다. 입력을 양자상태로 준비할 수 있어야 하고, 행렬이 희소하거나 효율적으로 시뮬레이션 가능해야 하며, 우리가 원하는 출력도 전체 해가 아니라 기대값·overlap·분류 결과처럼 양자상태에서 직접 추정 가능한 값이어야 합니다.
## 고유분해로 보는 핵심 {#spectral}
$A$가 고유분해된다고 합시다.
$$
A=\sum_j \lambda_j |u_j\rangle\langle u_j|
$$
입력 $|b\rangle$를 고유기저로 쓰면 아래입니다.
$$
|b\rangle=\sum_j \beta_j |u_j\rangle
$$
그러면 이상적인 해는 고유값의 역수를 계수에 곱한 상태입니다.
$$
A^{-1}|b\rangle
=
\sum_j {\beta_j\over\lambda_j}|u_j\rangle
$$
HHL은 QPE로 $\lambda_j$를 레지스터에 적고, ancilla 회전으로 $1/\lambda_j$ 비율을 진폭에 넣은 뒤, eigenvalue register를 uncompute합니다.
## 회로 단계 {#steps}
1. $|b\rangle$를 준비한다.
2. $e^{iAt}$에 대한 QPE로 고유값 정보를 붙인다.
3. 고유값 레지스터를 제어로 ancilla 회전을 수행한다.
4. QPE를 역으로 돌려 고유값 레지스터를 지운다.
5. ancilla가 1인 경우를 postselect하거나 amplitude amplification으로 성공확률을 키운다.
$$
\sum_j \beta_j |u_j\rangle|\lambda_j\rangle|0\rangle
\mapsto
\sum_j \beta_j |u_j\rangle|\lambda_j\rangle
\left(
\sqrt{1-{C^2\over\lambda_j^2}}|0\rangle
+{C\over\lambda_j}|1\rangle
\right)
$$
ancilla가 $|1\rangle$인 branch가 바로 역수 가중치를 담습니다.
## condition number가 왜 중요한가 {#condition}
condition number는 대략 가장 큰 고유값과 가장 작은 고유값의 비율입니다.
$$
\kappa={\lambda_{\max}\over\lambda_{\min}}
$$
$\lambda_j$가 작으면 $1/\lambda_j$가 커집니다. ancilla 회전은 진폭이 1을 넘을 수 없으므로 보통 $C\le\lambda_{\min}$를 택합니다. 그러면 성공확률이 작아질 수 있고, amplitude amplification 비용이 늘어납니다.
따라서 HHL의 복잡도는 단순히 행렬 크기만 보지 않고 $\kappa$, sparsity, Hamiltonian simulation 비용, precision에 강하게 의존합니다.
## readout 병목 {#readout}
HHL이 유용하려면 해 벡터 전체가 아니라 어떤 관측량이 필요해야 합니다.
$$
\langle x|M|x\rangle
$$
예를 들어 특정 기대값, overlap, 분류 결과 같은 값은 양자상태에서 직접 추정할 수 있습니다. 반면 $x_1,x_2,\dots,x_N$ 전체를 고전 데이터로 모두 꺼내는 작업은 일반적으로 비쌉니다. “양자 선형시스템 알고리즘”은 “선형방정식 풀이 결과를 전부 빠르게 출력하는 알고리즘”이 아닙니다.
## 비 Hermitian 행렬 처리 {#non-hermitian}
일반 행렬 $A$가 Hermitian이 아니면 block embedding으로 Hermitian 행렬을 만들 수 있습니다.
$$
\tilde A=
\begin{bmatrix}
0&A\\
A^\dagger&0
\end{bmatrix}
$$
이 행렬은 Hermitian입니다. HHL 계열 알고리즘은 이런 embedding을 통해 더 넓은 선형시스템으로 확장됩니다. 이후의 LCU, block-encoding, QSVT 문법은 이 embedding 사고방식을 훨씬 일반화합니다.
## 현대적 관점 {#modern-view}
초기 HHL은 QPE와 Hamiltonian simulation 중심으로 설명됩니다. 현대 선형시스템 알고리즘은 block-encoding과 QSVT를 이용해 $A^{-1}$를 polynomial로 근사하는 방향으로 설명하는 경우가 많습니다.
$$
A^{-1}\approx p(A)
$$
이 관점에서는 “고유값을 읽고 회전한다”가 아니라 “singular value에 원하는 함수를 직접 적용한다”가 핵심입니다. QSVT는 HHL의 목표를 더 일반적인 행렬 함수 변환 문제로 끌어올립니다.