Complexity Phase Diagram for Interacting and Long-Range Bosonic Hamiltonians

Here, 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 nu...

Full description

Saved in:
Bibliographic Details
Published in:Physical review letters 2022-10, Vol.129 (15), p.150604-150604, Article 150604
Main Authors: Maskara, Nishad, Deshpande, Abhinav, Ehrenberg, Adam, Tran, Minh C., Fefferman, Bill, Gorshkov, Alexey V.
Format: Article
Language:English
Subjects:
Bose-Hubbard model
boson sampling
cold gases in optical lattices
computational complexity
many-body techniques
MATHEMATICS AND COMPUTING
quantum algorithms
quantum protocols
quantum simulation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Here, 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 does change. Specifically, we find that there are two kinds of transitions, sharp and coarse, broadly corresponding to interacting and noninteracting bosons, respectively. Our Letter motivates future studies of complexity in many-body systems and its interplay with the associated physical phenomena.
ISSN:0031-9007
1079-7114
DOI:10.1103/PhysRevLett.129.150604