論文の概要: Deterministic spatial search using alternating quantum walks
- arxiv url: http://arxiv.org/abs/2104.03806v2
- Date: Wed, 25 Aug 2021 01:35:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-04 12:03:58.877537
- Title: Deterministic spatial search using alternating quantum walks
- Title（参考訳）: 交互量子ウォークを用いた決定論的空間探索
- Authors: S. Marsh and J. B. Wang
- Abstract要約: 最適な量子ウォーク時間と頂点位相シフトの組に対して、構造化空間探索のための決定論的アルゴリズムが確立されていることを証明した。
これにより、同じグラフのクラスにおける元の空間探索アルゴリズムを改善し、50%の確率しか増幅できないことを示す。
この新たなフレームワークは、グラフ構造の他のファミリーに対する決定論的空間探索に容易に拡張できると期待されている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper examines the performance of spatial search where the Grover
diffusion operator is replaced by continuous-time quantum walks on a class of
interdependent networks. We prove that for a set of optimal quantum walk times
and marked vertex phase shifts, a deterministic algorithm for structured
spatial search is established that finds the marked vertex with 100%
probability. This improves on the original spatial search algorithm on the same
class of graphs, which we show can only amplify to 50% probability. Our method
uses $\left\lceil\frac{\pi}{2\sqrt{2}}\sqrt{N}\right\rceil$ marked vertex phase
shifts for an $N$-vertex graph, making it comparable with Grover's algorithm
for unstructured search. It is expected that this new framework can be readily
extended to deterministic spatial search on other families of graph structures.
- Abstract（参考訳）: 本稿では,Grover拡散演算子を相互依存型ネットワーク上で連続時間量子ウォークに置き換えた空間探索の性能について検討する。
最適量子ウォーク時間と有向頂点位相シフトの組に対して、有向頂点を100%確率で検出する構造化空間探索のための決定論的アルゴリズムを確立する。
これにより、同じグラフのクラスにおける元の空間探索アルゴリズムを改善し、50%の確率しか増幅できないことを示す。
この方法は$n$-vertexグラフに対して$\left\lceil\frac{\pi}{2\sqrt{2}}\sqrt{n}\right\rceil$マークされた頂点位相シフトを用いる。
この新たなフレームワークは、グラフ構造の他のファミリーにおける決定論的空間探索に容易に拡張できると考えられる。
関連論文リスト
- Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。
量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。
このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
論文 参考訳（メタデータ） (2024-07-01T06:09:19Z) - Constant search time algorithm via topological quantum walks [0.0]
本研究では,探索確率を極端に改善した探索時間量子アルゴリズムの実現が可能であることを示す。
具体的には,2次元分割型量子ランダムウォークによって実現された空間探索アルゴリズムについて検討する。
論文 参考訳（メタデータ） (2024-06-26T21:36:47Z) - 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) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。
関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文 参考訳（メタデータ） (2022-07-04T19:33:06Z) - Of Shadows and Gaps in Spatial Search [0.0]
我々は、ハミンググラフやグラスマングラフのような距離正則グラフの族が最適空間探索を持つことを示す。
また、一定の忠実度を持つ空間探索の時間的下界も示し、これは完全忠実度に対するFarhiとGutmannによる境界を延長する。
論文 参考訳（メタデータ） (2022-04-09T02:02:53Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
本稿では,長距離接続を伴う複雑な検索空間上に探索アルゴリズムを構築する。
我々はtextbfIF-NAS という単純なアルゴリズムを提案し、異なるサブネットワークを構築するために周期的なサンプリング戦略を実行する。
提案した探索空間において、IF-NASはランダムサンプリングと従来の重み付け検索のアルゴリズムを有意差で上回っている。
論文 参考訳（メタデータ） (2021-12-05T06:42:48Z) - Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
既存の量子ウォークに基づく探索アルゴリズムは、サッフル問題に悩まされている。
量子スピードアップを犠牲にすることなくロバスト性を実現する新しい量子ウォークベースの探索フレームワークを提案する。
論文 参考訳（メタデータ） (2021-11-17T10:04:44Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。