量子科技中心_量科网

在机器学习等应用领域中，大规模数据密集型线性优化（LO）问题的出现，推动了对计算效率更高的内点法（IPMs）的需求。传统内点法虽具有多项式时间复杂度和快速收敛性，但对于稠密大规模线性优化问题，其单次迭代计算成本可能高得难以承受。量子线性系统求解器在加速内点法产生的线性方程组求解方面已展现出潜力。该研究团队提出了一种新型近乎精确的量子内点法：牛顿系统在量子计算机上构建并求解，而解向量更新在经典计算机上执行，且所有矩阵-向量乘积运算均在量子硬件完成。这种量子-经典混合框架对完全稠密线性优化问题实现了最优最坏情况复杂度𝒪(n²)。为确保高精度（尽管量子操作精度有限），该工作将迭代细化技术融入所提内点法的迭代过程内外。该算法具有𝒪(n¹.⁵κ_A log(1/ϵ))次量子随机存取存储器查询复杂度和𝒪(n² log(1/ϵ))次经典算术运算复杂度，其最坏情况复杂度优于现有经典与量子内点法，在可扩展性和计算效率方面实现了显著突破。