A sublinear-time quantum algorithm for approximating partition functions
Gibbs partition functions are ubiquitous in statistical physics and in combinatorial counting problems. They capture fundamental statistics, such as the free energy of a thermodynamic system or the number of independent sets of a graph. The problem of efficiently estimating partition functions is the object of intense research, both from a classical and a quantum algorithmic perspective. We present the first quantum algorithm whose running time is sublinear with respect to the logarithm of the size of the state space. Our result combines techniques from simulated annealing, Szegedy's quantum walks and quantum mean estimators. As an application, we obtain new polynomial improvements over the best-known algorithms for computing the partition function of the Ising model, counting the number of k-colorings, matchings or independent sets of a graph, and estimating the volume of a convex body.