論文の概要: Enabling Quantum Speedup of Markov Chains using a Multi-level Approach
- arxiv url: http://arxiv.org/abs/2210.14088v1
- Date: Tue, 25 Oct 2022 15:17:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-21 16:07:02.440094
- Title: Enabling Quantum Speedup of Markov Chains using a Multi-level Approach
- Title（参考訳）: マルチレベルアプローチによるマルコフ連鎖の量子スピードアップの実現
- Authors: Xiantao Li
- Abstract要約: マルコフ連鎖を混合する量子スピードアップは、ゆっくりと変化する$r$マルコフ鎖の構成に基づいて達成できる。
低分解能マルコフ鎖の密度関数を用いてマルコフ鎖を高分解能で温めることができることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum speedup for mixing a Markov chain can be achieved based on the
construction of slowly-varying $r$ Markov chains where the initial chain can be
easily prepared and the spectral gaps have uniform lower bound. The overall
complexity is proportional to $r$. We present a multi-level approach to
construct such a sequence of $r$ Markov chains by varying a resolution
parameter $h.$ We show that the density function of a low-resolution Markov
chain can be used to warm start the Markov chain with high resolution. We prove
that in terms of the chain length the new algorithm has $O(1)$ complexity
rather than $O(r).$
- Abstract（参考訳）: マルコフ鎖を混合するための量子スピードアップは、初期鎖が容易に作成でき、スペクトルギャップが均一な下界を持つ、ゆっくりと変化する$r$マルコフ鎖の構成に基づいている。
全体の複雑さは$r$に比例する。
解像度パラメータ $h を変化させることで、$r$マルコフ連鎖を構成するためのマルチレベルアプローチを提案する。
例えば、低分解能マルコフ鎖の密度関数は、高分解能でマルコフ鎖を温めるのに使うことができる。
連鎖長の観点では、新しいアルゴリズムは$o(r)ではなく$o(1)$の複雑さを持つことが証明される。
$
関連論文リスト
- Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
非対数確率分布からサンプリングする量子アルゴリズムを提案する。
f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
論文 参考訳（メタデータ） (2023-10-17T17:55:32Z) - Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
我々は、ある微分方程式のオイラー・マルヤマ離散化のように見える、より一般で幅広いマルコフ連鎖、伊藤鎖を考える。
伊藤鎖の法則と微分方程式の間の$W_2$-距離の有界性を証明する。
論文 参考訳（メタデータ） (2023-10-09T18:38:56Z) - Stochastic Gradient Descent under Markovian Sampling Schemes [3.04585143845864]
マルコフ型サンプリングスキームにのみアクセス可能なバニラ勾配勾配の変動について検討する。
我々は、基礎となるマルコフ連鎖で可能な最小限の制限的な仮定の下で収束率を得ることに焦点をあてる。
論文 参考訳（メタデータ） (2023-02-28T09:18:00Z) - A rapidly mixing Markov chain from any gapped quantum many-body system [2.321323878201932]
我々は、$pi(x)=|langle x|psirangle|2$ からビット文字列 $x$ を考える。
我々の主な結果は、逆スペクトルギャップ$H$と関連する連続時間Markov Chainと定常状態$pi$の混合時間との直接リンクを記述する。
論文 参考訳（メタデータ） (2022-07-14T16:38:42Z) - Space-efficient Quantization Method for Reversible Markov Chains [1.558664512158522]
Szegedy氏は、任意の可逆マルコフ連鎖に対する量子ウォーク$W(P)$の構築方法を示した。
ある種のマルコフ連鎖に対する状態空間の二重化を回避できることが示される。
論文 参考訳（メタデータ） (2022-06-14T14:41:56Z) - Neural Inverse Kinematics [72.85330210991508]
逆キネマティック(英語版)(IK)法は、キネマティックチェインにおける選択された要素の所望の位置から関節のパラメータを復元する。
本稿では,問題階層構造を用いて,所望の位置に条件付き有効関節角度を逐次サンプリングするニューラルIK法を提案する。
論文 参考訳（メタデータ） (2022-05-22T14:44:07Z) - An Information-Theoretic Approach for Automatically Determining the
Number of States when Aggregating Markov Chains [12.716429755564821]
マルコフ連鎖を集約する付加的な情報に基づくアプローチが,状態群数の決定を容易にすることを示す。
最適状態群カウントは、縮退鎖の複雑さが、原鎖と縮退鎖のダイナミックスの間の相互依存と均衡している場合と一致する。
論文 参考訳（メタデータ） (2021-07-05T05:36:04Z) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳（メタデータ） (2021-06-29T12:49:54Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。