摘要 Abstract
求解线性方程组是许多量子算法的关键子程序。在过去的15年里,开发了许多量子线性求解器(QLS),以实现最佳的渐近最坏情况复杂度。大多数QLS假设容错量子计算机,因此目前还无法在实际硬件上进行基准测试。由于渐近缩放更好的算法可能在实际感兴趣的实例上表现较差,哪种算法最具前景的问题仍未解决。在这项工作中,我们提出了一种方法部分解决这一问题。我们考虑了四种著名的直接实现近似矩阵求逆功能的QLS算法:Harrow-Hassidim-Lloyd算法、两个利用单位算符线性组合的算法以及一个利用量子奇异值变换(QSVT)的算法。这些被称为功能性QLS的方法在问题设定和oracle访问方面几乎具有相同的假设。它们的计算成本主要由对矩阵oracle的查询调用决定,该oracle编码了需要解决的问题。我们提供了计算解决特定问题实例所需查询数量的公式;这些公式可用于在没有量子硬件的情况下对真实实例进行基准测试。我们选择了三个数据集:随机生成的满足功能性QLS假设的实例、MIPLIB上的单纯形迭代线性系统以及泊松方程。我们的方法可以轻松扩展到其他数据集,并提供评估QLS算法性能的高层次指南。特别是,我们的工作表明,与其他方法相比,HHL在所有数据集上的表现都明显较差,通常相差几个数量级,而基于QSVT的方法表现出最佳性能。
Solving systems of linear equations is a key subroutine in many quantum algorithms. In the last 15 years, many quantum linear solvers (QLS) have been developed, competing to achieve the best asymptotic worst-case complexity. Most QLS assume fault-tolerant quantum computers, so they cannot yet be benchmarked on real hardware. Because an algorithm with better asymptotic scaling can underperform on instances of practical interest, the question of which of these algorithms is the most promising remains open. In this work, we implement a method to partially address this question. We consider four well-known QLS algorithms which directly implement an approximate matrix inversion function: the Harrow-Hassidim-Lloyd algorithm, two algorithms utilizing a linear combination of unitaries, and one utilizing the quantum singular value transformation (QSVT). These methods, known as functional QLS, share nearly identical assumptions about the problem setup and oracle access. Their computational cost is dominated by query calls to a matrix oracle encoding the problem one wants to solve. We provide formulas to count the number of queries needed to solve specific problem instances; these can be used to benchmark the algorithms on real-life instances without access to quantum hardware. We select three data sets: random generated instances that obey the assumptions of functional QLS, linear systems from simplex iterations on MIPLIB, and Poisson equations. Our methods can be easily extended to other data sets and provide a high-level guide to evaluate the performance of a QLS algorithm. In particular, our work shows that HHL underperforms in comparison to the other methods across all data sets, often by orders of magnitude, while the QSVT-based method shows the best performance.