The complexity of quantum matter

Quantum systems of many particles appear in numerous branches of physics, from condensed matter to statistical or high energy physics. Their study, however, is often very complicated due to the high dimensions of the Hilbert spaces involved. 

The field of quantum information brings a new perspective to the study of those systems. Through it, we can rigorously analyze whether specific physical problems are fundamentally complex, and will require a quantum computer, or whether they can be solved efficiently with (classical) numerical means. 

We overview the main ideas driving this approach. We also show how within it many interesting properties can be computed in polynomial time, with provable efficiency guarantees. In particular, we focus on the classical simulation of Gibbs or thermal states, and of arbitrary dynamics for short times. In doing so, we highlight how fundamental physical features, such as locality, constrain the complexity of quantum systems.