論文の概要: Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions
- arxiv url: http://arxiv.org/abs/2310.11445v1
- Date: Tue, 17 Oct 2023 17:55:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 14:37:58.286635
- Title: Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions
- Title(参考訳): 非logconcave分布の確率的量子サンプリングと分割関数の推定
- Authors: Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi, Chunhao Wang
- Abstract要約: 非対数確率分布からサンプリングする量子アルゴリズムを提案する。
f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
- 参考スコア(独自算出の注目度): 13.16814860487575
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present quantum algorithms for sampling from non-logconcave probability
distributions in the form of $\pi(x) \propto \exp(-\beta f(x))$. Here, $f$ can
be written as a finite sum $f(x):= \frac{1}{N}\sum_{k=1}^N f_k(x)$. Our
approach is based on quantum simulated annealing on slowly varying Markov
chains derived from unadjusted Langevin algorithms, removing the necessity for
function evaluations which can be computationally expensive for large data sets
in mixture modeling and multi-stable systems. We also incorporate a stochastic
gradient oracle that implements the quantum walk operators inexactly by only
using mini-batch gradients. As a result, our stochastic gradient based
algorithm only accesses small subsets of data points in implementing the
quantum walk. One challenge of quantizing the resulting Markov chains is that
they do not satisfy the detailed balance condition in general. Consequently,
the mixing time of the algorithm cannot be expressed in terms of the spectral
gap of the transition density, making the quantum algorithms nontrivial to
analyze. To overcome these challenges, we first build a hypothetical Markov
chain that is reversible, and also converges to the target distribution. Then,
we quantified the distance between our algorithm's output and the target
distribution by using this hypothetical chain as a bridge to establish the
total complexity. Our quantum algorithms exhibit polynomial speedups in terms
of both dimension and precision dependencies when compared to the best-known
classical algorithms.
- Abstract(参考訳): 本稿では,非logconcave確率分布から$\pi(x) \propto \exp(-\beta f(x))$でサンプリングする量子アルゴリズムを提案する。
ここで、$f$ は有限和 $f(x):= \frac{1}{N}\sum_{k=1}^N f_k(x)$ と書くことができる。
提案手法は,未調整のランゲヴィンアルゴリズムから導出されるゆっくりと変化するマルコフ鎖の量子的アニーリングに基づいて,混合モデリングと多安定系の大規模データセットに対して計算コストのかかる関数評価の必要性を除去する。
また、ミニバッチ勾配のみを用いて量子ウォーク演算子を不正確に実装する確率勾配オラクルも組み込んだ。
その結果、確率勾配に基づくアルゴリズムは、量子ウォークを実装する際にデータポイントの小さなサブセットにのみアクセスする。
マルコフ連鎖の定量化の課題は、それらが一般に詳細なバランス条件を満たさないことである。
したがって、アルゴリズムの混合時間は遷移密度のスペクトルギャップの観点からは表現できないため、量子アルゴリズムは解析が容易ではない。
これらの課題を克服するために、まずは可逆的かつ対象分布に収束する仮説的マルコフ連鎖を構築する。
そして,この仮説チェーンをブリッジとして,アルゴリズムの出力と目標分布との距離を定量化し,全複雑性を確定した。
我々の量子アルゴリズムは、最もよく知られた古典的アルゴリズムと比較して、次元と精度の両面で多項式の高速化を示す。
関連論文リスト
- Quantum Algorithms for the Pathwise Lasso [1.9374282535132377]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
論文 参考訳(メタデータ) (2023-12-21T18:57:54Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash
Equilibrium [62.51015395213579]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
提案アルゴリズムは粒子の動きを利用して$ilon$-mixed Nash平衡のランダム戦略の更新を表現する。
論文 参考訳(メタデータ) (2023-03-02T05:08:15Z) - Concise and Efficient Quantum Algorithms for Distribution Closeness
Testing [0.2741266294612775]
本研究では, 量子計算が分布特性の試験の基礎的問題に与える影響について検討する。
この問題に対して現在最高の量子アルゴリズムを$l1$-distanceと$l2$-distanceのメトリクスで提案する。
論文 参考訳(メタデータ) (2023-02-13T04:03:59Z) - Importance sampling for stochastic quantum simulations [68.8204255655161]
我々は、係数に応じてハミルトン式からサンプリングしてランダムな積公式を構築するqDriftプロトコルを導入する。
サンプリング段階における個別のシミュレーションコストを考慮し、同じ精度でシミュレーションコストを削減可能であることを示す。
格子核効果場理論を用いて数値シミュレーションを行った結果, 実験結果が得られた。
論文 参考訳(メタデータ) (2022-12-12T15:06:32Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳(メタデータ) (2022-10-12T19:10:43Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Faster quantum mixing of Markov chains in non-regular graph with fewer
qubits [0.0]
量子の場合、マルコフ連鎖からのqsamplingは、定常分布の平方根に任意に近い振幅を持つ量子状態の準備として構成することができる。
本稿では,すべての可逆マルコフ連鎖に対する新しいqsamplingアルゴリズムを離散時間量子ウォークを用いて構築する。
非正規グラフでは、量子高速フォワードアルゴリズムの起動は、離散時間と連続時間の両方で既存の最先端のqsamplingアルゴリズムを加速させる。
論文 参考訳(メタデータ) (2022-05-12T14:08:08Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z) - Quantum Sampling Algorithms for Near-Term Devices [0.0]
ギブス分布全体を符号化することで、偏りのないサンプルを提供する量子アルゴリズムのファミリを導入する。
このアプローチが従来のマルコフ連鎖アルゴリズムの高速化につながることを示す。
短期量子デバイス上で、潜在的に有用なサンプリングアルゴリズムを探索する扉を開く。
論文 参考訳(メタデータ) (2020-05-28T14:46:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。