A simple lower bound for the complexity of estimating partition functions on a quantum computer

We study the complexity of estimating the partition function Z(β)=∑x∈χ e-β 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 Ω(1/ε) lower bound for the number of reflections needed to estimate the partition function with a quantum algorithm. We also prove a Ω(1/ε²) query lower bound for classical algorithms. The proofs are based on a reduction from the problem of estimating the Hamming weight of an unknown binary string.