Complexity of complex quantum systems and quantum algorithms

There is a remarkable connection between quantum many-body theory - the theory that captures the behavior exhibited by a large number of interacting particles - and complexity theory in computer science. Indeed, there are striking parallels between key objects of study: The Hamiltonians of quantum many-body physics resemble propositional formulae as they are the object of study in complexity theory. It has become clear that the connection runs deeper, and that a close formal link between equilibrium properties and satisfying assignments can be established. By a reading of the Church Turing thesis, one can link questions of computationally hard problems to physical properties, such as glassy systems taking a long time to cool to their ground state.

We are concerned with several ramifications of the link between complexity studies and the physics of complex quantum systems, beyond what is usually referred to as Hamiltonian complexity. We have been concerned with questions of computational complexity of Hamiltonian systems, open many-body systems, Markovianity, Gibbs state preparation and many-body localization. Some problems turn out not only to be computationally difficult, but even undecidable.

Selected group publications