論文の概要: Weakly Measured Loops for Quantum Amplitude Amplification: Oracle Savings and Adaptive Search with Unknown Target Probability
- arxiv url: http://arxiv.org/abs/2609.39621v1
- Date: Wed, 30 Sep 2026 12:32:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-01 18:57:27.760585
- Title: Weakly Measured Loops for Quantum Amplitude Amplification: Oracle Savings and Adaptive Search with Unknown Target Probability
- Title（参考訳）: 量子振幅増幅のための弱測定ループ:未知のターゲット確率を持つOracleの節約と適応検索
- Abstract要約: 本稿では、通常のグローバー回転をループの弱い測定でインターリーブする量子振幅増幅アルゴリズムの族を示す。
成功した測定が目標状態となり、アルゴリズムが停止するが、失敗した後、ループは再起動することなく測定後の状態から再開する。
- 参考スコア（独自算出の注目度）: 1.9950682531209158
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a family of quantum amplitude amplification algorithms that interleave ordinary Grover rotations with tunable weak measurements in loops. A successful measurement yields the target state and stops the algorithm, while after a failure, the loop resumes from the post-measurement state without restarting. We express the leading costs in expected Grover iterations as $p \to 0$. For a known target probability $p$, an exact weak measurement-conditioned loop for states near the angle $π/4$ uses $(π/8+1/4+o(1))/\sqrt{p}$ iterations, improving on the standard Grover constant $π/4$ and on optimised restart Grover, and matching the corresponding infimum in our continuous-angle analysis. When only a lower bound $0 < p_0 \leq p < 1/2$ is available, a discrete Lyapunov equation gives the exact expected oracle cost for every fixed measurement strength and a closed-form optimal strength. Using the strength selected from $p_0$, the expected number of Grover iterations is at most $\frac{1}{2\sqrt{2}}(\frac{1}{\sqrt{p}}+\frac{1}{\sqrt{p_0}})$, where the expected cost decreases as the actual $p$ increases, and gives the leading constant $1/\sqrt{2}$ at the promise boundary $p = p_0$. For completely unknown $p$, we identify measurement strength $κ(t)=Θ(1/t)$ as the critical scale within the regular schedules considered here and analyse $κ_b(t)=\min\{1/2,b/t\}$. For each fixed $b > 2$, we rigorously derive a closed-form Gamma-function expression $C(b)$ giving $(C(b)/2+o(1))/\sqrt{p}$ expected iterations. Numerical minimisation of this explicit expression gives $b \approx 5.2$ and $C(b)/2 \approx 1.01$. The results show that weak measurements preserve the $Θ(1/\sqrt{p})$ search scale while adding an explicit fixed-point control mechanism and provable oracle savings.
- Abstract（参考訳）: 本稿では、通常のグローバー回転をループで調整可能な弱い測定でインターリーブする量子振幅増幅アルゴリズムの族を示す。
成功した測定が目標状態となり、アルゴリズムが停止するが、失敗した後、ループは再起動することなく測定後の状態から再開する。
期待されるGroverイテレーションのリードコストを$p \to 0$と表現します。
既知の目標確率 $p$ に対して、角度 $π/4$ に近い状態に対する正確な測度条件付きループは、$(π/8+1/4+o(1))/\sqrt{p}$ 反復を使用し、標準グロバー定数 $π/4$ と最適化された再起動グロバーで改善し、連続角解析において対応する無限小と一致する。
下限の$0 < p_0 \leq p < 1/2$しか得られないとき、離散リアプノフ方程式は、任意の固定された測定強度と閉形式の最適強度に対して正確なオラクルコストを与える。
p_0$ から選択された強さを用いて、グロバー反復の期待値は、最大$\frac{1}{2\sqrt{2}}(\frac{1}{\sqrt{p}}+\frac{1}{\sqrt{p_0}})$である。
完全に未知の$p$に対して、測定強度 $κ(t) = (1/t)$ を、ここで考慮される正規スケジュールにおける臨界スケールとし、$κ_b(t)=\min\{1/2,b/t\}$ を解析する。
固定された $b > 2$ に対して、我々は厳格に閉形式ガンマ関数式 $C(b)$$$(C(b)/2+o(1))/\sqrt{p}$期待反復を導出する。
この明示的な表現の数値最小化は$b \approx 5.2$と$C(b)/2 \approx 1.01$を与える。
その結果, 弱測定は, 明示的な固定点制御機構と証明可能なオラクルセーブを付加しながら, 探索スケールを$1/\sqrt{p})$保存することを示した。
関連論文リスト
- Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。
本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。
結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
論文 参考訳（メタデータ） (2026-08-12T14:54:15Z) - Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation [8.375876290025586]
正方形距離は確率分布間の差を測定するのによく使われるツールである。
我々は,サンプルの正規カルテシアングリッドスケッチを導入するためのSample-$計算パラダイムを開発した。
我々は、$W(P, Q)$を$-max(2,fracd+1+o(1)1+)$ time for $0 1$ Hlder smooth distributions の$$エラー内で近似する。
論文 参考訳（メタデータ） (2026-05-19T17:10:47Z) - Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling: Tight Upper and Lower Bounds [7.787109481104569]
ランダムシャッフルに基づくサブサンプリングによるDP-SGDのトレードオフ関数の厳密な解析を導出する。
Berry-Esseenの定理によって導かれる我々の具体的な境界は、証明フレームワーク内の定数要素に密着している。
論文 参考訳（メタデータ） (2026-05-07T13:35:43Z) - Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
論文 参考訳（メタデータ） (2025-08-09T08:28:06Z) - Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
この仮定は、収束とより微細な結果には必要ないことが初めて示される。
標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。
数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
論文 参考訳（メタデータ） (2024-05-28T05:11:05Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Faster Sampling from Log-Concave Distributions over Polytopes via a
Soft-Threshold Dikin Walk [28.431572772564518]
我々は、$d$-dimensional log-concave distribution $pi(theta) propto e-f(theta)$からポリトープ$K$に制約された$m$不等式をサンプリングする問題を考える。
我々の主な成果は、少なくとも$O((md + d L2 R2) times MDomega-1) log(fracwdelta)$ arithmetic operation to sample from $pi$ の "soft-warm' variant of the Dikin walk Markov chain" である。
論文 参考訳（メタデータ） (2022-06-19T11:33:07Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。
また、ディキンウォークの「ソフトパイ」バージョンも提示する。
論文 参考訳（メタデータ） (2021-11-07T13:44:50Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。