The Markov chain Monte Carlo (MCMC) method, especially the Metropolis-Hastings (MH) algorithm, is a widely used technique for sampling from a target probability distribution
P on a state space $\mathrm{\ensuremath{\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 $\mathrm{\ensuremath{\Delta}}$ compared 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\ensuremath{\in}\mathrm{\ensuremath{\Omega}}$ is obtained via computing the sum of many terms, $\frac{1}{M}{\ensuremath{\sum}}_{i=0}^{M\ensuremath{-}1}\ensuremath{\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 $\ensuremath{\ell}$ scales on $\mathrm{\ensuremath{\Delta}}$, the required accuracy $\ensuremath{\epsilon}$, and the standard deviation $\ensuremath{\sigma}$ of $\ensuremath{\ell}$ as $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}(\ensuremath{\sigma}/{\ensuremath{\epsilon}}^{2}{\mathrm{\ensuremath{\Delta}}}^{3/2})$, in contrast to $\stackrel{\ifmmode \tilde{}\else \~{}\fi{}}{O}(M/\ensuremath{\epsilon}{\mathrm{\ensuremath{\Delta}}}^{1/2})$ for QSA with
L calculated exactly. Therefore, the proposed method is advantageous if $\ensuremath{\sigma}$ scales on
M sublinearly. As one such example, we consider parameter estimation in a gravitational wave experiment, where $\ensuremath{\sigma}=O({M}^{1/2})$.
Performing exact inference on Bayesian networks is known to be $#P$-hard. Typically approximate inference techniques are used instead to sample from the distribution on query variables given the values
e of evidence variables. Classically, a single unbiased sample is obtained from a Bayesian network on
n variables with at most
m parents per node in time $O(nmP{(e)}^{\ensuremath{-}1})$, depending critically on
P(e), the probability that the evidence might occur in the first place. By implementing a quantum version of rejection sampling, we obtain a square-root speedup, taking $O(n{2}^{m}P{(e)}^{\ensuremath{-}\frac{1}{2}})$ time per sample. We exploit the Bayesian network's graph structure to efficiently construct a quantum state, a q-sample, representing the intended classical distribution, and also to efficiently apply amplitude amplification, the source of our speedup. Thus, our speedup is notable as it is unrelativized---we count primitive operations and require no blackbox oracle queries.
We give some quantum circuits for calculating the probability
P(G∣D) of a graph
G given data
D.
G together with a transition probability matrix for each node of the graph, constitutes a Classical Bayesian Network, or CB net for short. Bayesian methods for calculating
P(G∣D) have been given before (the so called structural modular and ordered modular models), but these earlier methods were designed to work on a classical computer. The goal of this paper is to "quantum computerize" those earlier methods.
Systems in thermal equilibrium at non-zero temperature are described by their Gibbs state. For classical many-body systems, the Metropolis-Hastings algorithm gives a Markov process with a local update rule that samples from the Gibbs distribution. For quantum systems, sampling from the Gibbs state is significantly more challenging. Many algorithms have been proposed, but these are more complex than the simple local update rule of classical Metropolis sampling, requiring non-trivial quantum algorithms such as phase estimation as a subroutine. Here, we show that a dissipative quantum algorithm with a simple, local update rule is able to sample from the quantum Gibbs state. In contrast to the classical case, the quantum Gibbs state is not generated by converging to the fixed point of a Markov process, but by the states generated at the stopping time of a conditionally stopped process. This gives a new answer to the long-sought-after quantum analogue of Metropolis sampling. Compared to previous quantum Gibbs sampling algorithms, the local update rule of the process has a simple implementation, which may make it more amenable to near-term implementation on suitable quantum hardware. This dissipative Gibbs sampler works for arbitrary quantum Hamiltonians, without any assumptions on or knowledge of its properties, and comes with certifiable precision and run-time bounds. We also show that the algorithm benefits from some measure of built-in resilience to faults and errors (``fault resilience''). Finally, we also demonstrate how the stopping statistics of an ensemble of runs of the dissipative Gibbs sampler can be used to estimate the partition function.
The self-learning Metropolis-Hastings algorithm is a powerful Monte Carlo method that, with the help of machine learning, adaptively generates an easy-to-sample probability distribution for approximating a given hard-to-sample distribution. This paper provides a new self-learning Monte Carlo method that utilizes a quantum computer to output a proposal distribution. In particular, we show a novel subclass of this general scheme based on the quantum Fourier transform circuit; this sampler is classically simulable while having a certain advantage over conventional methods. The performance of this "quantum inspired" algorithm is demonstrated by some numerical simulations.
The classical Metropolis sampling method is a cornerstone of many statistical modeling applications that range from physics, chemistry, and biology to economics. This method is particularly suitable for sampling the thermal distributions of classical systems. The challenge of extending this method to the simulation of arbitrary quantum systems is that, in general, eigenstates of quantum Hamiltonians cannot be obtained efficiently with a classical computer. However, this challenge can be overcome by quantum computers. Here, we present a quantum algorithm which fully generalizes the classical Metropolis algorithm to the quantum domain. The meaning of quantum generalization is twofold: The proposed algorithm is not only applicable to both classical and quantum systems, but also offers a quantum speedup relative to the classical counterpart. Furthermore, unlike the classical method of quantum Monte Carlo, this quantum algorithm does not suffer from the negative-sign problem associated with fermionic systems. Applications of this algorithm include the study of low-temperature properties of quantum systems, such as the Hubbard model, and preparing the thermal states of sizable molecules to simulate, for example, chemical reactions at an arbitrary temperature.