Title: Dynamical phase transitions in sampling complexity,
Abstract: We make the case for studying the complexity of approximately simulating
(sampling) quantum systems for reasons beyond that of quantum computational
supremacy, such as diagnosing phase transitions. We consider the sampling
complexity as a function of time $t$ due to evolution generated by spatially
local quadratic bosonic Hamiltonians. We obtain an upper bound on the scaling
of $t$ with the number of bosons $n$ for which approximate sampling is
classically efficient. We also obtain a lower bound on the scaling of $t$ with
$n$ for which any instance of the boson sampling problem reduces to this
problem and hence implies that the problem is hard, assuming the conjectures of
Aaronson and Arkhipov [Proc. 43rd Annu. ACM Symp. Theory Comput. STOC '11].
This establishes a dynamical phase transition in sampling complexity. Further,
we show that systems in the Anderson-localized phase are always easy to sample
from at arbitrarily long times. We view these results in the light of
classifying phases of physical systems based on parameters in the Hamiltonian.
In doing so, we combine ideas from mathematical physics and computational
complexity to gain insight into the behavior of condensed matter, atomic,
molecular and optical systems.