We consider the problem of estimating the partition function $Z(\beta)=\sum_x \exp(-\beta(H(x))$
of a Gibbs distribution with a Hamilton $H(\cdot)$, or more precisely the logarithm of the ratio $q=\ln Z(0)/Z(\beta)$.
It has been recently shown how to approximate $q$ with high probability assuming
the existence of an oracle that produces samples from the Gibbs distribution for a given parameter value in $[0,\beta]$.
The current best known approach due to Huber [9] uses $O(q\ln n\cdot[\ln q + \ln \ln n+\varepsilon^{-2}])$
oracle calls on average where $\varepsilon$ is the desired accuracy of approximation and $H(\cdot)$ is assumed to lie in $\{0\}\cup[1,n]$.
We improve the complexity to $O(q\ln n\cdot\varepsilon^{-2})$ oracle calls.