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.
12 pages, 3 figures
References in corpus (23)
- The density-matrix renormalization group in the age of matrix product states
- Probing many-body dynamics on a 51-atom quantum simulator
- Many body localization and thermalization in quantum statistical mechanics
- Real time evolution using the density matrix renormalization group
- Matrix Product Density Operators: Simulation of finite-T and dissipative systems
- Minimally Entangled Typical Thermal State Algorithms
- Typicality for Generalized Microcanonical Ensembles
- Quantum Many-Body Scars: A Quasiparticle Perspective
- The power of quantum systems on a line
- Numerical Linked-Cluster Approach to Quantum Lattice Models
- Approximating Gibbs states of local Hamiltonians efficiently with PEPS
- Numerical Linked-Cluster Algorithms. I. Spin systems on square, triangular, and kagome lattices
- Complexity of thermal states in quantum spin chains
- Numerical Linked-Cluster Algorithms. II. t-J models on the square lattice
- Accuracy of the finite-temperature Lanczos method compared to simple typicality-based estimates
- Toward Quantum Computing Phase Diagrams of Gauge Theories with Thermal Pure Quantum States
- Tangent Space Approach for Thermal Tensor Network Simulations of the 2D Hubbard Model
- Predicting Gibbs-State Expectation Values with Pure Thermal Shadows
- Adaptive variational quantum minimally entangled typical thermal states for finite temperature simulations
- Purity of thermal mixed quantum states
- Energy-filtered random-phase states as microcanonical thermal pure quantum states
- 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