論文の概要: 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)
• Towards Entropic Constraints on Quantum Speedups [0.0]
  いくつかの量子アルゴリズムは「量子スピードアップ(quantum speedups)」を持ち、同じタスクを解くための最もよく知られた古典的アルゴリズムと比較して、時間複雑性を改善している。 エントロピーの観点から、これらのスピードアップに何をもたらすのか理解できますか? 情報理論は、アルゴリズムを実行する量子コンピュータの振る舞いを「量子」がいかに根本的に測定するかを測定するために、私たちが選択できる様々な指標を与えてくれる。
  論文  参考訳（メタデータ） (2024-11-05T19:00:04Z)
• Demonstrating real-time and low-latency quantum error correction with superconducting qubits [52.08698178354922]
  超伝導量子プロセッサに組み込まれたスケーラブルFPGAデコーダを用いて低遅延フィードバックを示す。 復号ラウンド数が増加するにつれて、論理誤差の抑制が観察される。 この作業でデコーダのスループットとレイテンシが発達し、デバイスの継続的な改善と相まって、次世代の実験がアンロックされた。
  論文  参考訳（メタデータ） (2024-10-07T17:07:18Z)
• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。 同じ手法は他の1次元階層グラフにも適用できる。
  論文  参考訳（メタデータ） (2024-04-30T11:45:49Z)
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem [0.0]
  サイモンの問題は、未知の 2-to-1 関数に符号化された隠された周期を見つけることである。 隠れた周期がハミング重み$w$に制限されたシモン問題の変種に対するアルゴリズム的量子スピードアップを実証する。
  論文  参考訳（メタデータ） (2024-01-15T19:52:31Z)
• Non-Linear Transformations of Quantum Amplitudes: Exponential Improvement, Generalization, and Applications [0.0]
  量子アルゴリズムは量子状態の振幅を操作して計算問題の解を求める。 量子状態の振幅に非線形関数の一般クラスを適用するための枠組みを提案する。 我々の研究は、最適化、状態準備、量子化学、機械学習といった分野において、潜在的に多くの応用が可能な重要かつ効率的なビルディングブロックを提供する。
  論文  参考訳（メタデータ） (2023-09-18T14:57:21Z)
• 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 State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  我々は、$Theta(n)$-depth回路は、$O(ndlog d)$ acillary qubitsを持つ$Theta(log(nd))で作成可能であることを示す。 我々は、ハミルトンシミュレーション、方程式の線形系解法、量子ランダムアクセスメモリの実現など、異なる量子コンピューティングタスクにおける結果の適用について論じる。
  論文  参考訳（メタデータ） (2022-01-27T13:16:30Z)
• Quantum speedup for track reconstruction in particle accelerators [51.00143435208596]
  我々は,各局所追跡法に存在する基本ルーチンを4つ同定し,標準追跡アルゴリズムの文脈でどのようにスケールするかを解析する。 発見された量子スピードアップは穏やかだが、これは私たちの知識の中でも最高のものであり、高エネルギーの物理データ処理タスクに対する量子上の優位性の最初の厳密な証拠である。
  論文  参考訳（メタデータ） (2021-04-23T13:32:14Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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