論文の概要: Quantum amplitude estimation beyond power-of-two schedules
- arxiv url: http://arxiv.org/abs/2609.02715v1
- Date: Wed, 02 Sep 2026 15:20:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-03 17:53:18.445465
- Title: Quantum amplitude estimation beyond power-of-two schedules
- Title（参考訳）: 2つのスケジュールの電力を超える量子振幅推定
- Abstract要約: 非適応量子振幅推定(QAE)はGroverの深さを予め修正しているため、全ての回路が並列に動作可能である。
このギャップのほとんどは、サブスペースベースのポストプロセッシングとパワー・オブ・ツー・ディープ・ラグの2つの従来の選択に由来する。
第1の行列乗算は、推定のバッチごとに1つの行列乗算、第2の行列乗算は、比$r=1.45$の幾何学的はしごによって置き換える。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Non-adaptive quantum amplitude estimation (QAE) fixes its Grover depths in advance, so every circuit can run in parallel, but it has so far needed more queries than the best adaptive methods. We show that most of this gap comes from two conventional choices: subspace-based post-processing and power-of-two depth ladders. We replace the first by the exact maximum-likelihood estimate, one matrix multiplication per batch of estimates, and the second by a geometric ladder with ratio $r \approx 1.45$. The result is a fully parallel, deterministic-schedule estimator with total query complexity $2.8$-$3.1/\varepsilon$ at 95% confidence for target errors from $3.5\times 10^{-3}$ to $10^{-6}$. This matches the average-case complexity of chebAE, the best benchmarked adaptive method, within statistical uncertainty (with the lower point estimate at every scale tested), beats its maximum-observed complexity by $1.6\times$, and needs a maximum sequential depth of only $0.21/\varepsilon$ against chebAE's $2.9/\varepsilon$. Relative to csAE, the best non-adaptive benchmark, the constants improve by 30-35% at 95% and $1.5$-$1.7\times$ at 99% confidence. The optimal ratio has a simple origin. Doubling is the fastest depth growth at which the data can still tell neighboring candidate values apart, so power-of-two ladders sit at the edge of confusion and must buy reliability with extra shots; a slightly denser ladder checks every scale redundantly. An error-probability analysis reproduces the measured failure rates and locates the optimum. The likelihood formulation extends directly to noise-aware estimation, and uniformly scaling the capped ladder covers the depth-limited regime, realizing the optimal trade-off $M N_{\mathrm{tot}} \approx (0.4$-$0.6)/\varepsilon^2$ within $\sim 1.1\times$ of the schedule's Cramér-Rao limit.
- Abstract（参考訳）: 非適応的量子振幅推定(QAE)は、Groverの深さを予め修正しているため、全ての回路が並列に実行できるが、これまでは最高の適応法よりも多くのクエリが必要であった。
このギャップのほとんどは、サブスペースベースのポストプロセッシングとパワー・オブ・ツー・ディープ・ラグの2つの従来の選択に由来する。
第1の行列乗算は、推定のバッチごとに1つの行列乗算、第2の行列乗算は、比$r \approx 1.45$で幾何学的なはしごによって置き換える。
完全な並列で決定論的・スケジュール推定器で、クエリの複雑さは2.8$-$3.1/\varepsilon$で、目標誤差が3.5\times 10^{-3}$から10^{-6}$に95%の信頼性がある。
これは、統計的不確実性(各尺度での低い点推定値)の中で、最もベンチマークされた適応法であるchebAEの平均ケースの複雑さと一致し、最大観測された複雑性を16\times$で打ち負かし、chebAEの2.9/\varepsilon$に対して0.21/\varepsilon$の最大シーケンシャル深さしか必要としない。
最高の非適応ベンチマークであるcsAEとは対照的に、95%で30-35%、信頼で1.5$-1.7\times$で99%改善している。
最適比は単純な起源を持つ。
2つのはしごは混乱の端に座っており、余分なショットで信頼性を買わなければならない。
誤差確率解析は、測定された故障率を再現し、最適な位置を特定する。
確率の定式化は、ノイズ・アウェア推定に直接適用され、キャップ付きはしごを均一にスケーリングすることで、最適トレードオフである$M N_{\mathrm{tot}} \approx (0.4$-0.6)/\varepsilon^2$を、スケジュールのCramér-Rao極限の$\sim 1.1\times$内で実現する。
関連論文リスト
- Nearly Optimal Amplitude Estimation at any Depth [0.0]
我々は、可変回路深さ$M$と回路繰り返し$N$の振幅推定アルゴリズムを開発し、アンシラ量子ビットもグロバー演算も必要としない。
Grover角の加算エラー$$は、ほぼ最適なクエリ-深さトレードオフ$M2NinwidetildeO(-2)$を均一に$in[0,/2]$で達成し、古典的なサンプリングの$M=1$から、Heisenbergの$M=(-1)$までの範囲をまたがる。
論文 参考訳（メタデータ） (2026-08-25T11:46:21Z) - Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳（メタデータ） (2026-07-28T09:29:37Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity [32.65125292684608]
1ビット通信制約を用いた分散平均推定問題について検討する。
私たちの推定器は、有界平均$-lambda le mathbbE(X) le lambda $)と変数$mathrmVar(X) le sigma2$)を持つすべてのディストリビューションに対して$(epsilon, delta)$-PACです。
論文 参考訳（メタデータ） (2025-09-26T06:22:57Z) - Active Subsampling for Measurement-Constrained M-Estimation of Individualized Thresholds with High-Dimensional Data [3.1138411427556445]
測定制約のある問題では、大きなデータセットが利用可能であるにもかかわらず、大きなデータセットのごく一部でラベルを観測するのに手頃な価格にしかならない。
このことは、どのデータポイントが予算制約のあるラベルに最も有益であるかという重要な疑問を引き起こします。
本稿では,測定制約付きM推定フレームワークにおける最適個別化しきい値の推定に焦点をあてる。
論文 参考訳（メタデータ） (2024-11-21T00:21:17Z) - Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。
我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。
我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文 参考訳（メタデータ） (2024-11-20T02:46:15Z) - Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。