Simpler (classical) and Faster (quantum) Algorithms for Gibbs Partition Functions

We consider the problem of approximating the partition function of a classical Hamiltonian using simulated annealing. This requires the computation of a cooling schedule, and the ability to estimate the mean of the Gibbs distributions at the corresponding inverse temperatures. We propose classical and quantum algorithms for these two tasks, achieving two goals: (i) we simplify the seminal work of Štefankovič, Vempala and Vigoda (J.ACM, 56(3), 2009), improving their running time and almost matching that of the current classical state of the art; (ii) we quantize our new simple algorithm, improving upon the best known algorithm for computing partition functions of many problems, due to Harrow and Wei (SODA 2020). A key ingredient of our method is the paired-product estimator of Huber (Ann. Appl. @Probab., 25(2),~2015).