  In this paper, we present a quasi-polynomial time classical algorithm that
estimates the partition function of quantum many-body systems at temperatures
above the thermal phase transition point. It is known that in the worst case,
the same problem is NP-hard below this point. Together with our work, this
shows that the transition in the phase of a quantum system is also accompanied
by a transition in the hardness of approximation. We also show that in a system
of n particles above the phase transition point, the correlation between two
observables whose distance is at least log(n) decays exponentially. We can
improve the factor of log(n) to a constant when the Hamiltonian has commuting
terms or is on a 1D chain. The key to our results is a characterization of the
phase transition and the critical behavior of the system in terms of the
complex zeros of the partition function. Our work extends a seminal work of
Dobrushin and Shlosman on the equivalence between the decay of correlations and
the analyticity of the free energy in classical spin models. On the algorithmic
side, our result extends the scope of a recent approach due to Barvinok for
solving classical counting problems to quantum many-body systems.
