Quantum-enhanced Markov chain Monte Carlo

A rare occurrence of an MCMC paper in Nature!!! David Layden and co-authors published this paper on 12 July, about using a quantum proposal in a Metropolis-Rosenbluth-Hastings simulation of an Ising model. More specifically, based on “quenched dynamics of a transverse-field quantum Ising model²⁰, which can be efficiently simulated on a quantum computer²¹“, which amounts to using a Hamiltonian proposal. I tried to dig through the supplementary material to understand the implementation and the requirement for a quantum computer, but failed… (The picture below is from the News & Views tribune on the paper. It does not help.) The above illustrates the ability of the algorithm to explore more efficiently likely low energy configurations of the Ising model when compared with standard solutions, although I could not fathom if the time cost of resorting to the quantum computer for the former was accounted for.

“In experiments, our quantum algorithm converged in fewer iterations than common classical MCMC alternatives, suggesting unusual robustness to noise”

While this paper is a significant foray into quantum MCMC, its target is the modest Ising model for n=10 nodes, with very special features that seem to contribute to the construction of the proposal. A model that can be exactly simulated, either directly for that size or by perfect sampling à la Propp & Wilson for larger n’s. And whose discretisation is not too far from the model considered by Metropolis, [mostly] the Rosenbluths, and the Tellers in the 1950’s. It thus remains to see how extensions can be built for more realistic targets.