Dynamical phase transitions in sampling complexity
arXiv:1703.05332 · doi:10.1103/PhysRevLett.121.030501
Abstract
We make the case for studying the complexity of approximately simulating (sampling) quantum systems for reasons beyond that of quantum computational supremacy, such as diagnosing phase transitions. We consider the sampling complexity as a function of time due to evolution generated by spatially local quadratic bosonic Hamiltonians. We obtain an upper bound on the scaling of with the number of bosons for which approximate sampling is classically efficient. We also obtain a lower bound on the scaling of with for which any instance of the boson sampling problem reduces to this problem and hence implies that the problem is hard, assuming the conjectures of Aaronson and Arkhipov [Proc. 43rd Annu. ACM Symp. Theory Comput. STOC '11]. This establishes a dynamical phase transition in sampling complexity. Further, we show that systems in the Anderson-localized phase are always easy to sample from at arbitrarily long times. We view these results in the light of classifying phases of physical systems based on parameters in the Hamiltonian. In doing so, we combine ideas from mathematical physics and computational complexity to gain insight into the behavior of condensed matter, atomic, molecular and optical systems.
arXiv comment12 pages, 4 figures. v3: published version
References in corpus (60)
- Probing many-body dynamics on a 51-atom quantum simulator
- A bound on chaos
- Gapless Spin-Fluid Ground State in a Random Quantum Heisenberg Magnet
- Comments on the Sachdev-Ye-Kitaev model
- A quantum gas microscope - detecting single atoms in a Hubbard regime optical lattice
- Single-Atom Resolved Fluorescence Imaging of an Atomic Mott Insulator
- Fast Scramblers
- Unbounded growth of entanglement in models of many-body localization
- Complexity Equals Action
- Dynamical Quantum Phase Transitions in the Transverse Field Ising Model
- Quantum Computational Supremacy
- Probing the Superfluid to Mott Insulator Transition at the Single Atom Level
- Single-Spin Addressing in an Atomic Mott Insulator
- Chaos in quantum channels
- Dynamical quantum phase transitions: a review
- Complexity, action, and black holes
- Qubit architecture with high coherence and fast tunable coupling
- Quantum dynamics of a single, mobile spin impurity
- Spectral signatures of many-body localization with interacting photons
- Chaos and complexity by design
- Towards the fast scrambling conjecture
- Lyapunov Exponent and Out-of-Time-Ordered Correlator's Growth Rate in a Chaotic System
- Classical simulation of noninteracting-fermion quantum circuits
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- The Second Law of Quantum Complexity
- Out-of-Time-Order Correlation for Many-Body Localization
- Observation of molecules produced from a Bose-Einstein condensate
- Formation of Quantum-Degenerate Sodium Molecules
- Slow scrambling in disordered quantum systems
- Out-of-time-ordered correlators in many-body localized systems
- Hong-Ou-Mandel atom interferometry in tunnel-coupled optical tweezers
- Solvable model for a dynamical quantum phase transition from fast to slow scrambling
- No imminent quantum supremacy by boson sampling
- Obtaining highly-excited eigenstates of many-body localized Hamiltonians by the density matrix renormalization group
- Finding matrix product state representations of highly-excited eigenstates of many-body localized Hamiltonians
- Many-body localisation implies that eigenvectors are matrix-product states
- Characterizing Many-Body Localization by Out-of-Time-Ordered Correlation
- Coherent addressing of individual neutral atoms in a 3D optical lattice
- Observing Topological Invariants Using Quantum Walk in Superconducting Circuits
- Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
- Quantum Information Meets Quantum Matter -- From Quantum Entanglement to Topological Phase in Many-Body Systems
- Site-resolved imaging of ytterbium atoms in a two-dimensional optical lattice
- Efficient variational diagonalization of fully many-body localized Hamiltonians
- A Linear-Optical Proof that the Permanent is #P-Hard
- Dynamical Localization in Disordered Quantum Spin Systems
- Cooling and Autonomous Feedback in a Bose-Hubbard chain with Attractive Interactions
- BosonSampling with Lost Photons
- Entanglement Complexity in Quantum Many-Body Dynamics, Thermalization and Localization
- Universal Logarithmic Scrambling in Many Body Localization
- Supersonic quantum communication
- Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states---The quantum-classical divide and computational-complexity transitions in linear optics
- Site-resolved imaging of single atoms with a Faraday quantum gas microscope
- A Hubbard model for ultracold bosonic atoms interacting via zero-point-energy induced three-body interactions
- The complexity of simulating constant-depth BosonSampling
- Detecting two-site spin-entanglement in many-body systems with local particle-number fluctuations
- Superconducting circuit simulator of Bose-Hubbard model with a flat band
- Exact sampling hardness of Ising spin models
- Computational complexity of non-equilibrium steady states of quantum spin chains
- Efficient simulation of many-body localized systems
Cited by in corpus (39)
- Efficient classical simulation of random shallow 2D quantum circuits
- Computational advantage of quantum random sampling
- Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
- Hierarchy of linear light cones with long-range interactions
- The Lieb-Robinson light cone for power-law interactions
- Locality and digital quantum simulation of power-law interactions
- Computational power of one- and two-dimensional dual-unitary quantum circuits
- Classical simulation of boson sampling based on graph structure
- Temporal Entanglement in Chaotic Quantum Circuits
- Dynamical quantum phase transition from a critical quantum quench
- Programmable quantum simulations of bosonic systems with trapped ions
- Interference of Temporally Distinguishable Photons Using Frequency-Resolved Detection
- Lieb-Robinson bound and almost-linear light-cone in interacting boson systems
- An atomic boson sampler
- Noise in BosonSampling and the threshold of efficient classical simulatability
- Finite speed of quantum information in models of interacting bosons at finite density
- Resource theory of quantum uncomplexity
- Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice
- Complexity phase diagram for interacting and long-range bosonic Hamiltonians
- Distinguishing noisy boson sampling from classical simulations
- Page curves and typical entanglement in linear optics
- On the sampling complexity of open quantum systems
- Complexity of Fermionic Dissipative Interactions and Applications to Quantum Computing
- Disordered Lieb-Robinson bounds in one dimension
- Complexity-constrained quantum thermodynamics
- Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
- Entanglement and complexity of interacting qubits subject to asymmetric noise
- Quantum advantage from energy measurements of many-body quantum systems
- Quantum complexity phase transitions in monitored random circuits
- Dynamical phase transitions of information flow in random quantum circuits
- Classical simulability of constant-depth linear-optical circuits with noise
- Distinguishability Transitions in Non-Unitary Boson Sampling Dynamics
- Classical simulation of bosonic linear-optical random circuits beyond linear light cone
- Optimal spatial searches with long-range tunneling
- State-dependent mobility edge in kinetically constrained models
- On computational complexity and average-case hardness of shallow-depth boson sampling
- Quantum computational advantage of noisy boson sampling with partially distinguishable photons
- Dynamical complexity of non-Gaussian many-body systems with dissipation
- Clustering of steady-state correlations in open systems with long-range interactions