引用drkevorkian · 2013-06
“He might be referring to this: Quantum algorithm for solving linear systems of equations”
猜测对方指的是这篇稀疏线性方程组的量子加速算法
稀疏线性方程组的量子算法,可指数级加速估计解的期望值(HHL)
论文针对稀疏、条件数为 κ 的 N×N 线性方程组 Ax=b,不去求完整的解 x,而是估计与 x 相关的算子期望值 x'Mx。作者给出一种运行时间为 poly(log N, κ) 的量子算法,而经典算法需要 O(N√κ) 时间,因此声称有指数级加速。
HN 评论者把它当作量子线性方程组加速的出处,在讨论文章里的复杂度断言时引用其摘要。
“He might be referring to this: Quantum algorithm for solving linear systems of equations”
“See the abstract of [1] for the precise complexity claim about the algorithm mentioned in the article.”