Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems

Various statistical properties of quantum many-body systems in thermal equilibrium such as the free energy, entropy, and average energy can be obtained from the partition function. The problem of estimating the partition function has been the subject of numerous studies in statistical physics, computer science, and machine learning. The aim of this work is to present a new classical algorithm for estimating the partition function of quantum systems. We achieve this by studying the connection between the hardness of approximating the partition function and the thermal phase transition. In particular, we show the following:

(1) We demonstrate a quasi-polynomial time classical algorithm that estimates the partition function of quantum systems above the phase transition point. The running time of this algorithm relies heavily on the locus of the complex zeros of the partition function. Intriguingly, these complex zeros are known to mark where the phase transition occurs. By a result of [Sly10], 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.

(2) We show that in a system of n particles at temperatures above the phase transition point, where the complex zeros are far from the real axis, the correlations between two observables whose distance is Ω(log n) decay exponentially. We can improve the factor of log n to a constant when the Hamiltonian has commuting terms or is on a 1D chain. Previously, the decay of correlations was only proved for translationally-invariant 1D systems [Ara69] or at very high temperatures [KGK + 14].

(3) We find a deterministic quasi-polynomial time approximation algorithm for the XXZ model in the ferromagnetic regime at any temperature over arbitrary graphs. Previously, a randomized algorithm was known only for the ferromagnetic XY model [BG17].

This work is the first rigorous study of the connection between the complex zeros of the partition function and the decay of correlations in quantum many-body systems and extends a seminal work of Dobrushin and Shlosman on classical spin models [DS87]. On the algorithmic side, our result extends the scope of a recent approach due to Barvinok for solving classical counting problems [Bar16a] to quantum many-body problems.