  We classify phases of a bosonic lattice model based on the computational
complexity of classically simulating the system. We show that the system
transitions from being classically simulable to classically hard to simulate as
it evolves in time, extending previous results to include on-site
number-conserving interactions and long-range hopping. Specifically, we
construct a "complexity phase diagram" with "easy" and "hard" phases, and
derive analytic bounds on the location of the phase boundary with respect to
the evolution time and the degree of locality. We find that the location of the
phase transition is intimately related to upper bounds on the spread of quantum
correlations and protocols to transfer quantum information. Remarkably,
although the location of the transition point is unchanged by on-site
interactions, the nature of the transition point changes dramatically.
Specifically, we find that there are two kinds of transitions, sharp and
coarse, broadly corresponding to interacting and noninteracting bosons,
respectively. Our work motivates future studies of complexity in many-body
systems and its interplay with the associated physical phenomena.
