Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states

Abstract

One of the most fundamental problems in quantum many-body physics is the characterization of correlations among thermal states. Of particular relevance is the thermal area law, which justifies the tensor network approximations to thermal states with a bond dimension growing polynomially with the system size. In the regime of sufficiently low temperatures, which is particularly important for practical applications, the existing techniques do not yield optimal bounds. Here, we propose a new thermal area law that holds for generic many-body systems on lattices. We improve the temperature dependence from the original $\mathcal{O}(\beta )$ to $\tilde{\mathcal{O}}({\beta }^{2/3})$, thereby suggesting diffusive propagation of entanglement by imaginary time evolution. This qualitatively differs from the real-time evolution which usually induces linear growth of entanglement. We also prove analogous bounds for the Rényi entanglement of purification and the entanglement of formation. Our analysis is based on a polynomial approximation to the exponential function which provides a relationship between the imaginary-time evolution and random walks. Moreover, for one-dimensional (1D) systems with $n$ spins, we prove that the Gibbs state is well-approximated by a matrix product operator with a sublinear bond dimension of $e^{\sqrt{\tilde{\mathcal{O}}(\beta \log (n))}}$. This proof allows us to rigorously establish, for the first time, a quasi-linear time classical algorithm for constructing an MPS representation of 1D quantum Gibbs states at arbitrary temperatures of $\beta =o(\log (n))$. Our new technical ingredient is a block decomposition of the Gibbs state, that bears resemblance to the decomposition of real-time evolution given by Haah et al., FOCS'18.

arXiv comment20 pages + 29 pages, 9 figures - v2: published version

References in corpus (95)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Machine Learning
• The density-matrix renormalization group in the age of matrix product states
• The density-matrix renormalization group
• Area laws for the entanglement entropy - a review
• Entanglement in quantum critical phenomena
• Probing many-body dynamics on a 51-atom quantum simulator
• Efficient simulation of one-dimensional quantum many-body systems
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit Quantum Simulator
• An Area Law for One Dimensional Quantum Systems
• Time-dependent variational principle for quantum lattices
• Unifying time evolution and optimization with matrix product states
• Matrix product states represent ground states faithfully
• Area laws in quantum systems: mutual information and correlations
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• Mixed-state dynamics in one-dimensional quantum lattice systems: a time-dependent superoperator renormalization algorithm
• Variational ansatz-based quantum simulation of imaginary time evolution
• A Theory of Trotter Error
• The iTEBD algorithm beyond unitary evolution
• Theory of variational quantum simulation
• Quantum chemistry calculations on a trapped-ion quantum simulator
• Floquet-Magnus Theory and Generic Transient Dynamics in Periodically Driven Many-Body Quantum Systems
• Quantum Boltzmann Machine
• Sequential generation of entangled multi-qubit states
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Quantum Metropolis Sampling
• Minimally Entangled Typical Thermal State Algorithms
• The entanglement of purification
• Continuity of quantum conditional information
• Minimally entangled typical quantum states at finite temperature
• Solving Gapped Hamiltonians Locally
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• General entanglement scaling laws from time evolution
• Numerical Linked-Cluster Approach to Quantum Lattice Models
• Entropy and Entanglement in Quantum Ground States
• Learning a local Hamiltonian from local measurements
• Tomography and Generative Data Modeling via Quantum Boltzmann Training
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• Hamiltonian complexity
• Variational Quantum Eigensolver with Fewer Qubits
• A Quantum-Quantum Metropolis Algorithm
• Encoding of Matrix Product States into Quantum Circuits of One- and Two-Qubit Gates
• Approximating Gibbs states of local Hamiltonians efficiently with PEPS
• Quantum Hamiltonian Complexity
• An area law for entanglement from exponential decay of correlations
• Locality of temperature
• Simulation of Nonequilibrium Dynamics on a Quantum Computer
• A Short Introduction to Numerical Linked-Cluster Expansions
• An area law for the entropy of low-energy states
• Quantum Belief Propagation
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Machine learning quantum states in the NISQ era
• Entanglement rates and area laws
• Linearized Tensor Renormalization Group Algorithm for Thermodynamics of Quantum Lattice Models
• Exponential Thermal Tensor Network Approach for Quantum Lattice Models
• Stochastic Error Cancellation in Analog Quantum Simulation
• Variational Approach to Projected Entangled Pair States at Finite Temperature
• Purifications of multipartite states: limitations and constructive methods
• Quantum thermalization dynamics with Matrix-Product States
• Implementation of quantum imaginary-time evolution method on NISQ devices: Nonlocal approximation
• Quantum SDP-Solvers: Better upper and lower bounds
• Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature
• An improved 1D area law for frustration-free systems
• Complexity of thermal states in quantum spin chains
• Rapid adiabatic preparation of injective PEPS and Gibbs states
• Preparing thermal states of quantum systems by dimension reduction
• Rigorous RG algorithms and area laws for low energy eigenstates in 1D
• Upper bounds on entangling rates of bipartite Hamiltonians
• Entanglement vs. gap for one-dimensional spin systems
• Area law of non-critical ground states in 1D long-range interacting systems
• Large deviations for quantum spin systems
• Large deviations in quantum lattice systems: one-phase region
• Quantum Approximate Markov Chains are Thermal
• Fundamental limitations in the purifications of tensor networks
• Some Properties of Correlations of Quantum Lattice Systems in Thermal Equilibrium
• Minimally entangled typical thermal states versus matrix product purifications for the simulation of equilibrium states and time evolution
• Making Trotters Sprint: A Variational Imaginary Time Ansatz for Quantum Many-body Systems
• Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
• Monogamy, polygamy, and other properties of entanglement of purification
• Efficient description of many-body systems with Matrix Product Density Operators
• Gaussian concentration bound and Ensemble equivalence in generic quantum many-body systems including long-range interaction
• Eigenstate thermalization from the clustering property of correlation
• Polynomial-time classical simulation of quantum ferromagnets
• Local tests of global entanglement and a counterexample to the generalized area law
• Mutual information area laws for thermal free fermions
• Observations Outside the Light-Cone: Algorithms for Non-Equilibrium and Thermal States
• Belief propagation algorithm for computing correlation functions in finite-temperature quantum many-body systems on loopy graphs
• Thermal States as Convex Combinations of Matrix Product States
• One-dimensional quantum systems at finite temperatures can be simulated efficiently on classical computers
• Coarse grained belief propagation for simulation of interacting quantum systems at all temperatures
• Efficient Algorithms for Approximating Quantum Partition Functions
• Approximate quantum Markov chains
• A polynomial-time algorithm for ground states of spin trees

Cited by in corpus (49)

• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• Speed limits and locality in many-body quantum dynamics
• Nearly tight Trotterization of interacting electrons
• Area law of non-critical ground states in 1D long-range interacting systems
• Classical simulation of short-time quantum dynamics
• Lieb-Robinson bound and almost-linear light-cone in interacting boson systems
• Light cone tensor network and time evolution
• Quantum many-body systems in thermal equilibrium
• Exponential decay of mutual information for Gibbs states of local Hamiltonians
• On the complexity of implementing Trotter steps
• Computable Rényi mutual information: Area laws and correlations
• Learning quantum many-body systems from a few copies
• Exponential clustering of bipartite quantum entanglement at arbitrary temperatures
• Exact Thermal Eigenstates of Nonintegrable Spin Chains at Infinite Temperature
• Certified algorithms for equilibrium states of local quantum Hamiltonians
• Approximating the long time average of the density operator: Diagonal ensemble
• Many-body entropies and entanglement from polynomially-many local measurements
• Decay of quantum conditional mutual information for purely generated finitely correlated states
• Universality in the tripartite information after global quenches: (generalised) quantum XY models
• Thermalization in Kitaev's quantum double models via Tensor Network techniques
• Rényi free energy and variational approximations to thermal states
• Dynamical correlation functions from complex time evolution
• A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit
• Thermal Area Law in Long-Range Interacting Systems
• Accounting for Quantum Effects in Atomistic Spin Dynamics
• From decay of correlations to locality and stability of the Gibbs state
• Matrix product state approximations to quantum states of low energy variance
• Clustering theorem in 1D long-range interacting systems at arbitrary temperatures
• Tensor-network approach to thermalization in open quantum many-body systems
• Matrix product states and the decay of quantum conditional mutual information
• Clustering of conditional mutual information and quantum Markov structure at arbitrary temperatures
• Thermal Area Law for Lattice Bosons
• Counting atypical black hole microstates from entanglement wedges
• Universal contributions to charge fluctuations in spin chains at finite temperature
• Universality in the tripartite information after global quenches: spin flip and semilocal charges
• Variational Microcanonical Estimator
• Thermal pure matrix product state in two dimensions: tracking thermal equilibrium from paramagnet down to the Kitaev honeycomb spin liquid state
• Measuring multipartite quantum correlations by thermodynamic work extraction
• Conditional Independence of 1D Gibbs States with Applications to Efficient Learning
• Provably Efficient Simulation of 1D Long-Range Interacting Systems at Any Temperature
• A Faster Algorithm for the Free Energy in One-Dimensional Quantum Systems
• Efficient Simulation of Low Temperature Physics in One-Dimensional Gapless Systems
• Real-space spectral simulation of quantum spin models: Application to generalized Kitaev models
• Sample complexity of matrix product states at finite temperature
• Quantum Fisher information from tensor network integration of Lyapunov equation
• The product structure of MPS-under-permutations
• Learning mixed quantum states in large-scale experiments
• Variational quantum simulation of the quantum critical regime
• Locally accurate tensor networks for thermal states and time evolution