論文の概要: Quantum walk search by Grover search on coin space
- arxiv url: http://arxiv.org/abs/2503.04031v1
- Date: Thu, 06 Mar 2025 02:30:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-07 17:59:00.646009
- Title: Quantum walk search by Grover search on coin space
- Title（参考訳）: コイン空間上のグローバー探索による量子ウォークサーチ
- Authors: Pulak Ranjan Giri,
- Abstract要約: ラカダシカル量子ウォークは、追加の振幅増幅技術の助けなしに、グラフ上のターゲット頂点を探索することができる。
本稿では,不必要な量子ウォーク探索のための修正コインを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum walk followed by some amplitude amplification technique has been successfully used to search for marked vertices on various graphs. Lackadaisical quantum walk can search for target vertices on graphs without the help of any additional amplitude amplification technique. These studies either exploit AKR or SKW coin to distinguish the marked vertices from the unmarked vertices. The success of AKR coin based quantum walk search algorithms highly depend on the arrangements of the set of marked vertices on the graph. For example, it fails to find adjacent vertices, diagonal vertices and other exceptional configurations of vertices on a two-dimensional periodic square lattice and on other graphs. These coins also suffer from low success probability while searching for marked vertices on a one-dimensional periodic lattice and on other graphs for certain arrangements for marked vertices. In this article, we propose a modified coin for the lackadaisical quantum walk search. It allows us to perform quantum walk search for the marked vertices by doing Grover search on the coin space. Our model finds the marked vertices by searching the self-loops associated with the marked vertices. It can search for marked vertices irrespective of their arrangement on the graph with high success probability. For all analyzed arrangements of the marked vertices the time complexity for 1d-lattice and 2d-lattice are $\mathcal{O}(\frac{N}{M})$ and $\mathcal{O}\left(\sqrt{ \frac{N}{M}\log \frac{N}{M}}\right)$ respectively with constant and high success probability.
- Abstract（参考訳）: 量子ウォークと振幅増幅法は、様々なグラフ上のマークされた頂点の探索に成功している。
ラカダシカル量子ウォークは、追加の振幅増幅技術の助けなしに、グラフ上のターゲット頂点を探索することができる。
これらの研究は、マークされていない頂点とマークされた頂点を区別するために、AKRまたはSKWコインを利用する。
AKRコインに基づく量子ウォーク探索アルゴリズムの成功は、グラフ上のマークされた頂点の集合の配置に大きく依存する。
例えば、隣接する頂点、対角頂点、その他の例外的な頂点の構成を2次元周期的正方格子や他のグラフ上で見つけることができない。
これらのコインはまた、1次元周期格子上のマークされた頂点と、マークされた頂点に対する特定の配置のための他のグラフを探索しながら、成功確率が低い。
本稿では,不必要な量子ウォーク探索のための修正コインを提案する。
これにより、コイン空間上でグロバー探索を行うことで、マークされた頂点の量子ウォーク探索を行うことができる。
我々のモデルは、マークされた頂点に付随する自己ループを探索することにより、マークされた頂点を見つける。
グラフ上の配置に関係なく、高い成功確率でマークされた頂点を探索することができる。
1d-lattice と 2d-lattice の時間複雑性は、解析された全ての頂点の配置に対して $\mathcal{O}(\frac{N}{M})$ と $\mathcal{O}\left(\sqrt{ \frac{N}{M}\log \frac{N}{M}}\right)$ である。
関連論文リスト
- Quantum walk search on a two-dimensional grid with extra edges [0.0]
量子ウォークは、データベースの要素として識別された頂点を持つグラフ上のターゲットの探索に成功している。
我々は,長距離エッジを持つ2次元周期格子上の量子探索において,一定の成功確率を持つ$mathcalO(sqrtN/M)$の最適時間複雑性が達成可能であることを示す。
論文 参考訳（メタデータ） (2025-03-06T02:11:02Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Graph Neural Network Bandits [89.31889875864599]
グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。
この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。
グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
論文 参考訳（メタデータ） (2022-07-13T18:12:36Z) - 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) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
論文 参考訳（メタデータ） (2022-03-27T20:22:17Z) - The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
グラフ関数と出力が同一のグラフニューラルネットワーク(GNN)?
本稿では,この疑問に完全に答え,GNNで表現可能なグラフ問題のクラスを特徴付ける。
この条件は2次的に多くの制約をチェックすることで効率よく検証できることを示す。
論文 参考訳（メタデータ） (2022-02-17T18:54:27Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - Lackadaisical quantum walk in the hypercube to search for multiple
marked vertices [0.0]
本稿では,自己ループを用いたハイパーキューブにおける量子ウォーキングに関するいくつかの問題を実験的に解決する。
隣人がマークされている場合、成功の確率は1ドル近くになる。
論文 参考訳（メタデータ） (2021-08-20T23:19:55Z) - 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) - Lackadaisical quantum walks on 2D grids with multiple marked vertices [0.0]
ラカダシカル量子ウォーク(英: Lackadaisical quantum walk、LQW)は、古典的な遅延ウォークの量子アナログである。
我々は,LQWによる三角形,長方形,ハニカムの2次元格子の探索について数値解析を行った。
論文 参考訳（メタデータ） (2021-04-20T13:33:16Z) - Mining Large Quasi-cliques with Quality Guarantees from Vertex
Neighborhoods [44.007522460918565]
密度の高い部分グラフをマイニングすることは、グラフマイニングタスクのスペクトルにおいて重要なプリミティブである。
実世界のグラフから非自明な大きさのクランプと準クランプをマイニングすることは、しばしば難しい問題ではないことを示す。
論文 参考訳（メタデータ） (2020-08-18T15:50:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。