Quantum-enhanced Markov chain Monte Carlo.

Quantum computers promise to solve certain computational problems much faster than classical computers. However, current quantum processors are limited by their modest size and appreciable error rates. Recent efforts to demonstrate quantum speedups have therefore focused on problems that are both classically hard and naturally suited to current quantum hardware, such as sampling from complicated-although not explicitly useful-probability distributions1-3. Here we introduce and experimentally demonstrate a quantum algorithm that is similarly well suited to current hardware, but which samples from complicated distributions arising in several applications. The algorithm performs Markov chain Monte Carlo (MCMC), a prominent iterative technique4, to sample from the Boltzmann distribution of classical Ising models. Unlike most near-term quantum algorithms, ours provably converges to the correct distribution, despite being hard to simulate classically. But like most MCMC algorithms, its convergence rate is difficult to establish theoretically, so we instead analysed it through both experiments and simulations. In experiments, our quantum algorithm converged in fewer iterations than common classical MCMC alternatives, suggesting unusual robustness to noise. In simulations, we observed a polynomial speedup between cubic and quartic over such alternatives. This empirical speedup, should it persist to larger scales, could ease computational bottlenecks posed by this sampling problem in machine learning5, statistical physics6 and optimization7. This algorithm therefore opens a new path for quantum computers to solve useful-not merely difficult-sampling problems.

Preparing ground States of quantum many-body systems on a quantum computer.

Preparing the ground state of a system of interacting classical particles is an NP-hard problem. Thus, there is in general no better algorithm to solve this problem than exhaustively going through all N configurations of the system to determine the one with lowest energy, requiring a running time proportional to N. A quantum computer, if it could be built, could solve this problem in time sqrt[N]. Here, we present a powerful extension of this result to the case of interacting quantum particles, demonstrating that a quantum computer can prepare the ground state of a quantum system as efficiently as it does for classical systems.

Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer.

We present a quantum algorithm to prepare the thermal Gibbs state of interacting quantum systems. This algorithm sets a universal upper bound D(alpha) on the thermalization time of a quantum system, where D is the system's Hilbert space dimension and alpha < or = 1/2 is proportional to the Helmholtz free energy density. We also derive an algorithm to evaluate the partition function of a quantum system in a time proportional to the system's thermalization time and inversely proportional to the targeted accuracy squared.