Simulation Complexity of Many-Body Localized Systems

We investigate the difficulty of classically simulating evolution under many-body localized (MBL) Hamiltonians. Using the defining feature that MBL systems have a complete set of local integrals of motion (LIOMs), we demonstrate a transition in the classical complexity of simulating such systems as a function of evolution time. On one side, we construct a quasipolynomial-time tensor-network-inspired algorithm that can simulate MBL systems evolved for any time polynomial in the system size. On the other, we prove that classical simulation becomes formally hard after an exponentially long evolution time, assuming widely believed conjectures in complexity theory. If there is time, we will also discuss the gate complexity of quantum simulation for MBL systems and show that it is sublinear in evolution time.
(Pizza and drinks served after the talk.)