論文の概要: Optimal Quantum Speedups for Repeatedly Nested Expectation Estimation

• arxiv url: http://arxiv.org/abs/2602.08120v1
• Date: Sun, 08 Feb 2026 20:55:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:24.988807
• Title: Optimal Quantum Speedups for Repeatedly Nested Expectation Estimation
• Title（参考訳）: 繰り返しネスト予測推定のための最適量子スピードアップ
• Authors: Yihang Sun, Guanyang Wang, Jose Blanchet,
• Abstract要約: 本研究では, 量子コンピューティングを用いて, 一定の水平線(ネスト数)で繰り返しネスト予測(RNE)を推定する。 本稿では、対数係数まで、コスト$tilde O(varepsilon-1)$で$varepsilon$-errorを実現する量子アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 4.479120626873489
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the estimation of repeatedly nested expectations (RNEs) with a constant horizon (number of nestings) using quantum computing. We propose a quantum algorithm that achieves $\varepsilon$-error with cost $\tilde O(\varepsilon^{-1})$, up to logarithmic factors. Standard lower bounds show this scaling is essentially optimal, yielding an almost quadratic speedup over the best classical algorithm. Our results extend prior quantum speedups for single nested expectations to repeated nesting, and therefore cover a broader range of applications, including optimal stopping. This extension requires a new derandomized variant of the classical randomized Multilevel Monte Carlo (rMLMC) algorithm. Careful de-randomization is key to overcoming a variable-time issue that typically increases quantized versions of classical randomized algorithms.
• Abstract（参考訳）: 本研究では, 量子コンピューティングを用いて, 一定の水平線(ネスト数)で繰り返しネスト予測(RNE)を推定する。 我々は,対数係数まで,コスト$\tilde O(\varepsilon^{-1})$で$\varepsilon$-errorを実現する量子アルゴリズムを提案する。 標準的な下限は、このスケーリングが本質的に最適であることを示し、古典的アルゴリズムよりもほぼ2倍のスピードアップが得られることを示している。 我々の結果は、単一ネスト予測の前の量子スピードアップを繰り返しネストに拡張し、したがって最適な停止を含む幅広いアプリケーションをカバーする。 この拡張には、古典的ランダム化マルチレベルモンテカルロ (rMLMC) アルゴリズムの新しいデランドマイズ版が必要である。 注意深い非ランダム化は、古典的ランダム化アルゴリズムの量子化バージョンを通常増加させる可変時間問題を克服する鍵である。

関連論文リスト

• Quantum Speedup for Sampling Random Spanning Trees [2.356162747014486]
  我々は、$widetildeO(sqrtmn)$ timeの重み付きグラフからランダムスパンニング木をサンプリングする量子アルゴリズムを提案する。 我々のアルゴリズムは、高密度グラフのサブ線形ランタイムを持ち、よく知られた古典的アルゴリズムの量子スピードアップを実現する。
  論文  参考訳（メタデータ） (2025-04-22T05:45:04Z)
• Optimization by Decoded Quantum Interferometry [38.063836468778895]
  Decoded Quantum Interferometry (DQI) は、量子フーリエ変換を用いて、復号化問題に対する最適化問題を削減する量子アルゴリズムである。 有限体上の最適適合を近似するために、DQIは既知の古典的アルゴリズムよりも超多項式的なスピードアップを達成する。
  論文  参考訳（メタデータ） (2024-08-15T17:47:42Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
  最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。 この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
  論文  参考訳（メタデータ） (2023-11-17T20:38:38Z)
• Quantum speedup of leverage score sampling and its application [0.0]
  本稿では,レバレッジスコアの計算を高速化する量子アルゴリズムを提案する。 応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-15T14:40:18Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。 我々はモンテカルロ法と量子ウォークの量子アナログを利用する。 また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
  論文  参考訳（メタデータ） (2022-10-12T19:10:43Z)
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions [4.2698418800007865]
  古典ハミルトニアンの分配関数を所定の温度で近似するための古典的および量子的アルゴリズムを提案する。 我々は,vStefankovivc,Vempala,Vigodaの古典的アルゴリズムを改良し,サンプルの複雑さを改善する。 我々はこの新しいアルゴリズムを量子化し、HarrowとWeiにより、この問題に対してこれまで最速の量子アルゴリズムを改善した。
  論文  参考訳（メタデータ） (2020-09-23T17:27:28Z)

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

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