Counting without Sampling: Approximation Algorithms for Quantum Many-Body Systems at Finite Temperatures

Abstract

Basic statistical properties of quantum many-body systems in thermal equilibrium including the free energy, entropy, and average energy can be obtained from the partition function. This talk will focus on the problem of estimating the partition function which has been the subject of various numerical and theoretical studies both in statistical physics and computer science. It is well known that this problem is computationally hard in the worst case. In this talk, I will present a quasi-polynomial time algorithm that estimates the partition function of quantum many-body systems above the phase transition point. The algorithm extrapolates the solution at high temperatures where the problem is easy to low temperatures where finding the solution is harder. The running time of this algorithm relies on the locus of the complex zeros of the partition function. I will talk about cases where we can locate these complex zeros. I will also discuss the relation between other signatures of the phase transition such as the exponential decay of correlations and the locus of these zeros. This is based on joint work with Aram Harrow and Saeed Mehraban https://arxiv.org/abs/1910.09071.