Quantum algorithms for thermal equilibrium from fluctuation theorems

Fluctuation theorems provide a correspondence between properties of quantum systems in thermal equilibrium and a work distribution arising in a non-equilibrium process that connects two quantum systems with Hamiltonians H₀ and H₁=H₀+V. Building upon these theorems, we present quantum algorithms to prepare the thermal state of H₁ at inverse temperature β≥0 and to estimate the free energy difference between the two systems. The complexity of these algorithms, given by the number of times certain unitaries are used, is at most exponential in β|V|, where |V| is the spectral norm of V. This is a significant improvement of prior quantum algorithms that have complexity exponential in β|H₀| or β|H₁|. The dependence of the complexity in terms of a precision parameter ε>0 varies according to the structure of the quantum systems. For the problem of thermal state preparation, this complexity can be exponential in 1/ε in general, but we show it to be sublinear in 1/ε if H₀ and H₁ commute, or polynomial in 1/ε if H₀ and H₁ are local spin systems. The possibility of applying a unitary that drives the system H₀ out of equilibrium allows one to improve the complexity of the quantum algorithms even further.