A Faster Algorithm for the Free Energy in One-Dimensional Quantum Systems
arXiv:2402.19030 · doi:10.1063/5.0218349
Abstract
We consider the problem of approximating the free energy density of a translation-invariant, one-dimensional quantum spin system with finite range. While the complexity of this problem is nontrivial due to its close connection to problems with known hardness results, a classical subpolynomial-time algorithm has recently been proposed [Fawzi et al., 2022]. Combining several algorithmic techniques previously used for related problems, we propose an algorithm outperforming this result asymptotically and give rigorous bounds on its runtime. Our main techniques are the use of Araki expansionals, known from results on the nonexistence of phase transitions, and a matrix product operator construction. We also review a related approach using the Quantum Belief Propagation [Kuwahara et al., 2018], which in combination with our findings yields an equivalent result.
References in corpus (12)
- Sample-efficient learning of quantum many-body systems
- Quantum Belief Propagation
- Exponential Thermal Tensor Network Approach for Quantum Lattice Models
- Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
- Large deviations in quantum lattice systems: one-phase region
- On the complexity of quantum partition functions
- Quantum many-body systems in thermal equilibrium
- Exponential decay of mutual information for Gibbs states of local Hamiltonians
- The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
- Efficient Algorithms for Approximating Quantum Partition Functions
- A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit
- Polynomial-time Classical Simulation for One-dimensional Quantum Gibbs States