In quantum systems, physical quantities of interest can be expressed as expectation values of a probability distribution, which allows their estimation by Markov Chain Monte Carlo (MCMC) methods. This approach, an instance of Quantum Monte Carlo (QMC), plays a central role in obtaining predictions of system properties relevant to condensed matter and high energy physics. The use of Hamiltonian dynamics to design a Markov kernel, known as Hybrid or Hamiltonian Monte Carlo (HMC), is widespread in quantum applications. In this context, it is standard to use an HMC kernel that is ``adjusted'' with the Metropolis-Hastings (MH) criterion, so that estimates of expectations converge to their true value in the limit of infinite sample size. However, recent work in computational statistics suggests that an \emph{unadjusted} HMC kernel can be significantly more efficient, while safely maintaining an asymptotic bias which is small relative to the error arising from the variance of the finite sample size. We adapt this approach to the QMC setting, focusing on a challenging and high-dimensional \emph{spin-fermion} model of a quantum phase transition. We find that unadjusted methods outperform adjusted HMC in terms of effective sample size per gradient call, while retaining accurate results.
In quantum systems, physical quantities of interest can be expressed as expectation values of a probability distribution, which allows their estimation by Markov Chain Monte Carlo (MCMC) methods. This approach, an instance of Quantum Monte Carlo (QMC), plays a central role in obtaining predictions of system properties relevant to condensed matter and high energy physics. The use of Hamiltonian dynamics to design a Markov kernel, known as Hybrid or Hamiltonian Monte Carlo (HMC), is widespread in quantum applications. In this context, it is standard to use an HMC kernel that is ``adjusted'' with the Metropolis-Hastings (MH) criterion, so that estimates of expectations converge to their true value in the limit of infinite sample size. However, recent work in computational statistics suggests that an \emph{unadjusted} HMC kernel can be significantly more efficient, while safely maintaining an asymptotic bias which is small relative to the error arising from the variance of the finite sample size. We adapt this approach to the QMC setting, focusing on a challenging and high-dimensional \emph{spin-fermion} model of a quantum phase transition. We find that unadjusted methods outperform adjusted HMC in terms of effective sample size per gradient call, while retaining accurate results.
One of the open challenges in quantum computing is to find meaningful and practical methods to leverage quantum computation to accelerate classical machine-learning workflows. A ubiquitous problem in machine-learning workflows is sampling from probability distributions that we only have access to via their log probability. To this end, we extend the well-known Hamiltonian Monte Carlo (HMC) method for Markov chain Monte Carlo (MCMC) sampling to leverage quantum computation in a hybrid manner as a proposal function. Our new algorithm, Quantum Dynamical Hamiltonian Monte Carlo (QD-HMC), replaces the classical symplectic integration proposal step with simulations of quantum-coherent continuous-space dynamics on digital or analog quantum computers. We show that QD-HMC maintains key characteristics of HMC, such as maintaining the detailed balanced condition with momentum inversion, while also having the potential for polynomial speedups over its classical counterpart in certain scenarios. As sampling is a core subroutine in many forms of probabilistic inference, and MCMC in continuously parametrized spaces covers a large class of potential applications, this work widens the areas of applicability of quantum devices. Published by the American Physical Society 2024
Hamiltonian Monte Carlo (HMC) is a Markov chain algorithm for sampling from a high-dimensional distribution with density e−f(x), given access to the gradient of f. A particular case of interest is that of a d-dimensional Gaussian distribution with covariance matrix Σ, in which case f(x)=x⊤Σ−1x. We show that HMC can sample from a distribution that is ε-close in total variation distance using O(κd1/4log(1/ε)) gradient queries, where κ is the condition number of Σ. Our algorithm uses long and random integration times for the Hamiltonian dynamics. This contrasts with (and was motivated by) recent results that give an Ω(κd1/2) query lower bound for HMC with fixed integration times, even for the Gaussian case.
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})$.
High-quality random samples of quantum states are needed for a variety of tasks in quantum information and quantum computation. Searching the high-dimensional quantum state space for a global maximum of an objective function with many local maxima or evaluating an integral over a region in the quantum state space are but two exemplary applications of many. These tasks can only be performed reliably and efficiently with Monte Carlo methods, which involve good samplings of the parameter space in accordance with the relevant target distribution. We show how the Markov-chain Monte Carlo method known as Hamiltonian Monte Carlo, or hybrid Monte Carlo, can be adapted to this context. It is applicable when an efficient parameterization of the state space is available. The resulting random walk is entirely inside the physical parameter space, and the Hamiltonian dynamics enable us to take big steps, thereby avoiding strong correlations between successive sample points while enjoying a high acceptance rate. We use examples of single and double qubit measurements for illustration.
Monte Carlo methods use random sampling to estimate numerical quantities which are hard to compute deterministically. One important example is the use in statistical physics of rapidly mixing Markov chains to approximately compute partition functions. In this work, we describe a quantum algorithm which can accelerate Monte Carlo methods in a very general setting. The algorithm estimates the expected output value of an arbitrary randomized or quantum subroutine with bounded variance, achieving a near-quadratic speedup over the best possible classical algorithm. Combining the algorithm with the use of quantum walks gives a quantum speedup of the fastest known classical algorithms with rigorous performance bounds for computing partition functions, which use multiple-stage Markov chain Monte Carlo techniques. The quantum algorithm can also be used to estimate the total variation distance between probability distributions efficiently.
Quantum Monte Carlo (QMC) is one of the most promising methods for solving quantum many-body problems. QMC combines known analytical properties of wave functions, results from other methods, and stochastic techniques, into a powerful tool for investigation of the electronic structure of real materials. Furthermore, the method has a favorable scaling ( O[N3] in the number of electrons), perfect scalability on parallel architectures, and can be applied to a wide range of systems. Our work has focused both on expanding the capabilities of QMC for calculation of quantities beyond energies, such as interatomic forces, and on application of the method to challenging problems in nanostructure materials research. For the calculation of interatomic forces we have implemented a finite difference correlated sampling method. The correlated sampling enables us to avoid the problem of statistical noise in evaluating the energy differences and allows us to obtain forces with an average 1% error. We have analyzed the effect of the method's main approximations on the estimate of the forces, both by theoretical arguments and by performing a variety of tests on small systems. Furthermore, we have used this newly developed method for estimating equilibrium geometries in a problem where other methods have failed. QMC enabled us to treat the electron correlation effects with high accuracy and to provide accurate predictions in a number of interesting applications. In particular, for carbon rings of C4N+2 stoichiometry we have resolved a long-standing problem regarding the competition between the aromaticity and second order Jahn-Teller effects. We have found that the dominant mechanism at small and intermediate sizes, which stabilizes the bond angle and bond length alternated geometries, is the secondorder Jahn-Teller effect while the aromatic isomer is always found to be a transition state. These high accuracy calculations which have involved multi-reference wave functions, extensive variational optimizations, and the use of massively parallel platforms demonstrate clearly the unique capabilities of the QMC approach.