論文の概要: Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms
- arxiv url: http://arxiv.org/abs/2507.00823v1
- Date: Tue, 01 Jul 2025 14:55:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-03 14:22:59.675596
- Title: Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms
- Title（参考訳）: 多項式時間動的計画アルゴリズムの量子スピードアップ
- Authors: Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista, Michael T. Goodrich, Martin Nöllenburg,
- Abstract要約: 我々は量子力学プログラミングフレームワークを導入し、古典的動的プログラミングアルゴリズムの大きな体系である量子領域に直接拡張することを可能にする。
対応する量子力学プログラミングアルゴリズムは、計算スピードアップを達成しながら、従来のものと同じ空間の複雑さを保っている。
- 参考スコア（独自算出の注目度）: 4.832760917132771
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem $\mathcal P$ and an instance $I$ of $\mathcal P$, such a speedup can be expressed in terms of the average degree $\delta$ of the dependency digraph $G_{\mathcal{P}}(I)$ of $I$, determined by a recursive formulation of $\mathcal P$. The nodes of this graph are the subproblems of $\mathcal P$ induced by $I$ and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in $\tilde{O}(|V(G_{\mathcal{P}}(I))| \sqrt{\delta})$ time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted $n$-vertex digraph with $m$ edges that runs in $\tilde{O}(n\sqrt{nm})$ time, which improves the best known classical upper bound when $m \in \Omega(n^{1.4})$.
- Abstract（参考訳）: 我々は量子力学プログラミングフレームワークを導入し、古典的動的プログラミングアルゴリズムの大きな体系である量子領域に直接拡張することを可能にする。
対応する量子力学プログラミングアルゴリズムは、計算スピードアップを達成しながら、従来のものと同じ空間の複雑さを保っている。
組合せ(探索または最適化)問題 $\mathcal P$ とインスタンス $I$ of $\mathcal P$ に対して、そのようなスピードアップは従属グラフ $G_{\mathcal{P}}(I)$ の平均次数 $\delta$ で表現でき、$\mathcal P$ の帰納形式によって決定される。
このグラフのノードは$I$によって誘導される$\mathcal P$のサブプロブレムであり、その弧は各サブプロブレムからそれに依存する解へ向けられる。
特に、我々のフレームワークは、$\tilde{O}(|V(G_{\mathcal{P}}(I))| \sqrt{\delta})$ timeで考慮された問題を解くことができる。
例えば、単一ソース頂点から他の頂点への最短経路を計算するためのベルマン・フォードアルゴリズムの量子バージョンを、$m$エッジを持つ重み付き$n$-vertex digraphで、$\tilde{O}(n\sqrt{nm})$timeで実行し、$m \in \Omega(n^{1.4})$のときに最もよく知られた古典的上限を改善する。
関連論文リスト
- Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。
効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。
また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文 参考訳（メタデータ） (2025-02-25T19:08:26Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。
このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
論文 参考訳（メタデータ） (2023-02-06T15:14:34Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳（メタデータ） (2021-04-29T14:50:03Z) - Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
本研究では,事前の約束がなくても,これらのスピードアップが持続することを示すために,修正されたスパンプログラムアルゴリズムを示す。
我々のアルゴリズムは、$tildeO(sqrtkn)$クエリを使って、少なくとも$k$のエッジを持つパスがある場合、この問題を解決する。
論文 参考訳（メタデータ） (2020-12-02T15:32:52Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。