論文の概要: Exponential speedup of quantum algorithms for the pathfinding problem
- arxiv url: http://arxiv.org/abs/2307.12492v3
- Date: Mon, 23 Dec 2024 18:05:32 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-24 15:52:02.881524
- Title: Exponential speedup of quantum algorithms for the pathfinding problem
- Title（参考訳）: パスフィンディング問題に対する量子アルゴリズムの指数的高速化
- Authors: Jianqiang Li,
- Abstract要約: 溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。
古典的なアルゴリズムが確率の高い指数時間で$x$-$y$パスを見つけることはできないことを証明している。
我々の発見は、量子アルゴリズムがパスフィニング問題を解決するために、より多くの種類のグラフに利点をもたらす可能性があることを示唆している。
- 参考スコア（独自算出の注目度）: 5.260626311429307
- License:
- Abstract: Given $x, y$ on an unweighted undirected graph $G$, the goal of the pathfinding problem is to find an $x$-$y$ 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 $x$-$y$ path in the graph $G$. Finally, we prove that no classical algorithm can find an $x$-$y$ path in subexponential time with high probability. The pathfinding problem is one of the fundamental graph-related problems. Our findings suggest that quantum algorithms could potentially offer advantages in more types of graphs to solve the pathfinding problem.
- Abstract（参考訳）: 非重みのないグラフ上の$x, y$が与えられたとき、パスフィンディング問題の目標は、$x$-$y$パスを見つけることである。
本研究では、まず溶接木に基づいてグラフ$G$を構築し、隣接性リスト oracle $O$ においてパスフィニング問題を定義する。
次に、グラフの$G$で$x$-$y$パスを見つけるための効率的な量子アルゴリズムを提供する。
最後に、古典的なアルゴリズムが確率の高い指数時間で$x$-$y$パスを見つけることはできないことを証明した。
パスフィンディング問題は、グラフに関する基本的な問題の1つである。
我々の発見は、量子アルゴリズムがパスフィニング問題を解決するために、より多くの種類のグラフに利点をもたらす可能性があることを示唆している。
関連論文リスト
- Advances in quantum algorithms for the shortest path problem [0.18416014644193066]
我々は、構造化インスタンスの問題を解くために、隣接リストモデルに2つの有界エラー量子アルゴリズムを与える。
最初のアプローチは、量子フロー状態をサンプリングし、より小さな問題に対して古典的なアルゴリズムを実行することによって、元のグラフをスパース化することに基づいている。
2つ目のアプローチは、$tildeO(lsqrtm)$ stepsで最も短いパスを出力する分割および征服手順に基づいている。
論文 参考訳（メタデータ） (2024-08-19T21:30:02Z) - Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs [5.173438526554426]
隣接リストのオラクルによるパスフィンディング問題に対して指数的量子古典的分離を可能にするグラフのクラスを見つける。
通常のヒマワリグラフに$s$-$t$の経路を求めるのに有効な量子アルゴリズムを提供するが、古典的アルゴリズムは指数関数的な時間を要する。
論文 参考訳（メタデータ） (2024-07-19T15:21:13Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - 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) - Quantum Algorithm for Dynamic Programming Approach for DAGs and
Applications [0.0]
有向非巡回グラフ(DAG)問題に対する動的プログラミング手法のための量子アルゴリズムを提案する。
OR, AND, NAND, MAX, MIN 関数を主な遷移ステップとする問題を解くことができることを示す。
論文 参考訳（メタデータ） (2022-12-29T19:07:39Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。