論文の概要: Quantum Speedups for Multiproposal MCMC
- arxiv url: http://arxiv.org/abs/2312.01402v3
- Date: Tue, 18 Feb 2025 14:09:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-19 14:01:53.399783
- Title: Quantum Speedups for Multiproposal MCMC
- Title（参考訳）: 多目的MCMCの量子スピードアップ
- Authors: Chin-Yi Lin, Kuo-Chin Chen, Philippe Lemey, Marc A. Suchard, Andrew J. Holbrook, Min-Hsiu Hsieh,
- Abstract要約: より高速な量子多目的MCMC戦略であるQPMCMC2を提案する。
QPMCMC2は、多数の提案を計算する際に、ターゲット評価に$mathcalO(P)$と$mathcalO(log P)$ qubitsしか必要としない。
細菌進化ネットワーク上に構築された新しいIsing型モデルにQPMCMC2を適用することで,この柔軟性を示す。
- 参考スコア（独自算出の注目度）: 8.580097282861725
- License:
- Abstract: Multiproposal Markov chain Monte Carlo (MCMC) algorithms choose from multiple proposals to generate their next chain step in order to sample from challenging target distributions more efficiently. However, on classical machines, these algorithms require $\mathcal{O}(P)$ target evaluations for each Markov chain step when choosing from $P$ proposals. Recent work demonstrates the possibility of quadratic quantum speedups for one such multiproposal MCMC algorithm. After generating $P$ proposals, this quantum parallel MCMC (QPMCMC) algorithm requires only $\mathcal{O}(\sqrt{P})$ target evaluations at each step, outperforming its classical counterpart. However, generating $P$ proposals using classical computers still requires $\mathcal{O}(P)$ time complexity, resulting in the overall complexity of QPMCMC remaining $\mathcal{O}(P)$. Here, we present a new, faster quantum multiproposal MCMC strategy, QPMCMC2. With a specially designed Tjelmeland distribution that generates proposals close to the input state, QPMCMC2 requires only $\mathcal{O}(1)$ target evaluations and $\mathcal{O}(\log P)$ qubits when computing over a large number of proposals $P$. Unlike its slower predecessor, the QPMCMC2 Markov kernel (1) maintains detailed balance exactly and (2) is fully explicit for a large class of graphical models. We demonstrate this flexibility by applying QPMCMC2 to novel Ising-type models built on bacterial evolutionary networks and obtain significant speedups for Bayesian ancestral trait reconstruction for 248 observed salmonella bacteria.
- Abstract（参考訳）: マルチプロポサルマルコフ連鎖モンテカルロ (MCMC) アルゴリズムは、挑戦対象の分布からより効率的にサンプリングするために、次の連鎖ステップを生成するために複数の提案から選択する。
しかし、古典機械では、これらのアルゴリズムは、$P$提案の中から選択する場合、各マルコフ連鎖ステップに対して$\mathcal{O}(P)$ターゲット評価を必要とする。
最近の研究は、そのような多目的MCMCアルゴリズムの2次量子スピードアップの可能性を示している。
P$の提案を生成した後、この量子並列MCMC (QPMCMC) アルゴリズムは各ステップでの目標評価を$\mathcal{O}(\sqrt{P}) でしか必要とせず、古典的手法よりも優れている。
しかし、古典的コンピュータを使った$P$の提案を生成するには、依然として$\mathcal{O}(P)$時間複雑さが必要であり、QPMCMCの全体的な複雑さは$\mathcal{O}(P)$のままである。
本稿では,より高速な量子多元系MCMC戦略,QPMCMC2を提案する。
入力状態に近い提案を生成する特別に設計されたTjelmelandディストリビューションでは、QPMCMC2は、多数の提案を計算する際に、ターゲット評価が$\mathcal{O}(1)$$と$\mathcal{O}(\log P)$ qubitsしか必要としない。
前者とは異なり、QPMCMC2 Markov kernel (1) は細かなバランスを維持しており、(2) は大規模なグラフィカルモデルに対して完全に明示的である。
細菌進化ネットワーク上に構築された新規Ising型モデルにQPMCMC2を適用し,248種のサルモネラ菌に対するベイズ祖先形質再構成の大幅な高速化を図った。
関連論文リスト
- Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation [0.0]
量子モンテカルロ積分(Quantum Monte Carlo integration, QMCI)は、確率変数の予測を推定する量子アルゴリズムである。
本稿では直交級数密度推定に基づいて$U_X(t)$を分割する手法を提案する。
本手法は,回路深度と総クエリ複雑性のスケーリングを,それぞれ$O(sqrtN)$と$O(N3/2)$として達成する。
論文 参考訳（メタデータ） (2024-06-04T01:50:21Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - SMC Is All You Need: Parallel Strong Scaling [0.695967916921061]
並列高強度スケーリングを実現するための完全並列シーケンシャルモンテカルロ法(pSMC)を開発した。
pSMC は無限小精度 MSE$=O(varepsilon2)$ に収束し、固定された有限時間複素度コスト=O(1)$ であり、効率リークがない。
論文 参考訳（メタデータ） (2024-02-09T04:13:38Z) - Generalized Quantum Signal Processing [0.6768558752130311]
本稿では、一般的なSU(2)回転を信号処理演算子として用いた一般化量子信号処理手法を提案する。
我々のアプローチは、達成可能な変換の族に対するすべての実用的な制限を持ち上げ、残りの唯一の条件は、$|P|leq 1$である。
P$しか知られていない場合、我々は1分以内で識別できる効率的なGPU最適化を提供し、それに対応する$Q$は107$である。
論文 参考訳（メタデータ） (2023-08-03T01:51:52Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - A quantum parallel Markov chain Monte Carlo [0.0]
我々は、Gumbel-max トリックを用いて、一般化されたアセプション-リジェクトステップを離散最適化問題に変換する。
我々はGroverの量子探索アルゴリズムのよく知られた拡張の中にターゲット密度評価を埋め込む。
論文 参考訳（メタデータ） (2021-12-01T01:25:06Z) - On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。
効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。
我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
論文 参考訳（メタデータ） (2020-06-15T21:36:00Z) - 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) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。