Quantum Metropolis-Hastings algorithm with the target distribution calculated by quantum Monte Carlo integration
Quantum Metropolis-Hastings algorithm with the target distribution calculated by quantum Monte Carlo integration
复制标题
DOI：
10.1103/physrevresearch.5.033059
复制
发表时间：
2023-03
影响因子：
4.2
通讯作者：
Koichi Miyamoto
中科院分区：
文献类型：
--
作者：
Koichi Miyamoto
马尔可夫链蒙特卡罗方法(MCMC)，特别是Metropolis-Hastings(MH)算法是一种广泛使用的技术，用于从状态空间上的目标概率分布$P进行抽样，并应用于各种问题，如贝叶斯方法中统计模型中的参数估计。已经提出了适用于MCMC的量子算法，与经典算法相比，获得了相对于谱间隙的二次加速比。在这篇文章中，我们考虑了MH算法的量子版本，当计算$P$是因为一个态$x\in\Omega$的对数似然$L是通过计算多项之和$\frac{1}{M}\sum_{i=0}^{M-1}\ell(i，x)$而得到的。我们提出用量子蒙特卡罗积分来计算$L$，并将其与现有的量子模拟退火法相结合，产生以幅度编码$P$的量子态。我们不仅考虑状态的产生，而且考虑为参数寻找可信区间，这是贝叶斯推理中的一项常见任务。在所提出的可信区间计算方法中，对量子电路进行可信区间计算的查询次数在$\Delta$上，所需的精度$\epsilon$和$\ell$的标准差$\sigma$为$tide{O}(\sigma/\epsilon^2\Delta^{3/2})$，而对于带有$L$的QSA，则$\tide{O}(M/\epsilon\Delta^{1/2})$是精确计算的。因此，如果$Sigma$在$M$上次线性缩放，则所提出的方法是有利的。作为一个这样的例子，我们考虑引力波实验中的参数估计，其中$\sigma=O(M^{1/2})$。
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})$.