量子科技中心_量科网

量子线性系统（QLS）求解器是一类基础的量子算法，在机器学习、微分方程求解等众多潜在量子计算应用中具有重要作用。量子算法的性能通常通过查询复杂度来衡量，该指标量化了访问输入数据所需的oracle调用次数。决定QLS求解器复杂度的主要参数包括线性系统的条件数κ、稀疏度s以及目标误差ϵ。迄今为止，最著名的查询复杂度下界为Ω(κlog(1/ϵ))，这证明了最新QLS求解器的最优性。该下界的原始证明归功于Harrow和Kothari，但其成果未正式发表。此外，在讨论包含系统稀疏度s的更普遍下界时，学界普遍认为应表述为Ω(κs√log(1/ϵ))。该工作建立了严格捕获QLS稀疏度依赖性的下界证明，针对恒定误差的QLS量子算法，该团队证明了Ω(κs√)的下界。虽然参数κ、s、ϵ之间的完整依赖关系仍是未解难题，但这一成果为全面刻画QLS复杂度奠定了关键基石。