Complexity of sampling as an order parameter

We consider the classical complexity of approximately simulating time evolution under spatially local quadratic bosonic Hamiltonians for time t. We obtain upper and lower bounds on the scaling of twith the number of bosons, n, for which simulation, cast as a sampling problem, is classically efficient and provably hard, respectively. We view these results in the light of classifying phases of physical systems based on parameters in the Hamiltonian and conjecture a link to dynamical phase transitions. In doing so, we combine ideas from mathematical physics and computational complexity to gain insight into the behavior of condensed matter systems.