Sample complexity of matrix product states at finite temperature
arXiv:2403.10018 · doi:10.1103/PhysRevB.109.224410
Abstract
For quantum many-body systems in one dimension, computational complexity theory reveals that the evaluation of ground-state energy remains elusive on quantum computers, contrasting the existence of a classical algorithm for temperatures higher than the inverse logarithm of the system size. This highlights a qualitative difference between low- and high-temperature states in terms of computational complexity. Here, we describe finite-temperature states using the matrix product state formalism. Within the framework of random samplings, we derive an analytical formula for the required number of samples, which provides both quantitative and qualitative measures of computational complexity. At high and low temperatures, its scaling behavior with system size is linear and quadratic, respectively, demonstrating a distinct crossover between these numerically difficult regimes of quantitative difference.
arXiv comment12 pages, 3 figures
References in corpus (73)
- The density-matrix renormalization group in the age of matrix product states
- Area laws for the entanglement entropy - a review
- Probing many-body dynamics on a 51-atom quantum simulator
- Many body localization and thermalization in quantum statistical mechanics
- Many-body localization, thermalization, and entanglement
- Efficient simulation of one-dimensional quantum many-body systems
- Real time evolution using the density matrix renormalization group
- Realization of the Hofstadter Hamiltonian with ultracold atoms in optical lattices
- Time-dependent density-matrix renormalization-group using adaptive effective Hilbert spaces
- Realizing the Harper Hamiltonian with Laser-Assisted Tunneling in Optical Lattices
- 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
- The foundations of statistical mechanics from entanglement: Individual states vs. averages
- The ITensor Software Library for Tensor Network Calculations
- Canonical Typicality
- Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
- Mixed-state dynamics in one-dimensional quantum lattice systems: a time-dependent superoperator renormalization algorithm
- Eigenstate Thermalization Hypothesis
- Thermalization and prethermalization in isolated quantum systems: a theoretical overview
- Computational Studies of Quantum Spin Systems
- Quantum Many-Body Scars and Hilbert Space Fragmentation: A Review of Exact Results
- Observation of topological phenomena in a programmable lattice of 1,800 qubits
- Finite Temperature Density Matrix Renormalization using an enlarged Hilbert space
- Minimally Entangled Typical Thermal State Algorithms
- Long-range interacting quantum systems
- Typicality for Generalized Microcanonical Ensembles
- Undecidability of the Spectral Gap (short version)
- Minimally entangled typical quantum states at finite temperature
- Quantum Many-Body Scars: A Quasiparticle Perspective
- Solving Gapped Hamiltonians Locally
- Canonical Thermal Pure Quantum State
- The power of quantum systems on a line
- Thermal Pure Quantum States at Finite Temperature
- Fast Algorithm for Finding the Eigenvalue Distribution of Very Large Matrices
- Numerical Linked-Cluster Approach to Quantum Lattice Models
- Approximating Gibbs states of local Hamiltonians efficiently with PEPS
- Entanglement scaling of operators: a conformal field theory approach, with a glimpse of simulability of long-time dynamics in 1+1d
- Locality of temperature
- Power law violation of the area law in quantum spin chains
- Quantum Computation of Finite-Temperature Static and Dynamical Properties of Spin Systems Using Quantum Imaginary Time Evolution
- Criticality without frustration for quantum spin-1 chains
- Numerical Linked-Cluster Algorithms. I. Spin systems on square, triangular, and kagome lattices
- Exponential Thermal Tensor Network Approach for Quantum Lattice Models
- Entanglement area laws for long-range interacting systems
- Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature
- Complexity of thermal states in quantum spin chains
- Rigorous RG algorithms and area laws for low energy eigenstates in 1D
- Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
- Numerical Linked-Cluster Algorithms. II. t-J models on the square lattice
- Finding purifications with minimal entanglement
- Accuracy of the finite-temperature Lanczos method compared to simple typicality-based estimates
- Area law of non-critical ground states in 1D long-range interacting systems
- Tangent Space Approach for Thermal Tensor Network Simulations of the 2D Hubbard Model
- Toward Quantum Computing Phase Diagrams of Gauge Theories with Thermal Pure Quantum States
- Random State Technology
- Predicting Gibbs-State Expectation Values with Pure Thermal Shadows
- Minimally entangled typical thermal states versus matrix product purifications for the simulation of equilibrium states and time evolution
- Undecidability of the Spectral Gap in One Dimension
- Thermal Pure Quantum Matrix Product States Recovering a Volume Law Entanglement
- Symmetric minimally entangled typical thermal states for canonical and grand-canonical ensembles
- Adaptive variational quantum minimally entangled typical thermal states for finite temperature simulations
- Symmetric Minimally Entangled Typical Thermal States
- Hybrid Purification and Sampling Approach for Thermal Quantum Systems
- Implementation of rigorous renormalization group method for ground space and low-energy states of local Hamiltonians
- Generalized quantum microcanonical ensemble from random matrix product states
- Matrix product state approach for a quantum system at finite temperatures using random phases and Trotter gates
- Purity of thermal mixed quantum states
- Pure state thermodynamics with matrix product states
- Energy-filtered random-phase states as microcanonical thermal pure quantum states
- Minimally entangled typical thermal states algorithm with Trotter gates
- Evaluating thermal expectation values by almost ideal sampling with Trotter gates
- Thermal pure matrix product state in two dimensions: tracking thermal equilibrium from paramagnet down to the Kitaev honeycomb spin liquid state