論文の概要: Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma
- arxiv url: http://arxiv.org/abs/2403.02057v2
- Date: Thu, 6 Jun 2024 10:26:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-07 21:02:35.716319
- Title: Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma
- Title（参考訳）: 固定点量子探索の再検討:準チェビシェフ補題の証明
- Authors: Guanzhong Li, Lvzhou Li,
- Abstract要約: グローバーのアルゴリズムはソッフル問題に悩まされており、これは量子探索の成功確率が、時間が小さすぎる場合や、適切な時間から大きすぎる場合、劇的に減少することを意味する。
ソッフル問題を克服するため、最適なクエリ数を持つ固定点量子探索を提案した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The original Grover's algorithm suffers from the souffle problem, which means that the success probability of quantum search decreases dramatically if the iteration time is too small or too large from the right time. To overcome the souffle problem, the fixed-point quantum search with an optimal number of queries was proposed [Phys. Rev. Lett. 113, 210501 (2014)], which always finds a marked state with a high probability when a lower bound of the proportion of marked states is given. The fixed-point quantum search relies on a key lemma regarding the explicit formula of recursive quasi-Chebyshev polynomials, but its proof is not given explicitly. In this work, we give a detailed proof of this lemma, thus providing a sound foundation for the correctness of the fixed-point quantum search. This lemma may be of independent interest as well, since it expands the mathematical form of the recursive relation of Chebyshev polynomials of the first kind, and it also constitutes a key component in overcoming the souffle problem of quantum walk-based search algorithms, for example, robust quantum walk search on complete bipartite graphs [Phys. Rev. A 106, 052207 (2022)]. Hopefully, more applications of the lemma will be found in the future.
- Abstract（参考訳）: 元のGroverのアルゴリズムはソッフル問題に悩まされており、イテレーション時間が小さすぎる場合や、適切な時間から大きすぎる場合、量子探索の成功確率は劇的に低下する。
ソッフル問題を克服するために、最適なクエリ数を持つ固定点量子探索(Phys. Rev. Lett. 210501 (2014)]を提案した。
固定点量子探索は、再帰的準チェビシェフ多項式の明示的な公式に関する鍵補題に依存するが、その証明は明示的には与えられない。
本研究では、この補題の詳細な証明を行い、固定点量子探索の正当性に関する健全な基礎を提供する。
この補題は、第一種のチェビシェフ多項式の帰納関係の数学的形式を拡張し、また、量子ウォークに基づく探索アルゴリズムのソッフル問題(例えば、完全二部グラフ上のロバストな量子ウォーク探索(Phys. Rev. A 106, 052207 (2022))))を克服する重要な要素である。
将来的には、この補題のさらなる応用が期待できる。
関連論文リスト
- Constant search time algorithm via topological quantum walks [0.0]
本研究では,探索確率を極端に改善した探索時間量子アルゴリズムの実現が可能であることを示す。
具体的には,2次元分割型量子ランダムウォークによって実現された空間探索アルゴリズムについて検討する。
論文 参考訳（メタデータ） (2024-06-26T21:36:47Z) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Optimization of probabilistic quantum search algorithm with a priori
information [0.21756081703276003]
グロバーの量子探索アルゴリズムは古典計算よりも量子コンピューティングの優位性を証明する典型的な量子アルゴリズムである。
本稿では,一般の確率分布を持つデータベースの故障確率をゼロにできる確率論的グロバー探索アルゴリズムについて考察する。
論文 参考訳（メタデータ） (2023-04-06T04:33:37Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Hypercube Quantum Search: Exact Computation of the Probability of
Success in Polynomial Time [0.1957338076370071]
グロバーの量子探索は最も重要な量子アルゴリズムの1つである。
本稿では,ハイパーキューブレイアウト上の量子探索について詳細に検討する。
論文 参考訳（メタデータ） (2022-02-25T21:05:38Z) - Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
既存の量子ウォークに基づく探索アルゴリズムは、サッフル問題に悩まされている。
量子スピードアップを犠牲にすることなくロバスト性を実現する新しい量子ウォークベースの探索フレームワークを提案する。
論文 参考訳（メタデータ） (2021-11-17T10:04:44Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - 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) - Transition Probabilities in Generalized Quantum Search Hamiltonian
Evolutions [0.0]
本研究では、連続時間量子探索問題において、ソース状態からターゲット状態への遷移確率を計算するために必要な計算面について検討する。
最小探索時間の観点からは、よく知られたFarhi-Gutmannアナログ量子探索アルゴリズムよりも優れていることが分かる。
論文 参考訳（メタデータ） (2020-02-06T13:16:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。