論文の概要: Quantum Metropolis-Hastings algorithm with the target distribution
calculated by quantum Monte Carlo integration
- arxiv url: http://arxiv.org/abs/2303.05640v1
- Date: Fri, 10 Mar 2023 01:05:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-13 16:36:29.782294
- Title: Quantum Metropolis-Hastings algorithm with the target distribution
calculated by quantum Monte Carlo integration
- Title(参考訳): 量子モンテカルロ積分によるターゲット分布を用いた量子メトロポリス・ヘイスティングスアルゴリズム
- Authors: Koichi Miyamoto
- Abstract要約: MCMCの量子アルゴリズムが提案され、古典的なスペクトルギャップに対して$Delta$の2次スピードアップが得られる。
我々は状態生成だけでなく、ベイズ推定における共通課題であるパラメータの信頼区間も見いだすと考えている。
提案した信頼区間計算法では、$Delta$で$ell$スケールを計算するための量子回路へのクエリ数、$epsilon$で必要な精度$epsilon$、および標準偏差$sigma$$$ $ell$ as $tildeO(sigma/epsilonを演算する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Markov chain Monte Carlo method (MCMC), especially the
Metropolis-Hastings (MH) algorithm, is a widely used technique for sampling
from a target probability distribution $P$ on a state space $\Omega$ and
applied to various problems such as estimation of parameters in statistical
models in the Bayesian approach. Quantum algorithms for MCMC have been
proposed, yielding the quadratic speedup with respect to the spectral gap
$\Delta$ compered to classical counterparts. In this paper, we consider the
quantum version of the MH algorithm in the case that calculating $P$ is costly
because the log-likelihood $L$ for a state $x\in\Omega$ is obtained via
computing the sum of many terms $\frac{1}{M}\sum_{i=0}^{M-1} \ell(i,x)$. We
propose calculating $L$ by quantum Monte Carlo integration and combine it with
the existing method called quantum simulated annealing (QSA) to generate the
quantum state that encodes $P$ in amplitudes. We consider not only state
generation but also finding a credible interval for a parameter, a common task
in Bayesian inference. In the proposed method for credible interval
calculation, the number of queries to the quantum circuit to compute $\ell$
scales on $\Delta$, the required accuracy $\epsilon$ and the standard deviation
$\sigma$ of $\ell$ as $\tilde{O}(\sigma/\epsilon^2\Delta^{3/2})$, in contrast
to $\tilde{O}(M/\epsilon\Delta^{1/2})$ for QSA with $L$ calculated exactly.
Therefore, the proposed method is advantageous if $\sigma$ scales on $M$
sublinearly. As one such example, we consider parameter estimation in a
gravitational wave experiment, where $\sigma=O(M^{1/2})$.
- Abstract(参考訳): マルコフ連鎖モンテカルロ法(MCMC)、特にメトロポリス・ハスティングス(MH)アルゴリズムは、目標確率分布から$P$を状態空間$\Omega$でサンプリングし、ベイズ的アプローチの統計モデルにおけるパラメータ推定などの様々な問題に適用するための広く用いられている手法である。
MCMCの量子アルゴリズムが提案され、古典的なスペクトルギャップの$\Delta$に対して2次スピードアップが得られる。
本稿では,MHアルゴリズムの量子バージョンについて,数式$1}{M}\sum_{i=0}^{M-1} \ell(i,x)$の和を演算することで,対数的な$L$の状態を$x\in\Omega$とするので,$P$の計算に費用がかかると考える。
我々は,量子モンテカルロ積分による$l$の計算を提案し,それを量子シミュレートアニーリング(qsa)と呼ばれる既存の手法と組み合わせて,$p$イン振幅を符号化する量子状態を生成する。
我々は状態生成だけでなく、ベイズ推定における共通課題であるパラメータの信頼区間も見いだすと考えている。
提案した信頼区間計算法では、$\delta$で$\ell$スケールを計算する量子回路へのクエリの数は、$l$のqsaに対して$\tilde{o}(\sigma/\epsilon^2\delta^{3/2})$とは対照的に、$l$のqsaに対して、必要な精度である$\epsilon$と標準偏差$\sigma$ as $\tilde{o}(\sigma/\epsilon^2\delta^{3/2})$である。
したがって、$\sigma$が$M$サブラインでスケールすると、提案手法は有利である。
そのような例として、パラメータ推定を重力波実験で考慮し、$\sigma=O(M^{1/2})$とする。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。
我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。
教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文 参考訳(メタデータ) (2023-08-16T06:46:37Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳(メタデータ) (2022-10-12T19:10:43Z) - Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random
steps [0.0]
Hamiltonian Monte Carlo (HMC) は密度$e-f(x)$の高次元分布からサンプリングするマルコフ連鎖アルゴリズムである。
HMCは,$widetildeO(sqrtkappa d1/4 log(1/varepsilon)$グラデーションクエリを用いて,全変動距離で$varepsilon$-closeの分布からサンプリングできることを示す。
論文 参考訳(メタデータ) (2022-09-26T15:29:29Z) - Learning Distributions over Quantum Measurement Outcomes [4.467248776406005]
量子状態に対するシャドウトモグラフィーは、量子システムの特性を予測するためのサンプル効率の良いアプローチを提供する。
我々は,この問題を高い確率で解決するオンラインシャドウトモグラフィー手法を開発した。
論文 参考訳(メタデータ) (2022-09-07T09:08:58Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳(メタデータ) (2021-12-15T21:44:05Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳(メタデータ) (2021-11-29T19:26:28Z) - 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 Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳(メタデータ) (2020-02-25T19:18:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。