Abstract
We present the quantum algorithmic framework developed over the last 20 years for accelerating the computation of classical partition functions. We describe recent improvements that break down the linear-time barrier (with respect to the logarithm of the size of the state space) and suggest some directions for future improvements.