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

Zherui Chen, Giacomo Nannicini

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…