論文の概要: Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
- arxiv url: http://arxiv.org/abs/2111.09012v4
- Date: Sat, 19 Nov 2022 12:05:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-07 21:55:11.736720
- Title: Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
- Title（参考訳）: マーク付き頂点の数を知らずにロバストな量子ウォークサーチ
- Authors: Yongzhen Xu, Delong Zhang, Lvzhou Li
- Abstract要約: 既存の量子ウォークに基づく探索アルゴリズムは、サッフル問題に悩まされている。
量子スピードアップを犠牲にすることなくロバスト性を実現する新しい量子ウォークベースの探索フレームワークを提案する。
- 参考スコア（独自算出の注目度）: 0.2320417845168326
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: There has been a very large body of research on searching a marked vertex on
a graph based on quantum walks, and Grover's algorithm can be regarded as a
quantum walk-based search algorithm on a special graph. However, the existing
quantum walk-based search algorithms suffer severely from the souffl\'{e}
problem which mainly means that the success probability of finding a marked
vertex could shrink dramatically even to zero when the number of search steps
is greater than the right one, thus heavily reducing the robustness and
practicability of the algorithm. Surprisingly, while the souffl\'{e} problem of
Grover's algorithm has attracted enough attention, how to address this problem
for general quantum walk-based search algorithms is missing in the literature.
Here we initiate the study of overcoming the souffl\'{e} problem for quantum
walk-based search algorithms by presenting a new quantum walk-based search
framework that achieves robustness without sacrificing the quantum speedup. In
this framework, for any adjustable parameter $\epsilon$, the quantum algorithm
can find a marked vertex on an $N$-vertex {\it complete bipartite graph} with
probability at least $ 1-\epsilon$, whenever the number of search steps $h$
satisfies $h \geq \ln(\frac{2}{\sqrt{\epsilon}})\sqrt{N} + 1$. Note that the
algorithm need not know the exact number of marked vertices. Consequently, we
obtain quantum search algorithms with stronger robustness and practicability.
- Abstract（参考訳）: 量子ウォークに基づくグラフ上のマークされた頂点の探索に関する非常に大きな研究が行われており、グローバーのアルゴリズムは特別なグラフ上の量子ウォークに基づく探索アルゴリズムとみなすことができる。
しかし、既存の量子ウォークに基づく探索アルゴリズムは、suffl\'{e}問題に苦しめられている。つまり、マークされた頂点を見つける成功確率は、検索ステップ数が正しいステップ数よりも大きい場合にもゼロまで劇的に減少し、アルゴリズムのロバスト性と実用性が大幅に低下することを意味する。
驚くべきことに、グローバーのアルゴリズムのsouffl\'{e}問題は十分な注目を集めているが、一般の量子ウォークに基づく探索アルゴリズムのこの問題への対処方法は文献に欠けている。
ここでは,量子ウォークに基づく探索アルゴリズムにおけるsouffl\'{e}問題を克服する研究を開始し,量子スピードアップを犠牲にすることなく頑健性を実現する新しい量子ウォークに基づく探索フレームワークを提案する。
この枠組みでは、任意の調整可能なパラメータ $\epsilon$ に対して、量子アルゴリズムは、少なくとも 1-\epsilon$ の確率を持つ$n$-vertex {\it complete bipartite graph} 上のマークされた頂点を、探索ステップ $h$ が $h \geq \ln(\frac{2}{\sqrt{\epsilon}})\sqrt{n} + 1$ を満たすときに見つけることができる。
アルゴリズムはマークされた頂点の正確な数を知る必要はない。
その結果,強固なロバスト性と実用性を有する量子探索アルゴリズムが得られる。
関連論文リスト
- Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices [7.922488341886121]
本稿では,完全多部グラフ上での量子ウォーク探索アルゴリズムについて検討する。
我々は、量子ウォークモデルを用いて、二次的なスピードアップを実現する。
また、量子アルゴリズムの数値シミュレーションと回路実装も提供する。
論文 参考訳（メタデータ） (2024-10-07T11:13:41Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Quantum algorithms and the power of forgetting [1.5791732557395555]
本研究では,効率の良い量子アルゴリズムの自然なクラスは,ENTRANCEからEXITへの経路を確実に見つけることができないことを示す。
このことは、効率的に経路を見つける量子アルゴリズムの可能性を排除するものではないが、アルゴリズムがこの振る舞いからどのような恩恵を受けるかは定かではない。
論文 参考訳（メタデータ） (2022-11-22T18:04:10Z) - Improvement of quantum walk-based search algorithms in single marked
vertex graphs [0.0]
増幅増幅は通常、成功確率を増幅するために使用されるが、サッフル問題は続く。
本研究では,探索アルゴリズムの成功確率の向上とソッフル問題回避を両立できる一般化補間量子ウォークを定義する。
論文 参考訳（メタデータ） (2022-09-09T07:43:46Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantum Approximate Counting for Markov Chains and Application to
Collision Counting [0.0]
我々は,ブラザード,ホイヤー,タップ(ICALP 1998)によって開発された量子近似計数法を一般化し,マルコフ連鎖のマーク状態の数を推定する方法を示す。
これにより、Magniez、Nayak、Roland、Santhaによって確立された強力な"量子ウォークベースサーチ"フレームワークに基づいて、量子検索アルゴリズムから量子近似カウントアルゴリズムを構築することができる。
論文 参考訳（メタデータ） (2022-04-06T03:04:42Z) - 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) - Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
特定の演算を行うユニタリ行列が与えられた場合、等価な量子回路を得るのは非自明な作業である。
量子ウォーカーのコイン、トフォリゲート、フレドキンゲートの3つの問題が研究されている。
提案したアルゴリズムは量子回路の分解に効率的であることが証明され、汎用的なアプローチとして、利用可能な計算力によってのみ制限される。
論文 参考訳（メタデータ） (2021-06-06T13:15:25Z) - Quantum walk-based search algorithms with multiple marked vertices [0.0]
量子ウォークは量子アルゴリズムを開発するための強力なツールである。
我々は、Szegedyの量子ウォークに基づく従来の解析手法を拡張した。
2次元格子とハイパーキューブ上の量子ウォークに基づく2つの例は、我々の方法の詳細を示している。
論文 参考訳（メタデータ） (2021-03-23T22:57:07Z) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。
我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。
我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
論文 参考訳（メタデータ） (2020-12-03T07:12:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。