Complexity phase diagram for interacting and long-range bosonic Hamiltonians
arXiv:1906.04178 · doi:10.1103/PhysRevLett.129.150604
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.
arXiv comment15 pages, 5 figures. v2: 19 pages, 7 figures
References in corpus (51)
- Quantum information with Rydberg atoms
- Probing many-body dynamics on a 51-atom quantum simulator
- Improved Simulation of Stabilizer Circuits
- Engineered 2D Ising interactions on a trapped-ion quantum simulator with hundreds of spins
- Realizing a lattice spin model with polar molecules
- 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
- Spectral Gap and Exponential Decay of Correlations
- Probing entanglement in a many-body-localized system
- Quantum many-body models with cold atoms coupled to photonic crystals
- Unitary-projective entanglement dynamics
- Universal computation by multi-particle quantum walk
- A blueprint for demonstrating quantum supremacy with superconducting qubits
- Emergence and Frustration of Magnetic Order with Variable-Range Interactions in a Trapped Ion Quantum Simulator
- Classical simulation of noninteracting-fermion quantum circuits
- Universality in Quantum Computation
- The computational complexity of PEPS
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- A practical scheme for quantum computation with any two-qubit entangling gate
- Scalable Architecture for a Room Temperature Solid-State Quantum Information Processor
- 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
- Mapping local Hamiltonians of fermions to local Hamiltonians of spins
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- 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
- Quantum Simulation of Spin Models on an Arbitrary Lattice with Trapped Ions
- Persistence of locality in systems with power-law interactions
- Simulating boson sampling in lossy architectures
- Architectures for quantum simulation showing a quantum speedup
- Hierarchy of linear light cones with long-range interactions
- A computationally universal phase of quantum matter
- An atom optics approach to studying lattice transport phenomena
- Locality and digital quantum simulation of power-law interactions
- Fast State Transfer and Entanglement Renormalization Using Long-Range Interactions
- Anticoncentration theorems for schemes showing a quantum speedup
- Supersonic quantum communication
- Contracting projected entangled pair states is average-case hard
- Signaling and Scrambling with Strongly Long-Range Interactions
- Dynamical phase transitions in sampling complexity
- Extreme statistics of complex random and quantum chaotic states
- 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