Optimal quantum algorithm for Gibbs state preparation

Abstract

It is of great interest to understand the thermalization of open quantum many-body systems, and how quantum computers are able to efficiently simulate that process. A recently introduced disispative evolution, inspired by existing models of open system thermalization, has been shown to be efficiently implementable on a quantum computer. Here, we prove that, at high enough temperatures, this evolution reaches the Gibbs state in time scaling logarithmically with system size. The result holds for Hamiltonians that satisfy the Lieb-Robinson bound, such as local Hamiltonians on a lattice, and includes long-range systems. To the best of our knowledge, these are the first results rigorously establishing the rapid mixing property of high-temperature quantum Gibbs samplers, which is known to give the fastest possible speed for thermalization in the many-body setting. We then employ our result to the problem of estimating partition functions at high temperature, showing an improved performance over previous classical and quantum algorithms.

5+11 pages. Comments welcome

References in corpus (29)

• Open Quantum Systems. An Introduction
• Quantum speedup of Monte Carlo methods
• Quantum Metropolis Sampling
• Universal Lindblad equation for open quantum systems
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Quantum algorithm for simulating real time evolution of lattice Hamiltonians
• Speed-up via Quantum Sampling
• Strictly linear light cones in long-range interacting systems of arbitrary dimensions
• Completely positive master equation for arbitrary driving and small level spacing
• Locality and digital quantum simulation of power-law interactions
• Nonzero temperature Entanglement Negativity of quantum spin models: Area law, Linked Cluster Expansions and Sudden Death
• Rapid adiabatic preparation of injective PEPS and Gibbs states
• Preparing thermal states of quantum systems by dimension reduction
• Speed limits and locality in many-body quantum dynamics
• Thermal State Preparation via Rounding Promises
• Relative Entropy Convergence for Depolarizing Channels
• Rapid thermalization of spin chain commuting Hamiltonians
• Approximation algorithms for the normalizing constant of Gibbs distributions
• Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
• Entropy decay for Davies semigroups of a one dimensional quantum lattice
• Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions
• Efficient Algorithms for Approximating Quantum Partition Functions
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
• Completely Positive Markovian Quantum Dynamics in the Weak-Coupling Limit
• Rapid thermalization of dissipative many-body dynamics of commuting Hamiltonians
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
• Clustering of conditional mutual information and quantum Markov structure at arbitrary temperatures
• A little bit of self-correction

Cited by in corpus (4)

• Simple and efficient end-to-end quantum thermal and ground state preparation
• Stability of thermal equilibrium in long-range quantum systems
• Post-Moore Technologies for Plasma Simulation: A Community Roadmap
• Efficient and simple Gibbs state preparation of the 2D toric code via duality to classical Ising chains