論文の概要: Opening the Black Box Inside Grover's Algorithm
- arxiv url: http://arxiv.org/abs/2303.11317v2
- Date: Wed, 13 Nov 2024 04:01:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-14 19:24:57.442547
- Title: Opening the Black Box Inside Grover's Algorithm
- Title（参考訳）: グローバーのアルゴリズムでブラックボックスが開く
- Authors: E. M. Stoudenmire, Xavier Waintal,
- Abstract要約: グロバーのアルゴリズムは、量子コンピュータが古典的コンピュータよりも有利であることを示す主要なアルゴリズムである。
我々は,古典的コンピュータ上で動作可能な量子インスパイアされたアルゴリズムを構築し,Groverのタスクを,オラクルへの(シミュレーションの)呼び出し数で線形に実行する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Grover's algorithm is a primary algorithm offered as evidence that quantum computers can provide an advantage over classical computers. It involves an "oracle" specified for a given application whose structure is not part of the formal scaling of the quadratic speedup guaranteed by the algorithm. Grover's algorithm also requires exponentially many calls to the quantum oracle to succeed (about $\sqrt{2^n}$ calls for $n$ qubits), raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm, executable on a classical computer, that performs Grover's task in a linear number of calls to (simulations of) the oracle - an exponentially smaller number than Grover's algorithm - and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once which may or may not be exponential. Indeed, Grover's algorithm does not have an a priori quantum speedup as soon as one is given access to the "source code" of the oracle. Our findings illustrate this point explicitly as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There remain problems where Grover's algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of circuit complexity, for quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover's algorithm - which in the presence of noise decays as a double exponential in the number of qubits - makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability.
- Abstract（参考訳）: グローバーのアルゴリズムは、量子コンピュータが古典的コンピュータよりも有利であることを示す主要なアルゴリズムである。
アルゴリズムによって保証される二次的なスピードアップの形式的スケーリングの一部ではない、与えられたアプリケーションに指定された「オークル」を含む。
グローバーのアルゴリズムはまた、量子オラクルへの指数関数的に多くの呼び出し(約$\sqrt{2^n}$call for $n$ qubits)を成功させる必要があり、ノイズと誤り訂正された量子コンピュータの実装に関する疑問が提起される。
本研究では,古典的コンピュータ上で動作可能な量子インスピレーション付きアルゴリズムを構築し,Groverのアルゴリズムよりも指数関数的に小さいオラクルへの(シミュレーションの)呼び出し数でGroverのタスクを実行し,このアルゴリズムをブール適合性問題に対して明示的に実証する。
アルゴリズムの複雑さは、指数的であろうとなかろうと、一度オラクルをシミュレートするコストに依存する。
実際、グローバーのアルゴリズムは、託宣の「ソースコード」へのアクセスが与えられるとすぐに、先験的な量子スピードアップを持たない。
我々のアルゴリズムは、量子コンピュータをプログラムして探索を高速化するために使用される量子回路の構造を利用するため、この点を明確に示している。
グローバーのアルゴリズムが十分な大きさで正確に実行できれば、漸近的なスピードアップを提供するという問題はまだ残っている。
我々の量子インスパイアされたアルゴリズムは、回路の複雑さの観点から、量子ハードウェアがこれらの問題に対する古典的なアプローチに打ち勝つための低いバウンドを提供する。
これらの推定は、Groverのアルゴリズムの成功確率の好ましくないスケーリング(量子ビット数の倍指数としてノイズ減衰が存在すること)と組み合わせて、ハードウェア品質と可用性の両方の進化の極めて楽観的な仮定の下でも、現実的なスピードアップを非現実的なものにする。
関連論文リスト
- Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Quantum Advantage of Noisy Grover's Algorithm [3.803244458097104]
グロバーの探索アルゴリズムは、古典的な探索アルゴリズムの可能性を証明した唯一の量子アルゴリズムである。
本稿では,Groverアルゴリズムの雑音閾値を指数関数的に改善する耐雑音性手法を提案する。
論文 参考訳（メタデータ） (2023-06-19T11:17:32Z) - Recovering the original simplicity: succinct and deterministic quantum
algorithm for the welded tree problem [0.0]
この研究は、よく知られた溶接木問題に対する量子アルゴリズムを再考する。
最も単純な量子ウォークに基づく非常に簡潔な量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-17T16:03:50Z) - 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) - Iterative Qubits Management for Quantum Index Searching in a Hybrid
System [56.39703478198019]
IQuCSは、量子古典ハイブリッドシステムにおけるインデックス検索とカウントを目的としている。
我々はQiskitでIQuCSを実装し、集中的な実験を行う。
その結果、量子ビットの消費を最大66.2%削減できることが示されている。
論文 参考訳（メタデータ） (2022-09-22T21:54:28Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Hybrid Quantum-Classical Search Algorithms [0.0]
古典計算は,探索問題自体が解けない限り,量子計算を補助できないことを示す。
我々はこの結果を、不安定な成功確率を持つアルゴリズムに一般化する。
論文 参考訳（メタデータ） (2022-02-23T11:43:17Z) - Hardware Efficient Quantum Search Algorithm [17.74233101199813]
本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。
我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。
回路コストの削減は、システムの成功率を著しく向上させる。
論文 参考訳（メタデータ） (2021-03-26T01:08:50Z) - Quantum Computing without Quantum Computers: Database Search and Data
Processing Using Classical Wave Superposition [101.18253437732933]
スピン波重畳を用いた磁気データベース探索の実験データを示す。
古典的な波動に基づくアプローチは、量子コンピュータと同じ速度でデータベース検索を行う場合もあると我々は論じる。
論文 参考訳（メタデータ） (2020-12-15T16:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。