Complexity phase transition in interacting and long-range bosonic Hamiltonians

We investigate the complexity of sampling from time-evolved states due to bosonic Hamiltonians. We obtain timescales for which approximate sampling is easy and hard, generalising the results in Ref. [1] to systems with interacting bosons and to systems with long-range couplings. The easiness results rely on recent developments in the simulation of spatially local Hamiltonians [2,3]. For free bosons with long-range hops, where the strength of the hopping term decays with distance as a power law, we observe the hardness setting in earlier than the nearest-neighbor case. We also obtain hardness results for interacting bosons. Along the way, we develop methods and tools that are of independent interest. Our work maps out the timescale between easiness and hardness of sampling on a "complexity phase diagram", giving a testbed for exploring physical manifestations of the computational complexity of simulating interacting quantum systems.

[1] A. Deshpande, B. Fefferman, M. C. Tran, M. Foss-Feig, and A. V. Gorshkov, Phys. Rev. Lett. 121, 030501 (2018).
[2] J. Haah, M. B. Hastings, R. Kothari, and G. H. Low, arXiv:1801.03922 [quant-ph] (2018).
[3] M. C. Tran, A. Y. Guo, Y. Su, J. R. Garrison, Z. Eldredge, M. Foss-Feig, A. M. Childs, and A. V. Gorshkov, arXiv:1808.05225 [quant-ph] (2018).