論文の概要: Quadratic Speed-up in Infinite Variance Quantum Monte Carlo
- arxiv url: http://arxiv.org/abs/2401.07497v2
- Date: Thu, 7 Mar 2024 01:46:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-08 17:04:58.742218
- Title: Quadratic Speed-up in Infinite Variance Quantum Monte Carlo
- Title（参考訳）: 無限可変量子モンテカルロにおける擬似高速化
- Authors: Jose Blanchet, Mario Szegedy, Guanyang Wang
- Abstract要約: 我々はモンタナロのarXiv/archive:1504.06987量子モンテカルロ法の拡張を与える。
無限分散を示す確率変数の期待値を計算するために調整されている。
- 参考スコア（独自算出の注目度）: 1.2891210250935148
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this study, we give an extension of Montanaro's arXiv/archive:1504.06987
quantum Monte Carlo method, tailored for computing expected values of random
variables that exhibit infinite variance. This addresses a challenge in
analyzing heavy-tailed distributions, which are commonly encountered in various
scientific and engineering fields. Our quantum algorithm efficiently estimates
means for variables with a finite $(1+\delta)^{\text{th}}$ moment, where
$\delta$ lies between 0 and 1. It provides a quadratic speedup over the
classical Monte Carlo method in both the accuracy parameter $\epsilon$ and the
specified moment of the distribution. We establish both classical and quantum
lower bounds, showcasing the near-optimal efficiency of our algorithm among
quantum methods. Our work focuses not on creating new algorithms, but on
analyzing the execution of existing algorithms with available additional
information about the random variable. Additionally, we categorize these
scenarios and demonstrate a hierarchy in the types of supplementary information
that can be provided.
- Abstract（参考訳）: 本研究ではモンタナロのarXiv/archive:1504.06987 量子モンテカルロ法の拡張について述べる。
これは、様々な科学・工学分野でよく見られる重尾分布の分析における課題に対処する。
我々の量子アルゴリズムは、有限の$(1+\delta)^{\text{th}}$ moment を持つ変数に対して平均を効率的に推定する。
これは、古典的モンテカルロ法よりも精度パラメータ$\epsilon$と分布の指定モーメントの両方で二次的なスピードアップを提供する。
古典的下界と量子下界の両方を確立し、量子法の中でアルゴリズムの最適に近い効率を示す。
我々の研究は、新しいアルゴリズムを作成することではなく、確率変数に関する追加情報を用いて既存のアルゴリズムの実行を分析することに焦点を当てている。
さらに、これらのシナリオを分類し、提供可能な補足情報の種類における階層構造を示す。
関連論文リスト
- 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) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳（メタデータ） (2023-12-21T18:57:54Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - 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) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳（メタデータ） (2021-11-30T12:21:41Z) - Quantum algorithms for approximate function loading [0.0]
我々は,Grover-RudolphアルゴリズムにインスパイアされたNISQ時代の量子状態生成法を2つ導入した。
上述の滑らかさ条件を超えて関数をロードできる変分アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-15T17:36:13Z) - Quantum-accelerated multilevel Monte Carlo methods for stochastic
differential equations in mathematical finance [1.128265591164748]
我々は微分方程式(SDE)の量子アルゴリズムを研究する。
我々は,モンテカルロ法を一般設定で2次高速化する量子アルゴリズムを提案する。
我々は,このアルゴリズムを,数学的なファイナンスに起因した様々な応用で実演する。
論文 参考訳（メタデータ） (2020-12-11T12:34:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。