論文の概要: Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants
- arxiv url: http://arxiv.org/abs/2210.06539v1
- Date: Wed, 12 Oct 2022 19:10:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-14 17:55:33.615027
- Title: Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants
- Title（参考訳）: 対数凹分布のサンプリングと正規化定数推定のための量子アルゴリズム
- Authors: Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, Ruizhe
Zhang
- Abstract要約: 我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
- 参考スコア（独自算出の注目度）: 8.453228628258778
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a convex function $f\colon\mathbb{R}^{d}\to\mathbb{R}$, the problem of
sampling from a distribution $\propto e^{-f(x)}$ is called log-concave
sampling. This task has wide applications in machine learning, physics,
statistics, etc. In this work, we develop quantum algorithms for sampling
log-concave distributions and for estimating their normalizing constants
$\int_{\mathbb{R}^d}e^{-f(x)}\mathrm{d} x$. First, we use underdamped Langevin
diffusion to develop quantum algorithms that match the query complexity (in
terms of the condition number $\kappa$ and dimension $d$) of analogous
classical algorithms that use gradient (first-order) queries, even though the
quantum algorithms use only evaluation (zeroth-order) queries. For estimating
normalizing constants, these algorithms also achieve quadratic speedup in the
multiplicative error $\epsilon$. Second, we develop quantum Metropolis-adjusted
Langevin algorithms with query complexity $\widetilde{O}(\kappa^{1/2}d)$ and
$\widetilde{O}(\kappa^{1/2}d^{3/2}/\epsilon)$ for log-concave sampling and
normalizing constant estimation, respectively, achieving polynomial speedups in
$\kappa,d,\epsilon$ over the best known classical algorithms by exploiting
quantum analogs of the Monte Carlo method and quantum walks. We also prove a
$1/\epsilon^{1-o(1)}$ quantum lower bound for estimating normalizing constants,
implying near-optimality of our quantum algorithms in $\epsilon$.
- Abstract（参考訳）: 凸関数 $f\colon\mathbb{r}^{d}\to\mathbb{r}$ が与えられたとき、分布 $\propto e^{-f(x)}$ からサンプリングする問題は log-concave sampling と呼ばれる。
このタスクは、機械学習、物理学、統計など、幅広い応用がある。
本研究では、対数凹分布をサンプリングし、正規化定数 $\int_{\mathbb{R}^d}e^{-f(x)}\mathrm{d} x$ を推定するための量子アルゴリズムを開発する。
まず、量子アルゴリズムが評価(ゼロオーダー)クエリのみを使用するにもかかわらず、勾配(一階)クエリを使用する類似の古典的アルゴリズムのクエリ複雑性(条件番号$\kappa$および次元$d$)に一致する量子アルゴリズムを開発する。
定数の正規化を推定するために、これらのアルゴリズムは乗算誤差 $\epsilon$ の二次高速化も達成する。
次に,モンテカルロ法と量子ウォークの量子アナログを利用して,モンテカルロ法および量子ウォークの多項式スピードアップを達成するために,量子メトロポリス調整ランゲインアルゴリズムをクエリ複雑性$\widetilde{O}(\kappa^{1/2}d^{3/2}/\epsilon)$と$\widetilde{O}(\kappa^{1/2}d^{3/2}/\epsilon)$で開発する。
また、正規化定数を推定するために1/\epsilon^{1-o(1)$の量子下界を証明し、量子アルゴリズムのほぼ最適性を$\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) - Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳（メタデータ） (2023-12-21T18:57:54Z) - Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
量子アルゴリズムは多対数あるいは指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができることを示す。
また、量子アルゴリズムが多対数または指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができる領域を特徴付ける。
論文 参考訳（メタデータ） (2022-12-05T19:10:32Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳（メタデータ） (2020-09-09T18:00:09Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。