Efficient Algorithms for Approximating Quantum Partition Functions

Abstract

We establish a polynomial-time approximation algorithm for partition functions of quantum spin models at high temperature. Our algorithm is based on the quantum cluster expansion of Netočný and Redig and the cluster expansion approach to designing algorithms due to Helmuth, Perkins, and Regts. Similar results have previously been obtained by related methods, and our main contribution is a simple and slightly sharper analysis for the case of pairwise interactions on bounded-degree graphs.

arXiv comment7 pages, 0 figures, published version

References in corpus (9)

• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature
• Large deviations for quantum spin systems
• Algorithmic Pirogov-Sinai theory
• The Ising Partition Function: Zeros and Deterministic Approximation
• Efficient algorithms for the Potts model on small-set expanders
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs

Cited by in corpus (14)

• Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
• Classical simulation of short-time quantum dynamics
• Quantum many-body systems in thermal equilibrium
• Certified algorithms for equilibrium states of local quantum Hamiltonians
• Optimal quantum algorithm for Gibbs state preparation
• Algorithmic Cluster Expansions for Quantum Problems
• Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature
• A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit
• Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
• Positive bias makes tensor-network contraction tractable
• A Faster Algorithm for the Free Energy in One-Dimensional Quantum Systems
• High-temperature partition functions and classical simulatability of long-range quantum systems
• Stability of thermal equilibrium in long-range quantum systems
• Efficient Algorithms for Weakly-Interacting Quantum Spin Systems