論文の概要: Raising the Bar: An Asymptotic Comparison of Classical and Quantum Shortest Path Algorithms

• arxiv url: http://arxiv.org/abs/2508.12074v1
• Date: Sat, 16 Aug 2025 15:16:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-19 14:49:10.551469
• Title: Raising the Bar: An Asymptotic Comparison of Classical and Quantum Shortest Path Algorithms
• Title（参考訳）: バーのライジング:古典的および量子的最短経路アルゴリズムの漸近比較
• Authors: Phuc Hao Do, Tran Duc Le,
• Abstract要約: Dijkstraのアルゴリズムは、長い間、シングルソースショート・パス問題の古典的なベースラインであった。 ランドスケープは、O(m cdot (log n)2/3)$の複雑さを持つ新しい古典的アルゴリズムの導入によって、最近再形成された。 より高度な量子アルゴリズムは、より好ましいスケーリングを示すが、短い解経路によって特徴づけられるレギュレーションに限られることを示す。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: SSSP問題(Single-Source Shortest Path)は、Dijkstraのアルゴリズムが長年にわたって古典的なベースラインであった膨大な応用のコンピュータ科学の基盤である。 様々な量子アルゴリズムが提案されているが、その性能は通常、この数十年前のアプローチに対してベンチマークされている。 この風景は、Duanらによる新しい古典的アルゴリズムの導入によって、O(m \cdot (\log n)^{2/3})$の複雑さによって、最近再形成された。 この発展は、SSSPの量子優位性物語の再評価を必要とする。 本稿では,この古典的フロンティアに照らして,現代量子および古典的SSSPアルゴリズムの体系的理論的比較を行う。 理論的コスト関数の解析を通じて,グラフ密度と経路長の異なるシナリオ間で相対スケーリングがどのように比較されるかを説明する。 Wesolowski や Piddock などの高度な量子アルゴリズムは、より好適な漸近的スケーリングを示すことができるが、短い解経路によって特徴づけられるレジームに限られる。 逆に、長い経路に関わる問題に対して、最先端の古典的アルゴリズムはスケーリングの優位性を維持しているように見える。 我々の研究は、将来の量子アルゴリズム開発に対する最新の視点を提供し、量子優位性の追求は、古典的なゴールポストが絶えずシフトしている動的なレースである、と強調する。

関連論文リスト

• Efficient Learning Implies Quantum Glassiness [0.0]
  量子学習理論とアルゴリズムの硬さの驚くべき関係を示す。 量子アルゴリズムの「Lipschitz」では,スパース乱れの量子系の近傍状態の発見が平均的に困難であることを示す。
  論文  参考訳（メタデータ） (2025-04-30T18:00:29Z)
• Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis [1.9081120388919084]
  量子コンピュータは、最先端の古典的手法よりも優れたスケールのリソースを用いて、半定値プログラム(SDP)を解くことができる。 本稿では,量子SDPソルバの非漸近的リソース要求の解析を行う。
  論文  参考訳（メタデータ） (2025-02-21T12:54:05Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL [0.562479170374811]
  我々は、Harrow, Hassidim and Lloyd (HHL) によって提案された方程式の線形系に対するよく知られたアルゴリズムを、直接解法ではなく予測子-相関子に適応させることにより適用する。 この戦略は、多くの古典的アルゴリズムでよく見られる計算コストの高いステップのインテリジェントな省略を可能にし、同時に量子状態の抽出に関連する悪名高い読み出し問題を緩和する。 このアプローチの汎用性は、滑らかな粒子流体力学、プラズマシミュレーション、反応性流れ構成など、様々な分野の応用を通して説明される。
  論文  参考訳（メタデータ） (2024-06-28T15:31:10Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。 結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
  論文  参考訳（メタデータ） (2023-04-17T16:42:05Z)
• A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits [3.5707423185282665]
  永続ベッチ数を計算するための改良された量子アルゴリズムを提案する。 量子アルゴリズムが実用的なタスクの指数的高速化を達成できるかどうかを論じる。
  論文  参考訳（メタデータ） (2022-09-26T17:56:11Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。