Quantum Metropolis sampling

By Kristan Temme, Tobias J. Osborne, K. Vollbrecht, David Poulin, Frank Verstraete. Nature, 2009

358 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/02b866bec133558fe6bac59cd2539677dcc0211b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Quantum speedup of Monte Carlo methods (2015, background): “Several recent works have developed quantum algorithms for the quantum generalisation of sampling from a Gibbs distribution: producing a Gibbs state ρ ∝ e−βH for some quantum Hamiltonian H [53, 47, 52, 60].”
Quantum Simulation (2013, methodology): “General methods for simulating the markovian dynamics of open quantum systems have been investigated in (Bacon et al., 2001; Terhal and DiVincenzo, 2000; Wang et al., 2011).”
Quantum machine learning (2016, positive): “nt the QAO algorithm. There are several ways that quantum computers can give advantages here. First, quantum methods can make the system thermalize quadratically faster than its classical counterpart [59, 60, 20, 61]. This can make accurate training of fully connected Boltzmann machines practical. S”
Simulating chemistry using quantum computers. (2010, positive): “This issue was addressed by building up the Markov chain by applying random local unitary operations (123).”
Quantum optimization using variational algorithms on near-term quantum devices (2017, methodology): “e challenge of eciently mapping the fermionic problem to the available qubit hardware is overcome. In fact, on a quantum device the natural way is to solve the chemical system in second quantization [3,4,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25, 26,27,28,29,30,31,32,33] formulated in terms ”