Title: Complexity of sampling as an order parameter
Speaker Name: Abhinav Deshpande
Speaker Institution: QuICS and JQI
Abstract: We consider the classical complexity of approximately simulating time evolution under spatially local quadratic bosonic Hamiltonians for time t. We obtain upper bounds on the scaling of t with the number of bosons, n, for which simulation is classically efficient. We also obtain a lower bound on the scaling of t with n for which this problem reduces to a general instance of the boson sampling problem and is hence hard, assuming the conjectures of Aaronson and Arkhipov [Proc. 43rd Annu. ACM Symp. Theory Comput. STOC '11]. 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.