論文の概要: A mathematical framework for maze solving using quantum walks
- arxiv url: http://arxiv.org/abs/2411.12191v1
- Date: Tue, 19 Nov 2024 03:10:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-20 13:35:25.300819
- Title: A mathematical framework for maze solving using quantum walks
- Title（参考訳）: 量子ウォークを用いた迷路解の数学的枠組み
- Authors: Leo Matsuoka, Hiromichi Ohno, Etsuo Segawa,
- Abstract要約: 本稿では、グローバーウォーク(Grover walk)を用いて迷路の最短経路を識別する枠組みについて述べる。
グラバー・ウォークの有限グラフ上の定常状態の解析は、このアプローチが迷路を効果的に解くことができることを示した。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: We provide a mathematical framework for identifying the shortest path in a maze using a Grover walk, which becomes non-unitary by introducing absorbing holes. In this study, we define the maze as a network with vertices connected by unweighted edges. Our analysis of the stationary state of the Grover walk on finite graphs, where we strategically place absorbing holes and self-loops on specific vertices, demonstrates that this approach can effectively solve mazes. By setting arbitrary start and goal vertices in the underlying graph, we obtain the following long-time results: (i) in tree structures, the probability amplitude is concentrated exclusively along the shortest path between start and goal; (ii) in ladder-like structures with additional paths, the probability amplitude is maximized near the shortest path.
- Abstract（参考訳）: 本稿では、グローバーウォークを用いて迷路の最短経路を識別する数学的枠組みを提案する。
本研究では,この迷路を,非重み付きエッジで接続された頂点を持つネットワークとして定義する。
グラバー・ウォークの定常状態の解析は有限グラフ上にあり、そこでは特定の頂点に吸収孔と自己ループを戦略的に配置し、このアプローチが迷路を効果的に解くことができることを示した。
基礎となるグラフに任意の開始点とゴール頂点を設定することにより、以下の長期的結果が得られる。
(i) 木の構造において、確率振幅は、開始とゴールの間の最短経路にのみ集中する。
(ii) 追加経路を持つはしご状の構造では, 最短経路付近で確率振幅を最大化する。
関連論文リスト
- Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。
植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
論文 参考訳（メタデータ） (2024-02-01T03:39:01Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。
関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文 参考訳（メタデータ） (2022-07-04T19:33:06Z) - Walking on Vertices and Edges by Continuous-Time Quantum Walk [0.0]
私たちは、歩行者が頂点から端までホップできる連続時間量子ウォークのバージョンを定義します。
両部グラフ上の空間探索アルゴリズムをハミルトン版の修正により解析する。
論文 参考訳（メタデータ） (2022-06-07T15:10:18Z) - GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。
提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
論文 参考訳（メタデータ） (2022-05-30T16:22:53Z) - Gaussian Amplitude Amplification for Quantum Pathfinding [0.0]
逐次連結な二部グラフの幾何学に焦点をあて、ガウス分布によって記述可能な解空間を自然に生み出す。
本稿では,これらの分布を符号化したオラクルを用いて振幅増幅による最適経路を解く方法を示す。
論文 参考訳（メタデータ） (2021-12-15T14:41:14Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。
本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
論文 参考訳（メタデータ） (2021-12-08T08:23:37Z) - Deterministic spatial search using alternating quantum walks [0.0]
最適な量子ウォーク時間と頂点位相シフトの組に対して、構造化空間探索のための決定論的アルゴリズムが確立されていることを証明した。
これにより、同じグラフのクラスにおける元の空間探索アルゴリズムを改善し、50%の確率しか増幅できないことを示す。
この新たなフレームワークは、グラフ構造の他のファミリーに対する決定論的空間探索に容易に拡張できると期待されている。
論文 参考訳（メタデータ） (2021-04-08T14:32:48Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Continuous-time quantum walks in the presence of a quadratic
perturbation [55.41644538483948]
連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。
低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
論文 参考訳（メタデータ） (2020-05-13T14:53:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。