Raising the Bar: An Asymptotic Comparison of Classical and Quantum Shortest Path Algorithms

• URL: http://arxiv.org/abs/2508.12074v1
• Date: Sat, 16 Aug 2025 15:16:02 GMT
• Title: Raising the Bar: An Asymptotic Comparison of Classical and Quantum Shortest Path Algorithms
• Authors: Phuc Hao Do, Tran Duc Le,
• Abstract summary: Dijkstra's algorithm has long been the classical baseline for the Single-Source Shortest Path problem.<n>The landscape was recently reshaped by the introduction of a new classical algorithm with a complexity of $O(m cdot (log n)2/3)$.<n>We show that sophisticated quantum algorithms can exhibit more favorable scaling, but only in regimes characterized by short solution paths.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 \cdot (\log n)^{2/3})$. This development necessitates a re-evaluation of the quantum advantage narrative for SSSP. In this paper, we conduct a systematic theoretical comparison of modern quantum and classical SSSP algorithms in light of this new classical frontier. Through an analysis of their theoretical cost functions, we illustrate how their relative scaling compares across scenarios that vary in graph density and path length. Our analysis suggests a nuanced picture: sophisticated quantum algorithms, such as the one by Wesolowski and Piddock, can exhibit more favorable asymptotic scaling, but only in regimes characterized by short solution paths. Conversely, for problems involving long paths, state-of-the-art classical algorithms appear to maintain a scaling advantage. Our work provides an updated perspective for future quantum algorithm development and underscores that the pursuit of quantum advantage is a dynamic race where the classical goalposts are continually shifting.

Related papers

• Quantum DPLL and Generalized Constraints in Iterative Quantum Algorithms [0.0]
  We explore a class of hybrid quantum algorithms that are closely related to classical greedy or local search algorithms.<n>We develop a hybrid quantum version of the well-known classical Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability problems.
  arXiv  Detail & Related papers  (2025-09-02T18:00:05Z)
• Efficient Learning Implies Quantum Glassiness [0.0]
  We show a surprising relation between quantum learning theory and algorithmic hardness.<n>We show that finding near-ground states of certain sparse disordered quantum systems is average-case hard for "Lipschitz" quantum algorithms.
  arXiv  Detail & Related papers  (2025-04-30T18:00:29Z)
• Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis [1.9081120388919084]
  Quantum computers can solve semidefinite programs (SDPs) using resources that scale better than state-of-the-art classical methods.<n>We present an analysis of the non-asymptotic resource requirements of a quantum SDP solver.
  arXiv  Detail & Related papers  (2025-02-21T12:54:05Z)
• Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
  We propose quantum algorithms for linear differential equations.<n>The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions.<n>The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
  arXiv  Detail & Related papers  (2024-12-19T14:04:11Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL [0.562479170374811]
  We adapt a well-known algorithm for linear systems of equations, originally proposed by Harrow, Hassidim and Lloyd (HHL), by adapting it into a predictor-corrector instead of a direct solver. This strategy enables the intelligent omission of computationally costly steps commonly found in many classical algorithms, while simultaneously mitigating the notorious readout problems associated with extracting a quantum state. The versatility of the approach is illustrated through applications in various fields such as smoothed particle hydrodynamics, plasma simulations, and reactive flow configurations.
  arXiv  Detail & Related papers  (2024-06-28T15:31:10Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  Quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs. Results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical.
  arXiv  Detail & Related papers  (2023-04-17T16:42:05Z)
• A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits [3.5707423185282665]
  We present an improved quantum algorithm for computing persistent Betti numbers.<n>We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest.
  arXiv  Detail & Related papers  (2022-09-26T17:56:11Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.