論文の概要: Grover's Algorithm Offers No Quantum Advantage
- arxiv url: http://arxiv.org/abs/2303.11317v1
- Date: Mon, 20 Mar 2023 17:56:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-21 14:15:37.915548
- Title: Grover's Algorithm Offers No Quantum Advantage
- Title(参考訳): Groverのアルゴリズムは量子アドバンテージを提供しない
- Authors: E.M. Stoudenmire and Xavier Waintal
- Abstract要約: グロバーのアルゴリズムは、量子コンピュータが古典的コンピュータよりも有利であることを示す証拠として提供される主要なアルゴリズムの1つである。
我々は、古典的なコンピュータ上で実行可能な量子インスパイアされたアルゴリズムを構築し、Groverのタスクをオラクルへの線形呼び出し数で実行する。
本研究は, 量子回路の性質に依存した, 実用的な高速化の可能性について批判的に検討する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Grover's algorithm is one of the primary algorithms offered as evidence that
quantum computers can provide an advantage over classical computers. It
involves an "oracle" (external quantum subroutine) which must be specified for
a given application and whose internal structure is not part of the formal
scaling of the quantum speedup guaranteed by the algorithm. Grover's algorithm
also requires exponentially many steps to succeed, raising the question of its
implementation on near-term, non-error-corrected hardware and indeed even on
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 call to the oracle - an exponentially smaller number
than Grover's algorithm - and demonstrate this algorithm explicitly for boolean
satisfiability problems (3-SAT). Our finding implies that there is no a priori
theoretical quantum speedup associated with Grover's algorithm. We critically
examine the possibility of a practical speedup, a possibility that depends on
the nature of the quantum circuit associated with the oracle. We argue that the
unfavorable scaling of the success probability of Grover's algorithm, which in
the presence of noise decays as the exponential of the exponential of the
number of qubits, makes a practical speedup unrealistic even under extremely
optimistic assumptions on both hardware quality and availability.
- Abstract(参考訳): グロバーのアルゴリズムは、量子コンピュータが古典的コンピュータよりも有利であることを示す主要なアルゴリズムの1つである。
oracle(external quantum subroutine)と呼ばれるもので、特定のアプリケーションのために指定され、その内部構造はアルゴリズムによって保証される量子スピードアップの正式なスケーリングの一部ではない。
グローバーのアルゴリズムは、成功するためには指数関数的に多くのステップを必要とするため、短期的、非エラー訂正ハードウェアの実装や、実際はエラー修正量子コンピュータの実装の問題も提起する。
本研究では,古典的コンピュータ上で実行可能な量子インスピレーションアルゴリズムを構築し,Groverのアルゴリズムよりも指数関数的に小さいオラクルに対して,Groverのタスクを線形に呼び出し,このアルゴリズムをブール充足可能性問題(3-SAT)に対して明示的に示す。
我々の発見は、Groverのアルゴリズムに付随する事前理論量子スピードアップが存在しないことを示唆している。
本研究は, 量子回路の性質に依存した, 実用的な高速化の可能性について批判的に検討する。
我々は,量子ビット数の指数関数の指数関数としてノイズ減衰の存在下では,ハードウェア品質と可用性の双方において非常に楽観的な仮定の下でも実用的な高速化が非現実的なものになるグローバーアルゴリズムの成功確率の好ましくないスケーリングを論じている。
関連論文リスト
- Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳(メタデータ) (2023-11-19T00:06:11Z) - Practical limitations of quantum data propagation on noisy quantum
processors [1.2891210250935146]
行列を高い条件数で反転させるのに古典的な計算を必要とする量子アルゴリズムは、誤り確率が非常に低い単一および2量子ゲートを必要とすることを示す。
我々の研究は、ノイズの多い環境下で実行できるハイブリッド量子古典アルゴリズムの主流概念に挑戦する。
論文 参考訳(メタデータ) (2023-06-22T17:12:52Z) - 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) - 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) - Demonstrating robust simulation of driven-dissipative problems on
near-term quantum computers [53.20999552522241]
量子コンピュータは物理学と化学における量子力学系のシミュレーションに革命をもたらす。
現在の量子コンピュータは、訂正されていないノイズ、ゲートエラー、デコヒーレンスのためにアルゴリズムを不完全に実行している。
ここでは、量子力学における最も難しい問題の1つとして、駆動散逸多体問題の解法が本質的にエラーに対して堅牢であることを示す。
論文 参考訳(メタデータ) (2021-08-02T21:36:37Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。