  We present a novel quantum algorithm for estimating Gibbs partition functions
in sublinear time with respect to the logarithm of the size of the state space.
This is the first speed-up of this type to be obtained over the seminal
nearly-linear time algorithm of \v{S}tefankovi\v{c}, Vempala and Vigoda [JACM,
2009]. Our result also preserves the quadratic speed-up in precision and
spectral gap achieved in previous work by exploiting the properties of quantum
Markov chains. 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.
  Our approach relies on developing new variants of the quantum phase and
amplitude estimation algorithms that return nearly unbiased estimates with low
variance and without destroying their initial quantum state. We extend these
subroutines into a nearly unbiased quantum mean estimator that reduces the
variance quadratically faster than the classical empirical mean. No such
estimator was known to exist prior to our work. These properties, which are of
general interest, lead to better convergence guarantees within the paradigm of
simulated annealing for computing partition functions.
