論文の概要: 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)
• Quantum Advantage of Noisy Grover's Algorithm [3.803244458097104]
  グロバーの探索アルゴリズムは、古典的な探索アルゴリズムの可能性を証明した唯一の量子アルゴリズムである。 本稿では,Groverアルゴリズムの雑音閾値を指数関数的に改善する耐雑音性手法を提案する。
  論文  参考訳（メタデータ） (2023-06-19T11:17:32Z)
• Quantum Multiplication Algorithm Based on the Convolution Theorem [0.0]
  時間複雑性を持つ整数乗算の量子アルゴリズムをO(sqrtnlog2 n)$で提案する。 Harveyアルゴリズムとは異なり、我々のアルゴリズムは極大数にのみ適用できるという制限はない。 また、古典的乗法アルゴリズムの歴史と発展を概観し、量子資源がこの根本的な問題に対してどのように新たな視点と可能性を提供できるかを探求する動機付けとなる。
  論文  参考訳（メタデータ） (2023-06-14T12:40:54Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。 我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。 最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
  論文  参考訳（メタデータ） (2023-05-17T18:00:06Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• 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)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。