Dynamical phase transitions in sampling complexity

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 $t$ due to evolution generated by spatially local quadratic bosonic Hamiltonians. We obtain an upper bound on the scaling of $t$ with the number of bosons $n$ for which approximate sampling is classically efficient. We also obtain a lower bound on the scaling of $t$ with $n$ 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.

12 pages, 4 figures. v3: published version

References in corpus (22)

• Probing many-body dynamics on a 51-atom quantum simulator
• Single-Atom Resolved Fluorescence Imaging of an Atomic Mott Insulator
• Quantum Computational Supremacy
• Single-Spin Addressing in an Atomic Mott Insulator
• Dynamical quantum phase transitions: a review
• Spectral signatures of many-body localization with interacting photons
• Lyapunov Exponent and Out-of-Time-Ordered Correlator's Growth Rate in a Chaotic System
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• The Second Law of Quantum Complexity
• Observation of molecules produced from a Bose-Einstein condensate
• Formation of Quantum-Degenerate Sodium Molecules
• Slow scrambling in disordered quantum systems
• No imminent quantum supremacy by boson sampling
• Many-body localisation implies that eigenvectors are matrix-product states
• Characterizing Many-Body Localization by Out-of-Time-Ordered Correlation
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Site-resolved imaging of ytterbium atoms in a two-dimensional optical lattice
• Entanglement Complexity in Quantum Many-Body Dynamics, Thermalization and Localization
• Universal Logarithmic Scrambling in Many Body Localization
• Detecting two-site spin-entanglement in many-body systems with local particle-number fluctuations
• The complexity of simulating constant-depth BosonSampling
• Exact sampling hardness of Ising spin models

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