Quantum Metropolis Sampling

Author(s): K. Temme, T. J. Osborne, K. G. H. Vollbrecht, D. Poulin, F. Verstraete

Journal: Nature

Volume: 471

Page(s): 87-90

Year: 2011

DOI Number: DOI:10.1038/nature09770

Link: Link to publication


The original motivation to build a quantum computer came from Feynman who envisaged a machine capable of simulating generic quantum mechanical systems, a task that is believed to be intractable for classical computers. Such a machine would have a wide range of applications in the simulation of many-body quantum physics, including condensed matter physics, chemistry, and high energy physics. Part of Feynman's challenge was met by Lloyd who showed how to approximately decompose the time-evolution operator of interacting quantum particles into a short sequence of elementary gates, suitable for operation on a quantum computer. However, this left open the problem of how to simulate the equilibrium and static properties of quantum systems. This requires the preparation of ground and Gibbs states on a quantum computer. For classical systems, this problem is solved by the ubiquitous Metropolis algorithm, a method that basically acquired a monopoly for the simulation of interacting particles. Here, we demonstrate how to implement a quantum version of the Metropolis algorithm on a quantum computer. This algorithm permits to sample directly from the eigenstates of the Hamiltonian and thus evades the sign problem present in classical simulations. A small scale implementation of this algorithm can already be achieved with today's technology.

Note: http://arxiv.org/abs/0911.3635

File: Link to PDF

Verstraete Group Verstraete Group