Tutte Colloquium - David Gosset

Title: On the complexity of quantum partition functions

Abstract: Quantum complexity theory has been intertwined with the study of quantum many-body systems ever since Kitaev's insight that computing their ground energies is an intractable quantum constraint satisfaction problem that is complete for a quantum generalization of NP. In this talk I will discuss the computational complexity of less well studied problems having to do with computing properties of quantum many-body systems in thermal equilibrium. I will describe how the problem of approximating the partition function of a quantum spin system at a given temperature captures a broad class of quantum approximate counting problems whose worst-case complexity is a mystery. We will see that certain mathematical quantities related to the representation theory of the symmetric group can be approximated in this class.  I will also discuss efficient classical algorithms for approximating quantum partition functions in certain special cases. This talk is based on joint works with Sergey Bravyi, Anirban Chowdhury, Vojtech Havlicek, Pawel Wocjan and Guanyu Zhu.