論文の概要: 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)$ と書くことができる。
提案手法は,未調整のランゲヴィンアルゴリズムから導出されるゆっくりと変化するマルコフ鎖の量子的アニーリングに基づいて,混合モデリングと多安定系の大規模データセットに対して計算コストのかかる関数評価の必要性を除去する。
また、ミニバッチ勾配のみを用いて量子ウォーク演算子を不正確に実装する確率勾配オラクルも組み込んだ。
その結果、確率勾配に基づくアルゴリズムは、量子ウォークを実装する際にデータポイントの小さなサブセットにのみアクセスする。
マルコフ連鎖の定量化の課題は、それらが一般に詳細なバランス条件を満たさないことである。
したがって、アルゴリズムの混合時間は遷移密度のスペクトルギャップの観点からは表現できないため、量子アルゴリズムは解析が容易ではない。
これらの課題を克服するために、まずは可逆的かつ対象分布に収束する仮説的マルコフ連鎖を構築する。
そして,この仮説チェーンをブリッジとして,アルゴリズムの出力と目標分布との距離を定量化し,全複雑性を確定した。
我々の量子アルゴリズムは、最もよく知られた古典的アルゴリズムと比較して、次元と精度の両面で多項式の高速化を示す。
関連論文リスト
- Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
論文 参考訳（メタデータ） (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 Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - 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) - Quantum Sampling Algorithms for Near-Term Devices [0.0]
ギブス分布全体を符号化することで、偏りのないサンプルを提供する量子アルゴリズムのファミリを導入する。
このアプローチが従来のマルコフ連鎖アルゴリズムの高速化につながることを示す。
短期量子デバイス上で、潜在的に有用なサンプリングアルゴリズムを探索する扉を開く。
論文 参考訳（メタデータ） (2020-05-28T14:46:20Z) - Oracle Lower Bounds for Stochastic Gradient Sampling Algorithms [39.746670539407084]
我々は、$bbRd$の強い対数凹密度からサンプリングする問題を考察する。
必要なログ密度の勾配クエリ数に基づいて,情報理論の下界を証明した。
論文 参考訳（メタデータ） (2020-02-01T23:46:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。