論文の概要: Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk
- arxiv url: http://arxiv.org/abs/2108.01992v1
- Date: Wed, 4 Aug 2021 12:16:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-19 22:31:23.589424
- Title: Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk
- Title（参考訳）: 連続時間量子ウォークによるジョンソングラフの空間探索
- Authors: Hajime Tanaka, Mohamed Sabri, Renato Portugal
- Abstract要約: 連続時間量子ウォークによるジョンソングラフ上の空間探索は、固定径毎に1ドル程度の成功確率を持つ下界の$pisqrtN/2$を達成することを示す。
この証明は数学的に厳密であり、他のグラフクラスにも利用できる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Spatial search on graphs is one of the most important algorithmic
applications of quantum walks. To show that a quantum-walk-based search is more
efficient than a random-walk-based search is a difficult problem, which has
been addressed in several ways. Usually, graph symmetries aid in the
calculation of the algorithm's computational complexity, and Johnson graphs are
an interesting class regarding symmetries because they are regular,
Hamilton-connected, vertex- and distance-transitive. In this work, we show that
spatial search on Johnson graphs by continuous-time quantum walk achieves the
Grover lower bound $\pi\sqrt{N}/2$ with success probability $1$ asymptotically
for every fixed diameter, where $N$ is the number of vertices. The proof is
mathematically rigorous and can be used for other graph classes.
- Abstract（参考訳）: グラフ上の空間探索は量子ウォークの最も重要なアルゴリズム応用の1つである。
量子ウォークに基づく探索がランダムウォークに基づく探索よりも効率的であることは、いくつかの方法で解決されてきた難しい問題である。
通常、グラフ対称性はアルゴリズムの計算複雑性の計算に役立ち、ジョンソングラフは正則、ハミルトン連結、頂点、距離推移であるので対称性に関する興味深いクラスである。
本研究では,連続時間量子ウォークによるジョンソングラフの空間探索によって,一定の直径毎に漸近的に1ドルの成功確率を持つグロバー下限の$\pi\sqrt{n}/2$が得られることを示す。
この証明は数学的に厳密であり、他のグラフクラスにも利用できる。
関連論文リスト
- Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs [5.173438526554426]
隣接リストのオラクルによるパスフィンディング問題に対して指数的量子古典的分離を可能にするグラフのクラスを見つける。
通常のヒマワリグラフに$s$-$t$の経路を求めるのに有効な量子アルゴリズムを提供するが、古典的アルゴリズムは指数関数的な時間を要する。
論文 参考訳（メタデータ） (2024-07-19T15:21:13Z) - Universal approach to deterministic spatial search via alternating
quantum walks [2.940962519388297]
本稿では,量子ウォークを交互に組み合わせることで,様々なグラフ上で決定論的量子探索アルゴリズムを設計するための新しいアプローチを提案する。
我々のアプローチは、異なるグラフに対してインスタンス固有の分析を必要としないため、普遍的である。
論文 参考訳（メタデータ） (2023-07-30T05:14:19Z) - A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near
Neighbor Graph [51.880164098926166]
グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。
グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。
低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
論文 参考訳（メタデータ） (2023-03-10T21:18:34Z) - Learning Graph Search Heuristics [48.83557172525969]
本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。
我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。
実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
論文 参考訳（メタデータ） (2022-12-07T22:28:00Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。
関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文 参考訳（メタデータ） (2022-07-04T19:33:06Z) - Spatial Search on Johnson Graphs by Discrete-Time Quantum Walk [0.0]
本稿では、ジョンソングラフ上の空間探索問題に量子ウォークモデルを用いて対処する。
すべての固定径に対して、成功確率は、$pisqrt N/(2sqrt 2)$ steps を取った後に1/2$である。
すべての固定径に対して、成功確率は$pisqrt N/ (2sqrt)$ ステップを踏んだ後に1/2$であることを示した。
論文 参考訳（メタデータ） (2021-12-07T15:00:07Z) - Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
既存の量子ウォークに基づく探索アルゴリズムは、サッフル問題に悩まされている。
量子スピードアップを犠牲にすることなくロバスト性を実現する新しい量子ウォークベースの探索フレームワークを提案する。
論文 参考訳（メタデータ） (2021-11-17T10:04:44Z) - A framework for optimal quantum spatial search using alternating
phase-walks [0.0]
我々は、マーク頂点位相シフトと連続時間量子ウォークの交互適用により、Childs & Goldstone(mathcalCG$)アルゴリズムを一般化する。
様々なグラフ上の$mathcalO(sqrtN)$検索にアルゴリズムを適用することで,アルゴリズムの有効性を実証する。
論文 参考訳（メタデータ） (2021-09-29T11:16:52Z) - 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) - Continuous-time quantum walks in the presence of a quadratic
perturbation [55.41644538483948]
連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。
低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
論文 参考訳（メタデータ） (2020-05-13T14:53:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。