  We present classical and quantum algorithms for approximating partition
functions of classical Hamiltonians at a given temperature. Our work has two
main contributions: first, we modify the classical algorithm of
\v{S}tefankovi\v{c}, Vempala and Vigoda (\emph{J.~ACM}, 56(3), 2009) to improve
its sample complexity; second, we quantize this new algorithm, improving upon
the previously fastest quantum algorithm for this problem, due to Harrow and
Wei (SODA 2020). The conventional approach to estimating partition functions
requires approximating the means of Gibbs distributions at a set of inverse
temperatures that form the so-called cooling schedule. The length of the
cooling schedule directly affects the complexity of the algorithm. Combining
our improved version of the algorithm of \v{S}tefankovi\v{c}, Vempala and
Vigoda with the paired-product estimator of Huber (\emph{Ann.\ Appl.\ Probab.},
25(2),~2015), our new quantum algorithm uses a shorter cooling schedule than
previously known. This length matches the optimal length conjectured by
\v{S}tefankovi\v{c}, Vempala and Vigoda. The quantum algorithm also achieves a
quadratic advantage in the number of required quantum samples compared to the
number of random samples drawn by the best classical algorithm, and its
computational complexity has quadratically better dependence on the spectral
gap of the Markov chains used to produce the quantum samples.
