# A Faster Approximation Algorithm for the Gibbs Partition Function

arXiv: https://arxiv.org/abs/1608.04223 · HTML: https://mlsanity.com/paper/1608.04223/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Aug 2016.

## Built on by (most cited first, 4 of 4)

- [A Sublinear-Time Quantum Algorithm for Approximating Partition Functions](https://mlsanity.com/paper/2207.08643/) (2022)
- [Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds](https://mlsanity.com/paper/2111.07372/) (2021)
- [Asymptotically Optimal Change Detection for Unnormalized Pre- and Post-Change Distributions](https://mlsanity.com/paper/2410.14615/) (2024)
- [Partition Function Estimation under Bounded f-Divergence](https://mlsanity.com/paper/2602.23535/) (2026)

## Abstract (arXiv)

We consider the problem of estimating the partition function Z(β)=sumx exp(-β(H(x)) of a Gibbs distribution with a Hamilton H(·), or more precisely the logarithm of the ratio q=ln Z(0)/Z(β). 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,β]. The current best known approach due to Huber [9] uses O(qln n·[ln q + ln ln n+varepsilon-2]) oracle calls on average where varepsilon is the desired accuracy of approximation and H(·) is assumed to lie in 0cup[1,n]. We improve the complexity to O(qln n·varepsilon-2) oracle calls. We also show that the same complexity can be achieved if exact oracles are replaced with approximate sampling oracles that are within O(fracvarepsilon2qln n) variation distance from exact oracles. Finally, we prove a lower bound of Omega(q· varepsilon-2) oracle calls under a natural model of computation.