Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature

Abstract

We establish an efficient approximation algorithm for the partition functions of a class of quantum spin systems at low temperature, which can be viewed as stable quantum perturbations of classical spin systems. Our algorithm is based on combining the contour representation of quantum spin systems of this type due to Borgs, Kotecký, and Ueltschi with the algorithmic framework developed by Helmuth, Perkins, and Regts, and Borgs et al.

arXiv comment12 pages, 0 figures, published version

References in corpus (9)

• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature
• Algorithmic Pirogov-Sinai theory
• Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
• Efficient Algorithms for Approximating Quantum Partition Functions
• Weighted counting of solutions to sparse systems of equations
• Efficient algorithms for the Potts model on small-set expanders
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
• Sampling from the low temperature Potts model through a Markov chain on flows

Cited by in corpus (6)

• Algorithmic Cluster Expansions for Quantum Problems
• Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Provably Efficient Simulation of 1D Long-Range Interacting Systems at Any Temperature
• High-temperature partition functions and classical simulatability of long-range quantum systems
• Efficient Algorithms for Weakly-Interacting Quantum Spin Systems