量子科技中心_量科网

矩阵乘法的复杂度是计算机科学的核心课题。传统研究主要关注精确算法，但也有大量文献致力于研究能在更短时间内给出近似解的随机算法。该工作采用统一视角，将此类随机算法纳入均值估计框架进行分析。首先，研究人员基于该框架对经典算法给出了更精细的分析：包括Cohen-Lewis（1999年）提出的随机游走算法，以及Sarlós（2006年）与Drineas-Kannan-Mahoney（2006年）提出的草图算法。随后该团队改进了Cohen-Lewis算法——在不使用精确快速矩阵乘法作为子程序的前提下，新提出的单一经典算法速度超越了所有现有方法。其次，通过结合Cornelissen-Hamoudi-Jerbi（2022年）提出的量子多元均值估计算法，该研究团队在这些算法基础上实现了量子加速。