論文の概要: Exponential speedup of quantum algorithms for the pathfinding problem
- arxiv url: http://arxiv.org/abs/2307.12492v1
- Date: Mon, 24 Jul 2023 02:50:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-25 15:50:51.410214
- Title: Exponential speedup of quantum algorithms for the pathfinding problem
- Title(参考訳): パスフィンディング問題に対する量子アルゴリズムの指数的高速化
- Authors: Jianqiang Li
- Abstract要約: 非重みのないグラフで$s, t$が与えられたとき、パスフィンディング問題の目標は、$s$-$t$パスを見つけることである。
溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。
古典的なアルゴリズムが確率の高い指数時間で$s$-$t$パスを見つけることはできないことを証明している。
- 参考スコア(独自算出の注目度): 2.357029718308807
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given $s, t$ in an unweighted undirected graph $G$, the goal of the
pathfinding problem is to find an $s$-$t$ path. In this work, we first
construct a graph $G$ based on welded trees and define a pathfinding problem in
the adjacency list oracle $O$. Then we provide an efficient quantum algorithm
to find an $s$-$t$ path in the graph $G$. Finally, we prove that no classical
algorithm can find an $s$-$t$ path in subexponential time with high
probability. The pathfinding problem is one of the fundamental graph-related
problems. Our findings suggest that quantum algorithms may potentially offer
advantages in more types of graphs to solve the pathfinding problem and open up
new possibilities for practical applications of quantum computations in various
fields.
- Abstract(参考訳): unweighted undirected graph $g$の$s, t$が与えられると、pathfinding問題の目標は$s$-$t$パスを見つけることである。
この作業では、最初に溶接木に基づくグラフ$g$を構築し、隣接リストであるoracle $o$でパス検索問題を定義します。
次に、グラフの$G$で$s$-$t$パスを見つけるための効率的な量子アルゴリズムを提供する。
最後に、古典的なアルゴリズムが確率の高い指数時間で$s$-$t$パスを見つけることはできないことを証明した。
パスフィンディング問題はグラフに関する基本的な問題の1つである。
量子アルゴリズムは, 様々な分野における量子計算の実用化に向けて, パスフィニング問題を解き, 新たな可能性を開くために, より多くの種類のグラフに利点をもたらす可能性が示唆された。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳(メタデータ) (2024-02-09T19:01:48Z) - From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。
このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
論文 参考訳(メタデータ) (2023-02-06T15:14:34Z) - Quantum Algorithm for Dynamic Programming Approach for DAGs and
Applications [0.0]
有向非巡回グラフ(DAG)問題に対する動的プログラミング手法のための量子アルゴリズムを提案する。
OR, AND, NAND, MAX, MIN 関数を主な遷移ステップとする問題を解くことができることを示す。
論文 参考訳(メタデータ) (2022-12-29T19:07:39Z) - Learning Graph Search Heuristics [48.83557172525969]
本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。
我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。
実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
論文 参考訳(メタデータ) (2022-12-07T22:28:00Z) - 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) - Quantum algorithms and the power of forgetting [1.5791732557395555]
本研究では,効率の良い量子アルゴリズムの自然なクラスは,ENTRANCEからEXITへの経路を確実に見つけることができないことを示す。
このことは、効率的に経路を見つける量子アルゴリズムの可能性を排除するものではないが、アルゴリズムがこの振る舞いからどのような恩恵を受けるかは定かではない。
論文 参考訳(メタデータ) (2022-11-22T18:04:10Z) - A Generalization of the Shortest Path Problem to Graphs with Multiple
Edge-Cost Estimates [13.046825574678579]
グラフにおける最短経路問題は、AI理論と応用の基礎である。
本稿では,エッジウェイトを複数回(推定)計算できる重み付き有向グラフのフレームワークを提案する。
次に、一般化問題に対する2つの完全アルゴリズムを提示し、その有効性を実証的に示す。
論文 参考訳(メタデータ) (2022-08-22T22:07:27Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。
関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文 参考訳(メタデータ) (2022-07-04T19:33:06Z) - Quantum Algorithm for the Longest Trail Problem [0.0]
最長経路問題に対する量子アルゴリズムを提案する。
アルゴリズムの実行時間は$O* (1.728m)$である。
論文 参考訳(メタデータ) (2021-12-27T09:42:19Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳(メタデータ) (2021-06-11T09:43:09Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。