Raising the Bar: An Asymptotic Comparison of Classical and Quantum Shortest Path Algorithms
Phuc Hao Do, Tran Duc Le
单源最短路径(SSSP)问题是计算机科学的基石,具有广泛的应用,Dijkstra的算法长期以来一直是经典的基线。 虽然已经提出了各种量子算法,但它们的性能通常与这种几十年来的方法相吻合。 最近,Doutan等人引入了一种新的经典算法,其复杂性为O(m·(log n)^2/3,因此重塑了这种景观。 这一发展需要重新评估SSSP的量子优势叙事。 在本文中,我们根据这一新的经典前沿对现代量子和经典SSSP算法进行了系统的理论比较。 通过分析它们的理论成本函数,我们说明了它们的相对缩放如何比较图密度和路径长度不同的场景。 我们的分析提出了一个微妙的图景:复杂的量子算法,如Wesolowski和Piddock的量子算法,可以表现出更有利的渐近缩放,但只能在以短解决方案路径为特征的系统中。 相反,对于涉及长路径的问题,最先进的经典算法似乎保持缩放优势。 我们的工作为未来量子算法开发提供了最新的视角,并强调追求量子优势是一个动态的竞赛,其中经典的目标柱正在不断变化。
The Single-Source Shortest Path (SSSP) problem is a cornerstone of computer science with vast applications, for which Dijkstra's algorithm has long been the classical baseline. While various quantum algorithms have been proposed, their performance has typically been benchmarked against this decades-old approach. This landscape was recently reshaped by the introduction of a new classical algorithm by Duan et al. with a complexity of O(m · (log n)^2/3). This development necessitates a re-evaluatio...