論文の概要: Advances in quantum algorithms for the shortest path problem

• arxiv url: http://arxiv.org/abs/2408.10427v1
• Date: Mon, 19 Aug 2024 21:30:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-21 17:43:23.873731
• Title: Advances in quantum algorithms for the shortest path problem
• Title（参考訳）: 最短経路問題に対する量子アルゴリズムの進歩
• Authors: Adam Wesołowski, Stephen Piddock,
• Abstract要約: 我々は、構造化インスタンスの問題を解くために、隣接リストモデルに2つの有界エラー量子アルゴリズムを与える。 最初のアプローチは、量子フロー状態をサンプリングし、より小さな問題に対して古典的なアルゴリズムを実行することによって、元のグラフをスパース化することに基づいている。 2つ目のアプローチは、$tildeO(lsqrtm)$ stepsで最も短いパスを出力する分割および征服手順に基づいている。
• 参考スコア（独自算出の注目度）: 0.18416014644193066
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given an undirected, weighted graph, and two special vertices $s$ and $t$, the problem is to find the shortest path between them. We give two bounded-error quantum algorithms in the adjacency list model that solve the problem on structured instances. The first approach is based on sparsifying the original graph via sampling the quantum flow state and running a classical algorithm on the smaller problem. It has time complexity of $\tilde{O}(l^2\sqrt{m})$ and uses $O(\log{l})$ space, where $l$ is the length (or total weight, in case of weighted graphs) of the shortest $s$-$t$ path. The main result is the second approach which is based on a divide and conquer procedure that outputs the shortest path in $\tilde{O}(l\sqrt{m})$ steps when using $O(\log{l})$ space, and can be parallelised to $\tilde{O}(\sqrt{lm})$ circuit depth when using $O(l\log{l})$ space. With the latter we partially resolve with an affirmative answer the open problem of whether a path between two vertices can be found in the time required to detect it.
• Abstract（参考訳）: 無向重み付きグラフと2つの特別な頂点$s$と$t$が与えられたとき、問題はそれらの間の最短経路を見つけることである。 我々は、構造化インスタンスの問題を解くために、隣接リストモデルに2つの有界エラー量子アルゴリズムを与える。 最初のアプローチは、量子フロー状態をサンプリングし、より小さな問題に対して古典的なアルゴリズムを実行することによって、元のグラフをスパース化することに基づいている。 時間複雑性は$\tilde{O}(l^2\sqrt{m})$であり、$O(\log{l})$ space を用いる。 主な結果は、$O(\log{l})$ space を使用すれば $O(\log{l})$ space で最短経路を出力し、$O(l\log{l})$ space を使用すれば $\tilde{O}(\sqrt{lm})$ circuit depth に並列化できる。 後者では、2つの頂点の間の経路がそれを検出するのに必要な時間に見つかるかどうかというオープンな問題に対する肯定的な答えで部分的に解決する。

関連論文リスト

• Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
  非重みのないグラフで$s, t$が与えられたとき、パスフィンディング問題の目標は、$s$-$t$パスを見つけることである。 溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。 古典的なアルゴリズムが確率の高い指数時間で$s$-$t$パスを見つけることはできないことを証明している。
  論文  参考訳（メタデータ） (2023-07-24T02:50:34Z)
• Quantum Algorithm for Dynamic Programming Approach for DAGs and Applications [0.0]
  有向非巡回グラフ(DAG)問題に対する動的プログラミング手法のための量子アルゴリズムを提案する。 OR, AND, NAND, MAX, MIN 関数を主な遷移ステップとする問題を解くことができることを示す。
  論文  参考訳（メタデータ） (2022-12-29T19:07:39Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Leveraging Unknown Structure in Quantum Query Algorithms [0.0]
  本研究では,事前の約束がなくても,これらのスピードアップが持続することを示すために,修正されたスパンプログラムアルゴリズムを示す。 我々のアルゴリズムは、$tildeO(sqrtkn)$クエリを使って、少なくとも$k$のエッジを持つパスがある場合、この問題を解決する。
  論文  参考訳（メタデータ） (2020-12-02T15:32:52Z)
• Quantum complexity of minimum cut [0.2538209532048867]
  隣接行列モデルにおける最小カット問題の量子クエリと時間複雑性を特徴付ける。 我々のアルゴリズムは、Apers and de Wolf (FOCS 2020) によるグラフスカラー化のための量子アルゴリズムを用いており、Kawarabayashi and Thorup (STOC 2015) と Rubinstein, Schramm and Weinberg (ITCS 2018) による準最小カットの構造に関する結果である。
  論文  参考訳（メタデータ） (2020-11-19T13:51:49Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language [1.0118253437732931]
  2つの問題の量子クエリ複雑性について検討する。 グリッドのエッジのいくつかが欠落している場合、グリッドグラフ上の2次元の接続問題を考える。 平衡括弧」問題をグリッドに埋め込むことで、有向2Dグリッドに対して$Omega(n1.5-epsilon)$、無向2Dグリッドに対して$Omega(n2-epsilon)$の低い境界を示す。
  論文  参考訳（メタデータ） (2020-07-06T09:51:41Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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