論文の概要: Non-linear Quantum Monte Carlo
- arxiv url: http://arxiv.org/abs/2502.05094v1
- Date: Fri, 07 Feb 2025 17:13:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-10 14:58:41.907072
- Title: Non-linear Quantum Monte Carlo
- Title(参考訳): 非線形量子モンテカルロ
- Authors: Jose Blanchet, Yassine Hamoudi, Mario Szegedy, Guanyang Wang,
- Abstract要約: 量子コンピューティングは、平均推定のための古典モンテカルロ法よりも2次的なスピードアップを提供する。
本研究では,非線形推定問題の幅広いクラスに対して,そのような高速化を実現する量子インサイド量子モンテカルロアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 1.237454174824584
- License:
- Abstract: The mean of a random variable can be understood as a $\textit{linear}$ functional on the space of probability distributions. Quantum computing is known to provide a quadratic speedup over classical Monte Carlo methods for mean estimation. In this paper, we investigate whether a similar quadratic speedup is achievable for estimating $\textit{non-linear}$ functionals of probability distributions. We propose a quantum-inside-quantum Monte Carlo algorithm that achieves such a speedup for a broad class of non-linear estimation problems, including nested conditional expectations and stochastic optimization. Our algorithm improves upon the direct application of the quantum multilevel Monte Carlo algorithm introduced by An et al.. The existing lower bound indicates that our algorithm is optimal up polylogarithmic factors. A key innovation of our approach is a new sequence of multilevel Monte Carlo approximations specifically designed for quantum computing, which is central to the algorithm's improved performance.
- Abstract(参考訳): 確率変数の平均は、確率分布の空間上の$\textit{linear}$関数と解釈できる。
量子コンピューティングは、古典モンテカルロ法による平均推定の2次高速化を提供することで知られている。
本稿では、確率分布の $\textit{non-linear}$関数を推定するために、類似の二次的スピードアップが達成できるかどうかを検討する。
ネスト条件付き予測や確率最適化を含む,幅広い非線形推定問題に対して,そのような高速化を実現する量子内量子モンテカルロアルゴリズムを提案する。
提案アルゴリズムは,An et al によって導入された量子マルチレベルモンテカルロアルゴリズムの直接適用により改善される。
既存の下界は、アルゴリズムが多対数因子を最適にすることを示している。
このアプローチの重要な革新は、量子コンピューティング用に特別に設計されたマルチレベルモンテカルロ近似の新たなシーケンスである。
関連論文リスト
- Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
線形微分方程式に対する量子アルゴリズムを提案する。
アルゴリズムのゲートの複雑さは、次元に依存する$mathcalO(dlog(Nd))$を示す。
アルゴリズムはOrnstein-Uhlenbeck過程、ブラウン運動、L'evy飛行に対して数値的に検証される。
論文 参考訳(メタデータ) (2024-12-19T14:04:11Z) - Quantum Monte Carlo Integration for Simulation-Based Optimisation [34.96100129498306]
シミュレーションに基づく最適化問題のサブルーチンとして量子アルゴリズムを統合する可能性について検討する。
量子モンテカルロ積分の定式化に起因した全ての系統的誤差を徹底的に解析する。
基本的金融ユースケースに対する量子モンテカルロ積分の適用性について検討する。
論文 参考訳(メタデータ) (2024-10-04T21:05:32Z) - Calculating the expected value function of a two-stage stochastic optimization program with a quantum algorithm [0.0]
2段階プログラミングは不確実性の下での意思決定における問題定式化である。
この研究は量子アルゴリズムを用いて、期待値関数をスピードアップで推定する。
論文 参考訳(メタデータ) (2024-02-23T00:07:34Z) - Quadratic Speed-up in Infinite Variance Quantum Monte Carlo [1.2891210250935148]
我々はモンタナロのarXiv/archive:1504.06987量子モンテカルロ法の拡張を与える。
無限分散を示す確率変数の期待値を計算するために調整されている。
論文 参考訳(メタデータ) (2024-01-15T06:31:36Z) - A Survey of Quantum Alternatives to Randomized Algorithms: Monte Carlo
Integration and Beyond [7.060988518771793]
我々は,モンテカルロ法における量子回路を用いた計算速度において,量子的優位性を得る可能性に注目した。
従来のモンテカルロに取って代わる量子アルゴリズムを再検討し、既存の量子アルゴリズムと潜在的な量子実現の両方を考える。
論文 参考訳(メタデータ) (2023-03-08T23:39:49Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Quantum Adversarial Learning in Emulation of Monte-Carlo Methods for
Max-cut Approximation: QAOA is not optimal [0.0]
変分量子アニーリングと量子近似最適化(QAOA)にエミュレーションの概念を適用する。
我々の変分量子アニーリングスケジュールは、同じ物理成分を用いて、QAOAと同様の勾配のない方法で最適化できる新しいパラメータ化に基づいている。
アンス・アッツ型の性能を比較するため,モンテカルロ法の統計的概念を考案した。
論文 参考訳(メタデータ) (2022-11-24T19:02:50Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。
超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。
数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
論文 参考訳(メタデータ) (2022-09-27T17:56:15Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳(メタデータ) (2021-11-30T12:21:41Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳(メタデータ) (2020-06-11T19:40:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。