求解线性方程组 $A\vec{x} = \vec{b}$ 是科学计算中最基础、最高频的问题。HHL 算法（2009）首次证明量子计算机可在多项式时间内完成这一任务，但原始 HHL 有多项重大局限。本文系统梳理从 HHL 原始算法到近年来基于 Qubitization、QSVT、变分方法等现代改进的完整演进。

问题定义

给定 $A \in \mathbb{C}^{N \times N}$（$N = 2^n$），$\vec{b} \in \mathbb{C}^N$，求 $\vec{x} = A^{-1}\vec{b}$。

经典最优方法：

• 高斯消元：$O(N^3)$
• 共轭梯度法（稀疏 $A$）：$O(Ns\kappa \log(1/\varepsilon))$（$s$ 为稀疏度，$\kappa$ 为条件数）

量子目标：以 $O(\text{poly}(n) \cdot \text{poly}(\kappa) \cdot \log(1/\varepsilon))$ 代价实现 $|x\rangle \propto A^{-1}|b\rangle$。

第一代：原始 HHL（2009）

算法回顾

Harrow, Hassidim, Lloyd (2009) 提出：

1. QPE：对 $|b\rangle$ 执行量子相位估计，将 $A$ 的特征值 $\lambda_j$ 读入辅助寄存器
2. 受控旋转：$R_y(C/\lambda_j)$ 将 $1/\lambda_j$ 编码到辅助量子比特的振幅中
3. 逆 QPE：消去辅助寄存器中的特征值信息
4. 后选择：测量辅助比特得 $|1\rangle$，系统态坍缩为 $|x\rangle \propto A^{-1}|b\rangle$

局限性

第二代：最优精度改进（2017）

Childs-Kothari-Somma (SIAM J. Comp. 2017)

关键改进：将 $\kappa$ 依赖从 $O(\kappa^2)$ 降至 $O(\kappa \log(1/\varepsilon))$。

方法：用多项式变换替代简单的受控旋转。不是直接实现 $1/\lambda$，而是用切比雪夫多项式逼近 $f(x) = 1/x$（在 $[1/\kappa, 1]$ 上）。

多项式次数：$d = O(\kappa \log(\kappa/\varepsilon))$。

总复杂度：

$$O\left(d \cdot C_{U_A}\right) = O\left(\kappa \log(\kappa/\varepsilon) \cdot s \cdot n\right)$$

其中 $C_{U_A} = O(s \cdot n)$ 是 $e^{iA}$ 的一次实现代价。

优势：对 $\kappa$ 仅线性依赖（改进了二次依赖），无需后选择（多项式变换直接实现）。

第三代：Qubitization + QSVT 框架（2019）

Gilyén, Su, Low, Wiebe (STOC 2019)

QSVT 为量子线性求解提供了最通用、最优雅的框架。

核心思想：将 $A^{-1}$ 的实现归约为对 $A$ 的奇异值施加多项式变换 $P(\sigma_j) \approx 1/\sigma_j$。

步骤：

1. 块编码：构造 $A$ 的 $(\alpha, m, \varepsilon)$-块编码 $U_A$
2. Qubitization：构造量子行走酉算符 $W(A)$，特征相位 $\theta_j = \arccos(\sigma_j)$
3. QSP 多项式变换：选择相位参数 $\vec{\Phi}$ 使得 $P_{\vec{\Phi}}(\cos\theta_j) \approx 1/\cos\theta_j = 1/\sigma_j$
4. 执行：$d$ 次 $W(A)$ 调用，深度 $O(d)$

多项式次数：$d = O(\kappa \log(\kappa/\varepsilon))$。

总复杂度：

$$O\left(\kappa \log(\kappa/\varepsilon) \cdot C_{U_A}\right)$$

对比 HHL：

第四代：变分量子线性求解器（VQLS，2020）

Bravo-Prieto et al. (Quantum 2023)

VQLS 是面向 NISQ 设备的量子-经典混合算法，不使用 QPE，无需深层电路。

核心思想：将 $A\vec{x} = \vec{b}$ 转化为变分优化问题：

$$\min_{\vec{\theta}} \left\| A |x(\vec{\theta})\rangle - |b\rangle \right\|^2$$

等价于最小化损失函数：

$$\mathcal{L}(\vec{\theta}) = 1 - \frac{|\langle b|A|x(\vec{\theta})\rangle|^2}{\langle x(\vec{\theta})|A^\dagger A|x(\vec{\theta})\rangle}$$

算法步骤：

1. 参数化电路：$|x(\vec{\theta})\rangle = U(\vec{\theta})|0\rangle^{\otimes n}$
2. 损失函数估计：用 Hadamard Test 估计 $\langle x|A^\dagger A|x\rangle$、$\langle b|A|x\rangle$ 等
3. 经典优化：Adam/COBYLA 更新 $\vec{\theta}$
4. 收敛后测量：测量 $|x(\vec{\theta})\rangle$ 得到解的统计信息

Hadamard Test 电路：

|0⟩ ─ H ─ ctrl-A|x(θ)⟩ ─ H ─ 测量
|b⟩ ──────────────────────

测量期望值 $\text{Re}\langle b|A|x(\vec{\theta})\rangle$。

复杂度：

• 量子电路深度：$O(C_A \cdot D)$（$C_A$ 为 $A$ 的电路深度，$D$ 为拟设深度）
• 测量次数：$O(\text{poly}(n) / \varepsilon^2)$
• 优化迭代：$O(T_{\text{opt}})$（经验）

优势：

• 无 QPE，电路浅
• 适用于 NISQ 设备
• 可处理非稀疏矩阵

局限：

• 无收敛保证（可能陷入局部最小值）
• Barren Plateaus 问题
• 精度有限

LDSE（Linear Differential Equation Solver）

Xu, Sun, Yuan (PRL 2023) 将 VQLS 推广到微分方程求解，用变分方法实现 $A(t)\vec{x}(t) = \vec{b}(t)$ 的时间演化。

第五代：基于 Schrödingerization 的方法（2022-2024）

Jin, Liu, Yu (2022-2024)

Schrödingerization 框架将线性方程组 $A\vec{x} = \vec{b}$ 的求解转化为薛定谔方程的模拟。

思想：考虑动力学 $\dot{\vec{x}} = -A(\vec{x} - \vec{x}_{\text{eq}})$，稳态 $\vec{x}_{\text{eq}} = A^{-1}\vec{b}$。

将 $\vec{x}(0) = \vec{b}$，演化至 $t \to \infty$，$\vec{x}(t) \to A^{-1}\vec{b}$。

优势：不要求 $A$ 是 Hermitian，通过 Schrödingerization 的辅助维度处理非对称性。

代价：后选择概率 $O(e^{-\|A\|t})$，对大 $\|A\|t$ 需要指数重复。

其他现代方法

量子梯度下降法（2025）

arXiv:2502.13630 提出基于梯度下降的量子线性求解器：

$$\vec{x}_{k+1} = \vec{x}_k - \eta (A^T A \vec{x}_k - A^T \vec{b})$$

每步在量子电路上实现，避免了 QPE 的深度要求。

量子随机 Kaczmarz 方法

将经典 Kaczmarz 迭代（逐行投影）量子化：

$$\vec{x}_{k+1} = \vec{x}_k + \frac{b_i - \langle a_i, \vec{x}_k\rangle}{\|a_i\|^2} a_i$$

每步随机选取一行 $i$，量子实现需要 $O(n)$ 门。

收敛速度：$O(\kappa^2 \log(1/\varepsilon))$ 步。

绝热量子线性求解

将 $A\vec{x} = \vec{b}$ 编码为哈密顿量基态问题，用绝热演化求解：

$$H_P = I - \frac{|b\rangle\langle b|}{b^2} \cdot (I - A^\dagger A / \|A\|^2)$$

$H_P$ 的基态恰好是 $A^{-1}|b\rangle$ 的归一化版本。

复杂度对比

实验进展

关键限制与开放问题

输入问题（Input Problem）

将经典向量 $\vec{b}$ 加载为量子态 $|b\rangle$ 需要 $O(N)$ 门——抵消量子加速。对结构化 $\vec{b}$（稀疏、低秩），可用稀疏态制备降低代价。

输出问题（Output Problem）

$|x\rangle$ 编码了全部解分量，但读出 $x_j$ 需要 $O(1/|x_j|^2)$ 次测量。完整读出需要 $O(N)$ 次——与经典相同。

量子优势场景：

• 计算 $\langle x|M|x\rangle$（期望值）：$O(1)$ 次测量
• 计算 $\|x\|^2$：$O(1)$ 次测量
• 从 $|x\rangle$ 采样：$O(\text{poly}(n))$ 次

QRAM 的角色

许多”量子线性代数”算法假设数据可通过 QRAM 高效访问。若没有 QRAM，输入/输出的开销可能抵消理论加速。这是当前争议的焦点。

Barren Plateaus（对 VQLS）

对深拟设，VQLS 的损失景观存在贫瘠高原——梯度指数衰减。缓解策略包括局域损失函数、结构化拟设等。

应用场景

1. 有限元分析

将偏微分方程离散化为 $A\vec{x} = \vec{b}$，用 QSVT 求解。对稀疏、良态的 $A$，有望实现指数加速。

2. 机器学习

最小二乘回归：$A = X^T X$，$\vec{b} = X^T \vec{y}$。用 VQLS 在 NISQ 设备上求解。

3. 金融

Black-Scholes 方程的有限差分离散化产生大型线性系统，量子线性求解器有望加速风险计算。

4. 电力系统

潮流计算的核心是求解非线性方程组的线性化版本，每步迭代涉及线性方程组。

总结

量子线性求解器从 HHL (2009) 的开创性工作，经过 Childs-Kothari-Somma (2017) 的精度优化，到 QSVT (2019) 的统一框架，再到 VQLS (2020) 的 NISQ 适用方案，经历了五代演进。现代方法将 $\kappa$ 依赖从 $\kappa^2$ 改进到 $\kappa$（理论最优），并消除了后选择需求。在实际应用中，方法的选择取决于问题规模、精度要求和可用量子硬件。

参考文献：

1. Harrow, A. W., Hassidim, A., & Lloyd, S. (2009). Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15), 150502.
2. Childs, A. M., Kothari, R., & Somma, R. D. (2017). Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46(6), 1920-1950.
3. Gilyén, A., Su, Y., Low, G. H., & Wiebe, N. (2019). Quantum singular value transformation and beyond. STOC 2019.
4. Bravo-Prieto, C., et al. (2023). Variational Quantum Linear Solver. Quantum, 7, 1188.
5. Jin, S., Liu, N., & Yu, Y. (2022). Quantum simulation of partial differential equations via Schrödingerization. arXiv:2212.13969.