Efficient Algorithms for Weakly-Interacting Quantum Spin Systems
Provides the first efficient algorithms for a broad class of quantum spin systems, solving a long-standing problem in quantum statistical mechanics.
The paper develops efficient algorithms (FPTAS for partition function and efficient approximate sampling) for weakly-interacting quantum spin systems at arbitrary temperature, using cluster expansion and reduction from sampling to counting.
We establish efficient algorithms for weakly-interacting quantum spin systems at arbitrary temperature. In particular, we obtain a fully polynomial-time approximation scheme for the partition function and an efficient approximate sampling scheme for the thermal distribution over a classical spin space. Our approach is based on the cluster expansion method and a standard reduction from approximate sampling to approximate counting.