量子科技中心_量科网

单源最短路径（SSSP）问题是计算机科学领域的核心课题，其应用场景广泛，长期以来迪杰斯特拉算法被视为经典基准。尽管已有多种量子算法被提出，但它们的性能评估通常仍以这一数十年前的算法为参照。这一局面最近被段氏团队提出的新型经典算法打破——该算法实现了O(m·(log n)^(2/3))的复杂度突破。这一进展迫使学界重新审视量子算法在SSSP问题上的优势论述。本文基于这一经典算法的新进展，对现代量子与经典SSSP算法进行了系统性理论比较。通过分析其理论代价函数，研究人员揭示了它们在图像密度和路径长度不同场景下的相对扩展性差异。分析表明：韦索洛夫斯基和皮多克提出的精密量子算法虽能展现出更优的渐近扩展性，但仅适用于解路径较短的场景；反之，在涉及长路径的问题中，最先进的经典算法仍保持扩展优势。该工作为未来量子算法研发提供了更新视角，同时强调量子优势的探索是一场动态竞赛——经典算法的标杆始终处于移动之中。