HHL 算法

HHL 算法（Harrow–Hassidim–Lloyd，2009）在 $\kappa$、$s$ 与 $1/ϵ$ 都是 $\mathrm{polylog}N$ 量级时，以 $\mathrm{polylog}N$ 时间求解 $N\times N$ 稀疏线性方程组 $A\vec{x}=\vec{b}$，相对经典 $\tilde{O}(N\sqrt{\kappa })$ 实现指数加速——这是量子 CFD 全部线性代数故事的起点Harrow et al. 2009 (PRL)。但算法输出的不是 $\vec{x}$ 本身，而是解的期望值 ${\vec{x}}^{†}M\vec{x}$ 类泛函：不可压 CFD 的压力泊松步、隐式时间步进的每一次线性求解都是候选内核，而”只能读出阻力、通量等标量泛函、不能读全流场”的限制正源于此。

问题设定与假设

给定 Hermitian、$s$-稀疏、行可高效计算的 $A$，其谱缩放使奇异值落在 $[1/\kappa ,1]$（即 ${\kappa }^{-2}I\le A^{†}A\le I$），$\kappa$ 为条件数；右端项以量子态 $|b⟩={\sum }_i{b}_i|i⟩$ 给出。目标不是重构 $\vec{x}$，而是估计 ${\vec{x}}^{†}M\vec{x}$——这一”泛函输出”约定既是读出瓶颈的根源，也是 CFD 中”只算气动力系数、截面通量”这类目标输出的正当性来源Harrow et al. 2009 (PRL)。非 Hermitian 矩阵经嵌入归约：解

$$\left(\begin{array}{cc}0& A\\ A^{†}& 0\end{array}\right)\left(\begin{array}{c}0\\ \vec{x}\end{array}\right)=\left(\begin{array}{c}\vec{b}\\ 0\end{array}\right)$$

尺寸翻倍但保持 Hermitian、稀疏度不变；非方阵情形同样可嵌入。

算法流程推导

设 $A$ 的谱分解 $A={\sum }_j{\lambda }_j|u_j⟩⟨u_j|$，右端项按本征基展开 $|b⟩={\sum }_j{\beta }_j|u_j⟩$。所求解 $A^{-1}|b⟩={\sum }_j({\beta }_j/{\lambda }_j)|u_j⟩$ 的全部信息藏在每个本征分量的倒数控 ${\lambda }_j^{-1}$ 上。算法分四步把它写进振幅：

第一步：相位估计。对 $e^{iAt}$ 做相位估计（机制见quantum-phase-estimation），利用相位回踢把 ${\lambda }_j$ 写进辅助寄存器：

$$|b⟩|0⟩⟶\sum _j{\beta }_j|u_j⟩|{\lambda }_j⟩.$$

第二步：受控旋转。以 $|{\lambda }_j⟩$ 为控制、对附加辅助比特做旋转角 $\arcsin (C/{\lambda }_j)$ 的 $R_y$ 旋转：

$$|{\lambda }_j⟩|0⟩⟶|{\lambda }_j⟩\left(\sqrt{1-\frac{C^2}{{\lambda }_j^2}}|0⟩+\frac{C}{{\lambda }_j}|1⟩\right).$$

第三步：后选择。测量辅助比特得 $|1⟩$ 时，态坍缩为 $\propto {\sum }_j({\beta }_j/{\lambda }_j)|u_j⟩|{\lambda }_j⟩\propto A^{-1}|b⟩$。

第四步：uncompute。逆相位估计擦除 $|{\lambda }_j⟩$ 寄存器，留下 $|x⟩\propto A^{-1}|b⟩$，随后在 $|x⟩$ 上测量 $M$ 的期望。

图:受控 R_y 旋转电路——按相位寄存器中的特征值 λ 把 1/λ 写进振幅,这是 HHL 的心脏部件;Cao 等在泊松求解器中用 Newton 迭代电路先算 λ⁻¹ 再执行旋转(来源:QC014)

后选择成功率是 $\kappa$ 依赖的第一个来源：$p=\Vert A^{-1}|b⟩{\Vert }^2/{\kappa }^2$，由谱窗假设 $\Vert A^{-1}|b⟩\Vert \ge 1/\kappa$ 得 $p=\Omega (1/{\kappa }^2)$。裸重复需 $O({\kappa }^2)$ 次；改用幅值放大（amplification）把成功率提到 $O(1)$ 的代价是 $O(\kappa )$ 次重复，$\kappa$ 依赖从平方降为一次。

复杂度推导脉络

总运行时 $\tilde{O}({\kappa }^2{s}^2\log N/ϵ)$ 的构成Harrow et al. 2009 (PRL)：

1. 相位估计主导。要把 ${\lambda }_j$ 估计到 $O(ϵ)$ 精度需要演化时长 $t_0=O(\kappa /ϵ)$（谱窗 $[1/\kappa ,1]$ 决定相位的动态范围），稀疏哈密顿量模拟成本随 $s^2{t}_0\log N$ 增长；
2. 后选择/幅值放大贡献 $O(\kappa )$ 因子；
3. 附录中含态制备成本的合成界为 $\tilde{O}(\kappa T_B+{\kappa }^2{s}^2\log (N)/ϵ)$，$T_B$ 为制备 $|b⟩$ 的成本——这是态制备开销最早被显式记账的地方（见state-preparation）。

必须如实记录两点：对精度 $1/ϵ$ 的依赖劣于经典算法的 polylog 缩放；此框架沿用的 Suzuki 高阶积分器已被后续技术取代（见hamiltonian-simulation、block-encoding）。QSVT 时代的矩阵求逆已改进为 $O(\kappa \log (\kappa /ϵ))$ 次块编码查询Martyn et al. 2021 (arXiv)。

与经典算法对比：何时指数加速

HHL 给出的经典参照是 $\tilde{O}(N\sqrt{\kappa })$（含随机 Kaczmarz 类算法）Harrow et al. 2009 (PRL)。因此指数加速仅当 $\kappa$ 与 $1/ϵ$ 均为 $\mathrm{polylog}N$ 时成立。配套的硬度结果划出边界：任意 $n$ 比特、$T$ 门的量子电路都可被 $O(1)$-稀疏、$\kappa =O(T)$ 的矩阵求逆模拟——若存在经典 $\mathrm{poly}(\log N,\kappa )$ 求逆算法，就能多项式时间模拟量子电路（在 oracle 模型下不可能）。这同时说明 $\kappa$ 依赖不可轻易去除。

对 CFD 的两个直接推论：

• 条件数是头号敌人。FEM/有限差分离散的椭圆问题 $\kappa =O(N^{2/d})$（网格加密即恶化，见quantum-fem），预条件是必选项——Clader 等的 SPAI 稀疏近似逆与读出改进（辅助寄存器 + 幅值估计测 $⟨x|\hat{R}|x⟩$，去掉后选择后 $\kappa$ 依赖从平方改善到一次）是第一条完整的应用链路Clader et al. 2013 (PRL)，在块编码时代被 Rolls-Royce 的 CFD 矩阵预条件研究延续（见quantum-multigrid）。
• 读出决定输出形态。$|x⟩$ 是量子态，全振幅读出指数昂贵（见io-problem）；现实的量子 CFD 目标是”每步输出一个泛函”——阻力、升力、通量、能谱点，或把 $|x⟩$ 直接留作下一步演化的输入避免读出。

延伸阅读

• quantum-phase-estimation
• block-encoding
• vqls
• quantum-poisson-solver
• state-preparation
• io-problem