Complexity phase diagram for interacting and long-range bosonic Hamiltonians

Abstract

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.

15 pages, 5 figures. v2: 19 pages, 7 figures

References in corpus (24)

• Probing many-body dynamics on a 51-atom quantum simulator
• An atom-by-atom assembler of defect-free arbitrary 2d atomic arrays
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• Quantum Zeno Effect and the Many-body Entanglement Transition
• Probing entanglement in a many-body-localized system
• Unitary-projective entanglement dynamics
• Universal computation by multi-particle quantum walk
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Nearly-linear light cones in long-range interacting quantum systems
• Matchgates and classical simulation of quantum circuits
• Microscopic control and detection of ultracold strontium in optical-tweezer arrays
• Applying matrix product operators to model systems with long-range interactions
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• Efficient classical simulation of random shallow 2D quantum circuits
• Hierarchy of linear light cones with long-range interactions
• Locality and digital quantum simulation of power-law interactions
• Contracting projected entangled pair states is average-case hard
• Signaling and Scrambling with Strongly Long-Range Interactions
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Universal extensions of restricted classes of quantum operations
• Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice
• The complexity of simulating constant-depth BosonSampling
• Bose-Hubbard model for universal quantum walk-based computation
• Scale-Invariant Continuous Entanglement Renormalization of a Chern Insulator

Cited by in corpus (14)

• Computational advantage of quantum random sampling
• Computational power of one- and two-dimensional dual-unitary quantum circuits
• Programmable quantum simulations of bosonic systems with trapped ions
• An atomic boson sampler
• Finite-time teleportation phase transition in random quantum circuits
• Finite speed of quantum information in models of interacting bosons at finite density
• Effective light cone and digital quantum simulation of interacting bosons
• Page curves and typical entanglement in linear optics
• Sharp complexity phase transitions generated by entanglement
• Quantum complexity phase transitions in monitored random circuits
• Classical simulation of bosonic linear-optical random circuits beyond linear light cone
• Complexity of Gaussian quantum optics with a limited number of non-linearities
• Revealing effects of local dimension on variable-range interacting model by connecting Lieb-Robinson bounds and multipartite entanglement
• Dynamical complexity of non-Gaussian many-body systems with dissipation