Sampling-complexity phase diagrams
Abstract: In this talk, I argue that the question of whether a physical system can be simulated on a classical computer is important not just from a practical perspective but also a fundamental one. We consider the complexity of approximate sampling from states arising due to time evolution under a Hamiltonian or from equilibrium states of quantum many-body Hamiltonians. I will comment on extensions of these results to other physical systems. I will further sketch out what insight the obtained "complexity phase diagrams" may shed on the underlying Hamiltonians in question, illustrating that the field of quantum computational supremacy has applications in theoretical physics.