  We study the complexity of estimating the partition function
$\mathsf{Z}(\beta)=\sum_{x\in\chi} e^{-\beta H(x)}$ for a Gibbs distribution
characterized by the Hamiltonian $H(x)$. We provide a simple and natural lower
bound for quantum algorithms that solve this task by relying on reflections
through the coherent encoding of Gibbs states. Our primary contribution is a
$\varOmega(1/\epsilon)$ lower bound for the number of reflections needed to
estimate the partition function with a quantum algorithm. The proof is based on
a reduction from the problem of estimating the Hamming weight of an unknown
binary string.
