HHL 量子线性系统算法

在 $A$ 的特征向量坐标中，解线性方程只是把每个分量除以对应特征值。量子算法想相干地做这件事，却不能让一个酉门随意放大某些振幅。

办法是先把所有倒数乘一个足够小的 $C$，让它们都落在 $[-1,1]$，再把这个数当作一个辅助成功分支的振幅。成功时各特征方向的相对比例正是倒数，代价则是成功概率可能很小，以及小特征值要求更精细的相位估计。

理想精确谱记录下的五步 ​

写

为先看清逻辑，暂设相位估计能精确写下 ${\lambda }_j$。选择 $0<C\le 1/\kappa$：

1. 制备 $\sum _j{\beta }_j|u_j⟩$
2. 相干记录特征值，得到 $\sum _j{\beta }_j|u_j⟩|{\lambda }_j⟩$
3. 依 ${\lambda }_j$ 将新辅助0旋转为 $\sqrt{1-C^2/{\lambda }_j^2}|0⟩+(C/{\lambda }_j)|1⟩$
4. 反计算谱寄存器，使其返回0
5. 测最后辅助，仅保留结果1

未归一化成功向量为 $C{A}^{-1}|b⟩$，所以

由于 $1\le \Vert A^{-1}|b⟩\Vert \le \kappa$，取 $C=\mathrm{\Theta }(1/\kappa )$ 后，成功概率最坏为 $\mathrm{\Omega }(1/{\kappa }^2)$，并不是对所有输入相同。

反计算不能省掉。若保留可区分的 $|{\lambda }_j⟩$ 并丢弃它，不同谱分量的相干可能丢失，留下解态各谱方向的混合而不是所需纯态。

两维完整例子 ​

取 $A=\mathrm{diag}(1,1/2)$、$|b⟩=|+⟩$，精确例子可选最大 $C=1/2$。取相位估计的基础酉 $e^{i\pi A}$，两个相位为 $1/2,1/4$，可用两位相位寄存器精确表示为10、01。

倒数旋转的成功振幅分别为 $1/2,1$。反计算后的完整数据—标志态为

成功概率为

成功态为 $(|0⟩+2|1⟩)/\sqrt{5}$。其 $Z$ 期望为 $1/5-4/5=-3/5$，这是可以通过重复制备和测量读出的一个标量，而不是完整经典解向量。

若把矩阵第二个特征值换成 $-1/2$，正确解态变为 $(|0⟩-2|1⟩)/\sqrt{5}$。计算基概率没变，但相干相位变了；只验证成功概率不能检查倒数符号是否正确。

有限相位精度怎样经过倒数放大 ​

真实相位估计给 $\tilde{\lambda }$，不是无限精度标签。对满足 $|\tilde{\lambda }-\lambda |\le \mathrm{\Delta }$、$0<\mathrm{\Delta }\le 1/(4\kappa )$ 的分支，

这给出了 $\mathrm{\Delta }=O(\epsilon /\kappa )$ 的尺度。只说“相位误差小”不够，误差必须与最小特征值比较。

还要先保证单次估计的成功率超过一半，才可用中位数压低尾部。取基础酉 $e^{iA\tau }$、$\tau =\pi /2$，真实带符号相位为 $\theta =\lambda /4\in [-1/4,1/4]$。选不小于 $16/\mathrm{\Delta }$ 的最小二次幂 $K$，将 QPE 输出 $y/K$ 解码到 $[-1/2,1/2)$，再乘 $4$ 得到 $\tilde{\lambda }$。

由相位估计的有限几何级数分布，若输出与真实相位的圆周网格距离为 $d_y=K{d}_{\mathbb{T}}(y/K,\theta )>0$，则 $\text{Pr}(y)\le 1/(4d_y^2)$。每个距离区间 $[j,j+1)$ 至多含两个网格点，故

在其余结果上，相位误差至多 $4/K\le \mathrm{\Delta }/4$。由于 $\mathrm{\Delta }\le 1/(4\kappa )\le 1/4$，该窗口不碰带符号解码的切口，于是 $|\tilde{\lambda }-\lambda |\le 16/K\le \mathrm{\Delta }$。这给至少 $5/6$ 的单次保证；只使用最近网格点的 $4/{\pi }^2$ 下界则尚不足以支持中位数放大。

在同一个特征向量上，相干执行奇数 $r$ 次 QPE，各结果寄存器的计算基分布等同于独立重复。可逆地算出这些带符号估计的中位数，再按它旋转，最后将中位数计算和全部 QPE 逆转。用保守的单次成功率 $3/4$ 和Hoeffding 界公理库Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。，坏中位数质量至多 $e^{-r/8}$；取满足 $r\ge 8\ln \left(1/\zeta \right)$ 的最小正奇数 就压到给定 $0<\zeta <1$。不能真的测出特征值再把数据按经典标签混合。

为避免边界旋转过于敏感，在这份误差分析中取 $C=1/(2\kappa )$，而不是上面精确小例子的最大 $C$。对 $|\tilde{\lambda }|<1/(2\kappa )$ 的异常估计，可把成功振幅设0；其余分支用有界的 $C/\tilde{\lambda }$。好估计满足 $|C/\tilde{\lambda }|\le 2/3$，旋转的两个振幅都是平滑函数。

记理想成功概率为 $q$。式 (2) 及该平滑性使好分支的联合向量误差为 $O(\kappa \mathrm{\Delta }\sqrt{q})$；坏分支的范数误差至多 $2\sqrt{\zeta }$。酉反计算不增大这些误差。后选择再归一化，因 $\sqrt{q}\ge 1/(2\kappa )$，条件输出误差为

所以选 $\mathrm{\Delta }$ 为足够小常数倍 $\epsilon /\kappa$，$\zeta$ 为足够小常数倍 ${\epsilon }^2/{\kappa }^2$，即可得到目标精度，同时实际成功概率仍为 $\mathrm{\Omega }(1/{\kappa }^2)$。例如可从 $\mathrm{\Delta }=\epsilon /(100\kappa )$、$\zeta ={\epsilon }^2/({10}^4{\kappa }^2)$ 开始，再为门实现误差留余量。

上述带符号解码保留负特征值，而非把它误读为接近 $1$ 的正相位。一次 QPE 的总演化时间为 $O(1/\mathrm{\Delta })$；中位数版本还乘以 $O(1+\log \left(1/\zeta \right))$，逆计算和各次模拟精度也须计入。

为什么条件数又出现在运行时间里 ​

没有放大时，最坏需要 $O({\kappa }^2)$ 次独立制备才能接受。若提供整个制备—相位估计—旋转子程序及其逆，可用振幅放大公理库振幅放大Amplitude amplification · Quantum amplitude amplification用状态制备及其逆与两次选择性反射，将任意过程的成功振幅按二维旋转规律放大。把获得一个输出的调用次数降到 $O(\kappa )$，允许常数成功概率或相应高置信重试。

因此基本机制是：一次谱处理需总演化时间约 $\kappa /\epsilon$，放大再带来 $\kappa$；另有每次制备 $|b⟩$ 和可逆算术的成本。若记一次完整谱处理及其逆为 $C_{\mathrm{PE}}$，制备成本为 $C_b$，倒数旋转算术成本为 $C_{\mathrm{rot}}$，则得到一份解态的成本可记为

其中 $C_{\mathrm{PE}}$ 必须展开为各受控演化的查询/门数，不能只写“相位估计一次”。对整个近似子程序做放大时，放大保留它自身的归一化成功态；仍须在最初的子程序误差预算中保证该态接近目标。

原始HHL在高效稀疏访问和高效 $|b⟩$ 制备的前提下，常把运行时间概括为 $\tilde{O}(s^2{\kappa }^2\log N/\epsilon )$。[1, Run-time and error analysis] 这里沿原文简写，略去所用模拟器的次多项式精度因子及对数开销；它不是任意输入列表模型中的无条件上界，也不是后续改进算法的最优复杂度。

若 $|b⟩$ 制备向量误差为 ${\eta }_b$，最坏的归一化解态误差可达 $O(\kappa {\eta }_b)$；制备精度也须随条件数调整。经典输入处理不是在量子步骤开始后就可以忘记的成本。

读出任务决定最后能否省资源 ​

对上例直接测 $Z$，或使用Hadamard测试公理库Hadamard 测试Hadamard test逐振幅推导受控酉期望值的实部和虚部读出，固定S逆门的相位约定，并给出样本数、输入制备和黑盒控制访问的完整成本。估计更一般酉期望，每个样本都要重新得到一份解态。用上述 Hoeffding 界对独立样本把有界期望估到加法误差 $\eta$、失败概率 $\delta$，通常还要 $O({\eta }^{-2}\log \left(2/\delta \right))$ 份输出。

若要求打印 $N$ 个经典坐标，单是输出长度就不再是 $\mathrm{polylog}N$。此外，归一化解态不保留原向量整体尺度，坐标的相位和范数也需额外任务恢复。因此HHL的自然用途是某些态制备或可观测量问题，不能只把式子 $Ax=b$ 相同就与完整经典线性求解直接比较。