title: Quantum Metropolis sampling.
abstract: The original motivation to build a quantum computer came from Feynman, who imagined a machine capable of simulating generic quantum mechanical systems--a task that is believed to be intractable for classical computers. Such a machine could have far-reaching applications in the simulation of many-body quantum physics in condensed-matter, chemical and high-energy systems. 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 has basically acquired a monopoly on the simulation of interacting particles. Here we demonstrate how to implement a quantum version of the Metropolis algorithm. This algorithm permits sampling directly from the eigenstates of the Hamiltonian, and thus evades the sign problem present in classical simulations. A small-scale implementation of this algorithm should be achievable with today's technology.
authors.affiliation: Vienna Center for Quantum Science & Technology, Fakultät für Physik, Universität Wien, 1090 Wien, Austria.
authors.forename: K
authors.initials: K
authors.lastname: Temme
authors.forename: T J
authors.initials: TJ
authors.lastname: Osborne
authors.forename: K G
authors.initials: KG
authors.lastname: Vollbrecht
authors.forename: D
authors.initials: D
authors.lastname: Poulin
authors.forename: F
authors.initials: F
authors.lastname: Verstraete