Skip to content
首页/术语表/HHL 算法
Algorithms

HHL 算法

以 Harrow、Hassidim 和 Lloyd 三人姓氏命名的量子算法,在一组特定且相当严格的条件下,能以指数级速度快于经典方法求解线性方程组。

HHL 算法由 Aram Harrow、Avinatan Hassidim 和 Seth Lloyd 于 2009 年发表,用于求解形如 Ax = b 的线性系统,返回一个正比于解向量 x 的量子态,所需时间随系统规模呈对数增长——在合适的条件下,相对于最好的经典线性求解器实现了指数级加速。而这些条件正是问题所在:这种加速要求矩阵 A 必须是稀疏且条件数良好的,输入向量 b 必须已经能够以量子态的形式载入(这本身在一般情况下就是一个难题),而且输出是一个编码了解的量子态,而不是解本身的各个数值,所以要读出具体数值就需要额外的测量,往往还会把这种加速优势完全抵消掉。理解 HHL 最好的方式,是把它看作其他量子算法所依赖的一个子程序,尤其是若干种被提出的量子机器学习算法,它们内部都可以归结为求解一个线性系统,而不是把它当作经典线性代数的通用替代品。目前还不存在容错硬件能够在足以体现其渐近优势的规模上运行 HHL。