  The partition function and free energy of a quantum many-body system
determine its physical properties in thermal equilibrium. Here we study the
computational complexity of approximating these quantities for $n$-qubit local
Hamiltonians. First, we report a classical algorithm with $\mathrm{poly}(n)$
runtime which approximates the free energy of a given $2$-local Hamiltonian
provided that it satisfies a certain denseness condition. Our algorithm
combines the variational characterization of the free energy and convex
relaxation methods. It contributes to a body of work on efficient approximation
algorithms for dense instances of optimization problems which are hard in the
general case, and can be viewed as simultaneously extending existing algorithms
for (a) the ground energy of dense $2$-local Hamiltonians, and (b) the free
energy of dense classical Ising models. Secondly, we establish polynomial-time
equivalence between the problem of approximating the free energy of local
Hamiltonians and three other natural quantum approximate counting problems,
including the problem of approximating the number of witness states accepted by
a QMA verifier. These results suggest that simulation of quantum many-body
systems in thermal equilibrium may precisely capture the complexity of a broad
family of computational problems that has yet to be defined or characterized in
terms of known complexity classes. Finally, we summarize state-of-the-art
classical and quantum algorithms for approximating the free energy and show how
to improve their runtime and memory footprint.
