論文の概要: Amplitude amplification and estimation require inverses
- arxiv url: http://arxiv.org/abs/2507.23787v1
- Date: Thu, 31 Jul 2025 17:59:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-01 17:19:10.31033
- Title: Amplitude amplification and estimation require inverses
- Title（参考訳）: 振幅増幅と推定は逆を必要とする
- Authors: Ewin Tang, John Wright,
- Abstract要約: ブルートフォースサーチとカウントのための一般的な量子スピードアップは、私たちがそれらを適用するプロセスが効率的に逆転できるときにのみ保持される。
我々は、U$のみを使用するアルゴリズムが、単純で二次的に遅いアプローチに勝るような、トレース推定に基づく問題インスタンスを提示する。
逆アクセスなしでは、量子スピードアップが不足しており、それに伴い量子スピードアップが増加しています。
- 参考スコア（独自算出の注目度）: 3.084918555654188
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove that the generic quantum speedups for brute-force search and counting only hold when the process we apply them to can be efficiently inverted. The algorithms speeding up these problems, amplitude amplification and amplitude estimation, assume the ability to apply a state preparation unitary $U$ and its inverse $U^\dagger$; we give problem instances based on trace estimation where no algorithm which uses only $U$ beats the naive, quadratically slower approach. Our proof of this is simple and goes through the compressed oracle method introduced by Zhandry. Since these two subroutines are responsible for the ubiquity of the quadratic "Grover" speedup in quantum algorithms, our result explains why such speedups are far harder to come by in the settings of quantum learning, metrology, and sensing. In these settings, $U$ models the evolution of an experimental system, so implementing $U^\dagger$ can be much harder -- tantamount to reversing time within the system. Our result suggests a dichotomy: without inverse access, quantum speedups are scarce; with it, quantum speedups abound.
- Abstract（参考訳）: ブルートフォースサーチとカウントのための一般的な量子スピードアップは、それらを適用するプロセスが効率よく逆転できる場合にのみ成り立つことを証明している。
これらの問題を高速化するアルゴリズム、振幅増幅と振幅推定、状態準備単位の$U$とその逆の$U^\dagger$を仮定する。
我々の証明は単純であり、Zhandryが導入した圧縮オラクル法を通している。
これらの2つのサブルーチンは、量子アルゴリズムにおける二次的な"グラバー"スピードアップのユビキティを担っているため、量子学習、メトロジー、センシングの設定において、そのようなスピードアップがはるかに困難である理由を説明します。
これらの設定では、$U$は実験システムの進化をモデル化するので、$U^\dagger$を実装するのは非常に難しい。
逆アクセスなしでは、量子スピードアップが不足しており、それに伴い量子スピードアップが増加している。
関連論文リスト
- Augmenting Simulated Noisy Quantum Data Collection by Orders of Magnitude Using Pre-Trajectory Sampling with Batched Execution [47.60253809426628]
提案手法は,誤差型を調整して軌道シミュレーションの効率化と有効性を高めることを目的としている。
私たちはそれぞれ100兆枚と100万枚という膨大なデータセットを生成します。
論文 参考訳（メタデータ） (2025-04-22T22:36:18Z) - Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。
我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
論文 参考訳（メタデータ） (2025-02-13T12:04:39Z) - Demonstrating real-time and low-latency quantum error correction with superconducting qubits [52.08698178354922]
超伝導量子プロセッサに組み込まれたスケーラブルFPGAデコーダを用いて低遅延フィードバックを示す。
復号ラウンド数が増加するにつれて、論理誤差の抑制が観察される。
この作業でデコーダのスループットとレイテンシが発達し、デバイスの継続的な改善と相まって、次世代の実験がアンロックされた。
論文 参考訳（メタデータ） (2024-10-07T17:07:18Z) - Grover Speedup from Many Forms of the Zeno Effect [0.0]
我々は、他のゼノ効果の現示が、物理的に現実的なモデルにおいて最適なスピードアップをサポートすることを示す。
我々はこれらのアルゴリズムを3つのファミリーに分類し、スピードアップがどのように得られるかの構造化された理解を容易にする。
論文 参考訳（メタデータ） (2023-05-18T17:40:32Z) - Quantum Computing Provides Exponential Regret Improvement in Episodic
Reinforcement Learning [35.11103784048256]
有限水平MDPの学習を容易にするために,textitUpper Confidence Bound (UCB) ベースの量子アルゴリズムフレームワークを提案する。
我々の量子アルゴリズムは、古典的なアルゴリズムと比較して、後悔の指数的な改善を実現している。
論文 参考訳（メタデータ） (2023-02-16T23:01:27Z) - One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。
これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
論文 参考訳（メタデータ） (2023-01-05T11:05:22Z) - Quantum speedup for track reconstruction in particle accelerators [51.00143435208596]
我々は,各局所追跡法に存在する基本ルーチンを4つ同定し,標準追跡アルゴリズムの文脈でどのようにスケールするかを解析する。
発見された量子スピードアップは穏やかだが、これは私たちの知識の中でも最高のものであり、高エネルギーの物理データ処理タスクに対する量子上の優位性の最初の厳密な証拠である。
論文 参考訳（メタデータ） (2021-04-23T13:32:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。