1. 项目概述超越渐进复杂度量子线性求解器的实战性能较量量子线性求解器Quantum Linear Solver, QLS是量子计算领域一个经久不衰的核心课题。自2009年Harrow-Hassidim-LloydHHL算法横空出世展示了在特定条件下相对于经典算法的指数级加速潜力以来围绕如何更高效地求解线性方程组Axb的量子算法研究便层出不穷。在过去的十五年里我们见证了从HHL到基于线性组合酉算子Linear Combination of Unitaries, LCU的方法再到近年来基于量子奇异值变换Quantum Singular Value Transformation, QSVT的框架算法的渐进复杂度即理论上的大O标度被不断优化和刷新。然而对于身处一线的研究者和工程师而言一个更实际、也更棘手的问题是当理论上的渐进优势遭遇有限规模、特定结构的实际问题时哪种算法才是真正“能打”的一个在渐进分析中复杂度更优的算法可能因为巨大的常数因子或对问题参数如条件数κ、精度ε的敏感依赖而在实际应用中败给一个理论标度稍逊但更稳健的对手。这就像在经典优化中理论上具有多项式时间复杂度的椭球法在实际中往往不敌指数复杂度的单纯形法。因此仅仅比较算法的渐进标度就像只比较汽车的极速而不考虑其油耗、操控性和维修成本对于实际选型来说远远不够。本文旨在跳出传统的渐进复杂度分析框架采用一种名为“混合基准测试”Hybrid Benchmarking的实证方法对四种主流的“功能型”量子线性求解器进行头对头的性能比较。这四种算法是开山鼻祖HHL算法、两种基于LCU框架的算法我们称之为QLS-Fourier和QLS-Chebyshev以及基于QSVT框架的QLS-QSVT算法。它们都被归类为“功能型”因为其核心思想都是通过量子电路近似实现矩阵A的逆函数f(A)≈A⁻¹。我们的比较不依赖于尚在襁褓中的容错量子硬件而是基于一个共同的理想化假设模型所有算法都使用相同的“稀疏矩阵访问预言机”Sparse Access Oracle来编码问题矩阵A。在这个公平的竞技场上我们通过精确计算解决一个具体线性系统实例所需调用该预言机的总次数即查询复杂度来评估算法的实际效率。我们的测试覆盖了三类数据集1为满足QLS理想假设而生成的半随机矩阵2来源于实际混合整数规划库MIPLIB的单纯形法迭代过程中产生的线性系统3泊松方程离散化后产生的线性系统。结果清晰而具有启发性经典的HHL算法在所有数据集上均大幅落后于其他方法查询次数往往高出数个数量级这凸显了其作为实用工具的局限性。而在剩余的三位选手中基于Chebyshev多项式逼近的QLS-Chebyshev和QLS-QSVT表现最为出色其中QLS-Chebyshev在单纯形和泊松数据集上综合表现最佳QLS-QSVT则在随机生成的数据集上略有优势。这项工作的价值在于它提供了一套在硬件成熟之前即可评估和筛选量子算法潜力的方法论为未来量子软件栈的开发指明了更务实的方向。2. 核心思路与比较框架解析2.1 功能型量子线性求解器的共同舞台要公平地比较不同算法首先必须确保它们在解决同一个问题。我们考虑标准的线性方程组求解问题给定一个N×N的埃尔米特Hermitian矩阵A和一个向量b求解x A⁻¹b。在量子语境下目标并非输出完整的经典解向量x而是制备出与解x成正比的量子态|x⟩。此外我们假设矩阵A是d-稀疏的即每行/列最多有d个非零元并且具有条件数κ最大与最小特征值绝对值之比。求解精度由参数ε控制。所有被比较的功能型QLS算法共享以下核心资源与假设稀疏访问预言机PA这是算法与问题实例交互的唯一接口。它由两个子预言机构成OF|j, l⟩ - |j, f(j, l)⟩给定行索引j和序号l返回该行第l个非零元素的列索引。OA|j, k, z⟩ - |j, k, z ⊕ A_jk⟩给定行j和列k返回矩阵元素A_jk⊕表示模2加。状态制备预言机Pb能够制备与向量b对应的量子态|b⟩。量子振幅放大QAA由于核心的线性求解步骤通常以一定概率成功概率p输出目标态因此需要利用QAA即Grover搜索的广义形式将成功概率放大至O(1)。这会引入一个与1/√p成正比的预期重复次数开销。在这个框架下算法的总成本主要由对预言机PA即OF和OA的查询次数主导。其他操作如单/双量子门操作的成本在当前的算法分析中通常被认为与查询成本呈线性关系且对所有算法的影响相似。因此比较对PA的查询次数成为了衡量算法在理想化、容错环境下相对效率的一个合理启发式指标。2.2 混合基准测试从理论公式到实例化计数混合基准测试的核心思想非常直观为每个算法推导出计算其查询次数的精确公式然后将具体问题实例的参数N, d, κ, ε, 以及关键的解向量范数||x||代入公式得到该实例下的具体查询次数。这不同于传统的渐进分析只关心O(κ log(1/ε))这样的标度也不同于在量子模拟器或硬件上进行端到端的模拟后者资源消耗巨大且受当前噪声限制。它是一种介于两者之间的、面向算法设计阶段的评估方法。具体步骤如下参数提取对于一个给定的线性系统实例A, b在经典计算机上计算其关键参数矩阵规模N、稀疏度d、条件数κ、目标精度ε以及解向量的范数||x||。其中||x||对于精确计算QAA的重复次数至关重要。公式应用将上述参数代入每个算法对应的查询复杂度公式参见第3章。这些公式来源于各算法的原始论文但经过了我们的整理和统一以纳入常数因子和精确的QAA开销计算。计数与比较对每个算法计算得出一个具体的整数或浮点数查询次数。通过在不同类型、不同规模的实例上运行这一流程我们可以绘制出算法性能的热力图或分布图直观地看到哪种算法在何种参数区域内更具优势。这种方法的美妙之处在于它剥离了量子误差校正、特定硬件实现等带来的、对所有算法大致相当的额外开销让我们能够聚焦于算法设计本身的内在效率差异。如果一个算法在这种“理想实验室环境”下的查询成本已经高出其他算法好几个数量级那么在实际的、充满噪声和开销的硬件上它的劣势只会更加明显。2.3 为何选择这四种算法在众多QLS变体中我们聚焦于HHL、QLS-Fourier、QLS-Chebyshev和QLS-QSVT主要基于以下几点考量代表性HHL是奠基性工作是大多数QLS应用的起点和参照系。基于LCU的两种算法代表了在HHL之后、QSVT之前的一类重要优化思路。QSVT则是当前最通用、最强大的量子算法框架之一其QLS实现代表了前沿水平。可比性这四种算法同属“功能型”范畴都试图直接近似A⁻¹这个矩阵函数。它们对问题设置A为埃尔米特、稀疏和预言机访问相同的PA的假设几乎完全一致这为公平比较奠定了基础。实践相关性尽管存在理论上具有最优渐进复杂度的“绝热量子线性求解器”但它们与功能型QLS在结构上异较大难以在完全相同的假设下进行直接比较。而功能型QLS尤其是HHL在当前的量子算法文献和潜在应用中仍占据重要地位因此对其性能的深入评估具有直接的现实意义。3. 算法细节与查询复杂度公式拆解本章将深入剖析四种算法的核心机制并给出用于混合基准测试的精确查询复杂度计算公式。这些公式是后续性能比较的基石。3.1 公共组件哈密顿量模拟与量子振幅放大在深入各个算法之前有两个公共的子程序需要明确其成本。哈密顿量模拟Hamiltonian SimulationHHL和QLS-Fourier算法都需要模拟酉演化算子e^{-iAt}。我们采用目前已知最优的“量子比特化”Qubitization方法来实现。其查询复杂度公式为Q[e^{-iAt}] 48 * \tilde{r}(d * ||A||_max * t, ε)其中\tilde{r}(\tilde{t}, ε)是一个分段函数具体形式见原文Lemma 1。这里||A||_max是矩阵A中绝对值最大的元素t是模拟时间。这个公式告诉我们模拟的查询成本与模拟时间t和精度ε呈非线性关系。量子振幅放大QAA所有算法都需要用QAA来提升成功概率。关键点在于算法运行时通常只知道成功概率p的一个下界p0而QAA的调度策略即每次重复算法A的次数序列依赖于这个p0。然而在混合基准测试中我们可以在经典侧精确计算出真实的成功概率p sin²θ。由此可以计算出QAA的预期查询开销n_QAA。公式如下详见原文Lemma 2n_QAA Σ_{k1}^{∞} [ m_k * Π_{l1}^{k-1} (1 - ⟨p_{j_l}⟩) ]其中m_k floor(min(c^k, 1/√p0))c是一个介于1和2之间的常数文中取6/5⟨p_{j_l}⟩是基于真实概率p计算出的、在第l轮迭代中成功概率的期望值。这个公式看起来复杂但其物理意义清晰它计算了在随机化QAA策略下为了以高概率获得成功需要重复运行核心算法A的期望次数。最终算法的总查询次数需要乘以这个n_QAA因子。3.2 HHL算法开创者的代价HHL算法的核心思想是利用量子相位估计QPE将矩阵A的特征值编码到一个“时钟”寄存器中然后通过对该寄存器进行一个与特征值倒数相关的旋转操作来实现矩阵求逆。最后通过测量一个辅助量子比特标志位来后选择出成功的结果。查询复杂度公式Lemma 3:Q[HHL] 2 * n_QAA * Q[e^{-iAt}]其中t √(c_F) * κ / εc_F是一个约为100的常数。成功概率p ≈ ||x||² / (4κ²)其下界p0 1/(4κ²)。因子2来源于每次QAA操作需要调用两次核心算法一次A一次A†。关键点与性能瓶颈对精度ε的依赖HHL的模拟时间t与κ/ε成正比而查询复杂度Q[e^{-iAt}]随着t线性或超线性增长。这导致其对精度ε的需求极其敏感1/ε的依赖使得在高精度要求下成本急剧上升。相比之下其他算法的依赖是log(1/ε)。成功概率低成功概率下界p0与1/κ²成正比。对于病态κ很大问题这个概率非常小导致QAA的放大开销n_QAA正比于1/√p0即∝ κ非常大。双重打击模拟成本高∝ κ/ε且需要大量重复∝ κ两者相乘导致了O(κ²/ε)的总体标度这在实践中是致命的。3.3 QLS-Fourier算法傅里叶级数逼近QLS-Fourier算法基于LCU框架。其核心思想是将矩阵逆函数1/x在区间[1/κ, 1]上用一系列复指数函数e^{-iAt_j}的线性组合来逼近。这本质上是一个傅里叶级数逼近。查询复杂度公式Lemma 4:Q[QLS_Fourier] n_QAA * Q[e^{-iAt}]其中t 2√(2κ * log(1 8κ/ε))。可以看到模拟时间t与√(κ log(κ/ε))相关优于HHL的κ/ε。成功概率p ||x||² / α²下界p0 1/α²。这里α是LCU中所有系数的和其表达式为α (4√π * κ/(κ1)) * Σ_{l1}^{L} lΔz * e^{-(lΔz)²/2}L和Δz是与κ和ε相关的参数。α的增长约为O(κ √log(κ/ε))因此p0 ∝ 1/(κ² log(κ/ε))。与HHL相比少了因子2因为其LCU结构本身更高效。优势与局限通过将1/x的逼近转化为对e^{-iAt}的求和QLS-Fourier将对精度的依赖从1/ε改善到了log(1/ε)。然而它仍然依赖于哈密顿量模拟并且其成功概率的下界α²仍然较大导致QAA开销显著。3.4 QLS-Chebyshev算法切比雪夫多项式的力量QLS-Chebyshev同样基于LCU但它使用切比雪夫多项式来逼近1/x函数。切比雪夫多项式在函数逼近中具有最优性质这直接带来了性能提升。该算法利用量子行走Quantum Walk算子W来直接实现切比雪夫多项式T_n(A/d)而无需显式的哈密顿量模拟。查询复杂度公式Lemma 5:Q[QLS_Chebyshev] 8 * j0 * n_QAA其中j0 O( dκ * log(dκ/ε) * log( (dκ/ε) / ε ) )它是所需切比雪夫多项式的最高次数近似。成功概率p ||x||² / α²下界p0 1/α²这里α ≈ 4j0/d。关键点查询成本公式中没有哈密顿量模拟项。每一项U_j实现T_{2j1}(A/d)的实现成本是常数与量子行走算子W的调用次数相关而W的每次调用需要固定次数的预言机查询。总查询次数与多项式次数j0和QAA开销n_QAA的乘积成正比。为何更高效摆脱了哈密顿量模拟直接通过量子行走实现多项式避免了e^{-iAt}模拟带来的与t和ε相关的昂贵成本。更优的逼近切比雪夫多项式逼近1/x的效率很高所需的多项式次数j0标度为O(κ log(κ/ε))并且常数因子较小。更紧凑的LCU系数α的增长约为O(j0) ≈ O(κ log(κ/ε))优于QLS-Fourier的O(κ √log(κ/ε))这意味着更高的固有成功概率和更低的QAA开销。3.5 QLS-QSVT算法奇异值变换的现代框架QSVT是近年来出现的统一框架可以视作量子信号处理QSP的矩阵推广。QLS-QSVT利用QSVT来实现一个对矩阵奇异值进行变换的多项式该多项式在区间[1/κ, 1]上近似1/x而在[-1, -1/κ] U [1/κ, 1]之外近似为0通过一个矩形函数实现。查询复杂度公式Lemma 6:Q[QLS_QSVT] 4 * [ n_rect(1/(dκ), min(ε/(4κ), dκ/(2j0))) n_{1/x}(dκ, ε/(4κ)) ]其中n_rect是逼近矩形函数所需的多项式次数。n_{1/x}是逼近1/x函数在有效区间内所需的多项式次数。j0的定义与QLS-Chebyshev中类似。因子4来源于构建矩阵A的块编码Block Encoding所需的预言机调用次数。成功概率p ≈ ||x||² / (4κ²)下界p0 (1 - ε/(2κ))² / (4κ²)。核心机制QSVT通过交替调用一个块编码U_A它包含了归一化后的矩阵A/d及其共轭转置U_A†并在其间插入特定的相位旋转门来实现对A的奇异值施加一个目标多项式变换。对于矩阵求逆这个目标多项式就是P(x) ≈ (1 - rect(κx)) / (2κx)。整个电路不需要显式的QPE或LCU中的高维控制操作结构非常规整。优势QSVT提供了构建此类函数逼近的模块化方法。其查询复杂度直接正比于所需多项的次数而这个次数由函数逼近的理论决定通常具有接近最优的标度。在我们的比较中QLS-QSVT的表现与QLS-Chebyshev非常接近两者都是当前最先进的方法。实操心得公式中的“魔鬼细节”在将这些公式用于实际计算时有几点必须注意解范数||x||这是混合基准测试能提供比理论下界更精确估计的关键。p ||x||² / α²中的||x||是实例相关的。对于随机生成的b||x||可能远小于1因为||b||1但||A^{-1}||可能很大。直接使用理论下界p0会高估QAA开销。因此在经典侧预先计算||x||至关重要。常数因子不要忽略公式中的常数因子如HHL中的c_FQLS-Chebyshev中的8和4/d等。在问题规模不是天文数字时这些常数因子往往决定了算法的实际排序。分段函数与边界条件例如\tilde{r}(t, ε)和n_rect的计算都是分段或包含最小/最大操作。编程实现时需仔细处理这些边界确保在参数变化的临界点附近计算正确。4. 基准测试实施与结果分析我们依据第3章的公式对三类数据集进行了大规模的查询次数计算从而绘制出性能图谱。4.1 测试数据集构建随机数据集Random生成了超过100万个半随机埃尔米特矩阵实例规模从2到1600多万并确保其满足d-稀疏和给定条件数κ的约束。这个数据集用于检验算法在“理想”假设下的表现。单纯形数据集Simplex从MIPLIB的线性规划实例中运行经典单纯形法求解器并从中提取出迭代过程中产生的、良态的基矩阵对应的线性系统。这代表了来自经典优化实际应用的、具有真实世界特征的线性系统。泊松数据集Poisson通过对1维、2维和3维泊松方程狄利克雷边界条件进行有限元离散化生成一系列线性系统。这类问题在科学计算中无处不在其矩阵通常是对称正定、稀疏且具有特定的结构。所有测试均设定目标精度ε 10^{-8}这是一个在科学计算中常见的精度要求。4.2 性能结果总览我们通过热力图Heatmap来可视化算法性能其坐标轴是问题的两个关键参数条件数κ和稀疏度d颜色表示平均查询次数的对数。图1随机数据集上的性能对比此图清晰展示了HHL与其他算法之间的“断层式”差距。HHL的查询次数在10^12到10^18量级而其他三种方法则在10^4到10^10量级。这直接印证了HHL对1/ε依赖带来的巨大代价。在其余三者中QLS-QSVT基于QSVT的整体查询数最低颜色最深表示次数少尤其在κ和d较大的区域优势明显。QLS-Chebyshev次之QLS-Fourier最高。这个结果符合预期因为随机数据集完美符合算法的所有理想假设QSVT和Chebyshev这些更现代、逼近效率更高的方法自然脱颖而出。图2 图3真实世界数据集上的表现在单纯形图2和泊松图3数据集上我们排除了HHL因其成本过高重点比较剩余三者。单纯形数据集QLS-Chebyshev和QLS-QSVT的表现非常接近且显著优于QLS-Fourier。两者查询次数均被压制在10^8以下而QLS-Fourier在部分实例上达到了10^10。QLS-Chebyshev略胜一筹。泊松数据集趋势类似但查询次数的范围更广10^6到10^14。QLS-Chebyshev再次成为综合表现最好的方法QLS-QSVT紧随其后QLS-Fourier则在高κ、高d区域成本急剧上升。表1算法排名总结数据集排名查询次数由少到多关键观察随机QLS-QSVT QLS-Chebyshev QLS-Fourier HHLQSVT在理想条件下略微领先Chebyshev。单纯形QLS-Chebyshev QLS-QSVT QLS-FourierChebyshev方法在实际优化问题中表现最佳。泊松QLS-Chebyshev QLS-QSVT QLS-Fourier在科学计算PDE问题中Chebyshev保持优势。注意事项结果解读的边界混合基准测试的局限性我们的比较只计算了预言机查询次数忽略了状态制备Pb的成本、量子门数量、电路深度、辅助量子比特数等其他资源。在实际硬件上这些因素都可能影响最终性能。例如QLS-QSVT的电路结构可能更规整易于编译和优化。常数因子的影响我们的公式包含了主要的常数因子但不同算法在实现LCU、QAA或QSVT时其量子电路的具体常数开销可能仍有差异。本文的比较是基于查询复杂度这一核心指标的公平比较。“最优”算法的情境依赖性表1显示QLS-Chebyshev在两个真实数据集上领先。但这并不意味着它是所有情况下的绝对赢家。如果问题条件数κ极大或者对精度ε的要求极其严苛远超10^{-8}不同算法之间的优劣关系可能发生变化。我们的方法提供了工具可以让从业者针对自己的具体问题参数代入公式进行计算从而做出最适合的选择。4.3 深入分析HHL的敏感性与QAA开销的影响为了更深入理解性能差异的来源我们在附录中进行了两项补充分析以单纯形数据集为例敏感性分析关于ε我们将HHL的精度要求从ε10^{-8}放宽到ε10^{-2}。如图4所示HHL的查询次数改善了高达7个数量级这生动地说明了HHL对精度的高度敏感性。然而即使在这种对HHL极其有利的宽松精度下其查询次数仍然高于其他三种算法在ε10^{-8}下的要求。这进一步巩固了HHL不适用于高精度求解场景的结论。移除QAA开销在另一个实验中我们假设已知精确的成功概率p而非下界p0从而使用最优的、确定性的振幅放大策略移除了随机化QAA带来的额外期望开销。如图6所示即使在这种近乎理想的放大条件下算法的相对排名QLS-Chebyshev最优QLS-Fourier最差也并未改变。这表明性能差异的根源在于算法核心部分如哈密顿量模拟 vs. 切比雪夫多项式实现的查询效率而非后处理的放大步骤。5. 讨论、结论与未来方向5.1 核心结论与启示本研究通过系统的混合基准测试得出了几个明确且强有力的结论HHL已不适用于实际场景尽管具有历史性和理论重要性但HHL算法由于其O(κ²/ε)的查询复杂度在实际问题中产生的资源需求比其他方法高出多个数量级。除非在精度要求极低、条件数极小的特殊情况下否则不应将其作为实用QLS的首选方案。基于Chebyshev逼近的方法是目前综合最优的选择QLS-Chebyshev在大多数测试场景下特别是来自真实应用单纯形、泊松的数据集上表现出了最低的查询复杂度。其优势在于直接利用量子行走实现高效的切比雪夫多项式逼近避免了昂贵的哈密顿量模拟。QSVT是强大且具竞争力的框架QLS-QSVT的表现与QLS-Chebyshev非常接近在随机数据集上甚至略优。作为更通用的算法框架QSVT为实现更复杂的矩阵函数提供了清晰的路径其模块化特性在算法设计和编译方面可能具有长期优势。混合基准测试方法的有效性这项工作证明在缺乏大规模容错量子硬件的情况下通过经典计算精确估算算法的核心资源如预言机查询次数是一种评估和比较量子算法实用潜力的有效方法。它可以作为算法设计阶段的“试金石”帮助研究者识别并摒弃那些常数因子过大或对参数过于敏感的设计。5.2 对量子算法开发者的建议基于以上发现对正在开发或计划应用QLS的研究者和工程师我们提出以下建议停止将HHL作为默认基线在新的算法论文或应用研究中如果需要对比QLS性能应选择QLS-Chebyshev或QLS-QSVT作为更合理的基准而非HHL。在算法设计中关注常数因子和实际参数范围不要只满足于优化渐进标度。像本研究一样针对目标应用领域的典型问题参数κ, d, ε, N的范围进行具体的资源估算能更早地暴露算法的实际瓶颈。将混合基准测试纳入开发流程为自己设计的QLS变体推导出类似本文的精确查询复杂度公式并在标准数据集上进行测试比较。这能提供比渐进分析更有说服力的性能证据。5.3 未来工作展望本研究自然引向几个未来的研究方向扩展比较范围将绝热量子线性求解器Adiabatic QLS纳入比较框架是一个重要的挑战。虽然它们的假设和实现方式不同但开发一种公平的比较方法论对于全面评估QLS领域至关重要。纳入更多实际开销下一步可以扩展混合基准测试模型加入对状态制备预言机Pb的查询成本、辅助量子比特数、电路深度和总门数量的估算。特别是Pb的成本如果非常高昂可能会改变仅基于矩阵预言机PA的排名。面向特定应用的定制化评估针对机器学习、计算化学、金融建模等具体应用领域构建具有代表性的基准问题集并在此之上评估QLS算法的性能。这能更好地指导领域专家选择适合的量子算法。算法与编译协同优化QLS-QSVT等算法的性能与其实现所需的量子门序列由相位角度决定密切相关。研究如何为特定问题实例高效地生成或编译这些角度可能带来进一步的性能提升。量子计算正从理论走向工程化。在这个过程中像本文所采用的、超越渐进复杂度的、务实性能评估方法对于筛选出真正能在未来量子处理器上带来价值的算法将扮演越来越关键的角色。我们的工作表明在量子线性求解这个核心问题上基于切比雪夫多项式和量子奇异值变换的现代方法已经确立了明显的实用优势为后续的算法应用和软硬件协同设计奠定了更可靠的基础。
