Quantum Metropolis sampling: an algorithm to simulate thermal systems with a quantum computer

David Poulin

Published Jan 1, 2016• 0 citations

Abstract

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 intractable for classical computers. Such a machine would have tremendous applications in all physical sciences, 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 more fundamental problem of how to simulate the equilibrium and static properties of quantum systems. This requires the preparation of ground and Gibb's 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. In this talk, I will demonstrate that the corresponding quantum problem can be solved by a quantum Metropolis algorithm. This validates the quantum computer as a universal simulator, and proves that the so-called sign ! problem occurring in quantum Monte Carlo methods can be resolved with a quantum computer.

DOI: 10.14288/1.0103161

Related papers

A quantum–quantum Metropolis algorithm

Man‐Hong Yung, Alán Aspuru‐Guzik

The classical Metropolis sampling method is a cornerstone of many statistical modeling applications that range from physics, chemistry, and biology to economics. This method is particularly suitable for sampling the thermal distributions of classical systems. The challenge of extending this method to the simulation of arbitrary quantum systems is that, in general, eigenstates of quantum Hamiltonians cannot be obtained efficiently with a classical computer. However, this challenge can be overcome by quantum computers. Here, we present a quantum algorithm which fully generalizes the classical Metropolis algorithm to the quantum domain. The meaning of quantum generalization is twofold: The proposed algorithm is not only applicable to both classical and quantum systems, but also offers a quantum speedup relative to the classical counterpart. Furthermore, unlike the classical method of quantum Monte Carlo, this quantum algorithm does not suffer from the negative-sign problem associated with fermionic systems. Applications of this algorithm include the study of low-temperature properties of quantum systems, such as the Hubbard model, and preparing the thermal states of sizable molecules to simulate, for example, chemical reactions at an arbitrary temperature.

arXiv:1011.1468Proceedings of the National Academy of SciencesJan 3, 2012149 citations

Towards practical quantum Gibbs sampling

Müller, Adrian

Sampling from thermal equilibrium distributions of quantum systems is a fundamental problem in multiple areas of science, such as condensed matter physics, quantum chemistry, and high-energy physics. Classical methods can degrade quickly, due to the fermionic sign problem or classical approximation errors, motivating the search for more efficient alternatives on quantum hardware. The presented work develops the Quantum Metropolis algorithm proposed by Temme et al. (2011) further to arbitrary energy precision while also reducing demands on quantum resources by requiring only a single, non-persistent auxiliary register. A general formalism for quantum Markov Chain Monte Carlo (qMCMC) maps is introduced and used to prove correctness via primitivity and quantum detailed balance. The simplified rejection mechanism results in additional conditions on the step operators, in particular requiring them to be permutations on the eigenbasis. Numerical simulations validate convergence behavior and robustness under ideal and approximate step operators. However, since constructing step operators directly based on the eigenbasis is not feasible in general, future work could explore variational learning of approximate step operators, structured Hamiltonians, or hybrid classical-quantum walk sampling.

Jul 10, 20260 citations

A Quantum Mechanical Analog of Hamiltonian Monte Carlo

Matthew Hagan

The simulation of quantum systems is the most promising candidate for computational advantagesof large scale, fault-tolerant quantum computers over classical computers. Two fundamental prob- lems that appear when simulating quantum systems on quantum computers are the preparation of good input states to the simulation and the problem of decomposing the time evolution operator ???? into primitive gates that are available on the quantum computer. This thesis presents two new algorithms for solving these problems. The first is a time evolution algorithm that approximates the time evolution operator by combining two previously developed techniques. We bound the error of this composite approach and determine analytic conditions on when this can lead to cost savings of the overall simulation. These savings are then verified through extensive numerics. This simulation algorithm can then be used as a subroutine to prepare thermal states, which are typical input states that have a high overlap with the ground state. Our algorithm is inspired by Hamiltonian Monte Carlo, which is a classical sampling algorithm that utilizes Hamiltonian dynamics to sample from arbitrary probability distributions. We bound the cost of our quantum thermal state preparation algorithm in terms of the total amount of time needed to simulate the Hamiltonian of the system in four scenarios: single qubit systems, truncated harmonic oscillators, non-degenerate systems where one knows the eigenvalues, and non-degenerate systems where no eigenvalue knowledge is present. We numerically demonstrate that this algorithm works as guaranteed and can significantly outperform analytic worst-case bounds.

Oct 1, 20250 citations

Polynomial-time classical sampling of high-temperature quantum Gibbs states

Chao Nan Yin, Andrew Lucas

The computational complexity of simulating quantum many-body systems generally scales exponentially with the number of particles. This enormous computational cost prohibits first principles simulations of many important problems throughout science, ranging from simulating quantum chemistry to discovering the thermodynamic phase diagram of quantum materials or high-density neutron stars. We present a classical algorithm that samples from a high-temperature quantum Gibbs state in a computational (product state) basis. The runtime grows polynomially with the number of particles, while error vanishes polynomially. This algorithm provides an alternative strategy to existing quantum Monte Carlo methods for overcoming the sign problem. Our result implies that measurement-based quantum computation on a Gibbs state can provide exponential speed up only at sufficiently low temperature, and further constrains what tasks can be exponentially faster on quantum computers.

arXiv:2305.18514May 29, 20231 citation

Efficient quantum thermal simulation

Chi-Fang Chen, Michael J. Kastoryano, Fernando G. S. L. Brandão +1 more

Abstract Quantum computers promise to tackle quantum simulation problems that are classically intractable 1 . Although a lot of quantum algorithms 2–4 have been developed for simulating quantum dynamics, a general-purpose method for simulating low-temperature quantum phenomena remains unknown. In classical settings, the analogous task of sampling from thermal distributions has been largely addressed by Markov Chain Monte Carlo (MCMC) methods 5,6 . Here we propose an efficient quantum algorithm for thermal simulation that—akin to MCMC methods—exhibits detailed balance, respects locality and serves as a toy model for thermalization in open quantum systems. The enduring impact of MCMC methods suggests that our new construction may play an equally important part in quantum computing and applications in the physical sciences and beyond.

NatureOct 15, 202522 citations

Quantum Algorithms with Applications to Simulating Physical Systems

Anirban Ch Narayan Chowdhury

The simulation of quantum physical systems is expected to be an important application for quantum computers. The work presented in this dissertation aims to improve the resource requirements of quantum computers for solving simulation problems, by providing both novel quantum algorithms and improved implementations of existing ones. I present three main results that cover diverse aspects of simulation including equilibrium physics, the preparation of useful quantum states, and simulations based on classical stochastic processes. The results rely on established quantum algorithms and other recent techniques which I review. My first original contribution is a new quantum algorithm to sample from the thermal Gibbs state of quantum Hamiltonians. The complexity of this algorithm has an exponentially improved dependence on precision compared to an earlier quantum algorithm, and also provides polynomial improvements in other parameters. My second contribution is an improved algorithm to implement reflections about the eigenstates of unitary operators and Hamiltonians, an operation that can be used to prepare ground states of many-body Hamiltonians by quantum amplitude amplification. The improved algorithm for implementing reflections significantly reduces the number of ancilla qubits required over earlier implementations. The improvement relies in part on a novel quantum algorithm for efficiently preparing states with Gaussian-like amplitudes, which may have broad applications. I also prove a lower bound for implementing reflections, which shows that our algorithm is almost optimal. My third and final contribution regards quantum algorithms for classical stochastic processes, which are of importance in statistical physics. I present a quantum algorithm that estimates the average running time of a stochastic process, and provides a quadratic speed-up over a comparable classical algorithm.

Jan 1, 20190 citations