Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2201.06533 · Quantum

Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature

Tyler Helmuth, Ryan L. Mann

Published Oct 25, 2023• 6 citations
arXivHTMLPDF

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.

DOI
10.22331/q-2023-10-25-1155

Related papers

Efficient Algorithms for Weakly-Interacting Quantum Spin Systems

Ryan L. Mann, Gabriel Waite

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.

quant-pharXiv:2601.21140•Physical Review A•Jan 30, 2026•0 citations

Efficient algorithms for approximating quantum partition functions

Ryan L. Mann, Tyler Helmuth

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:2004.11568•Journal of Mathematical Physics•Feb 1, 2021•17 citations

High-Temperature Partition Functions and Classical Simulatability of Long-Range Quantum Systems

Jorge Sánchez-Segovia, Jan T. Schneider, Alvaro Martin Alhambra

Long-range quantum systems, in which the interactions decay as 1 / r α , are of increasing interest due to the variety of experimental setups in which they naturally appear. Motivated by this, we study fundamental properties of long-range spin systems in thermal equilibrium, focusing on the weak regime of α > D . Our main result is a proof of analyticity of their partition functions at high temperatures, which allows us to construct a classical algorithm with subexponential runtime exp  ( O ( log 2  ( N / ϵ ) ) ) that approximates the log-partition function to small additive error ϵ . As by-products, we establish the equivalence of ensembles and the Gaussianity of the density of states, which we verify numerically in both the weak and strong long-range regimes. This also yields constraints on the appearance of various classes of phase transitions, including thermal, dynamical, and excited-state ones. Our main technical contribution is the extension to the quantum long-range regime of the convergence criterion for cluster expansions of Kotecký and Preiss.

arXiv:2504.20901•PRX Quantum•Nov 17, 2025•1 citation

Algorithmic Cluster Expansions for Quantum Problems

Ryan L. Mann, Romy Minko

We establish a general framework for developing approximation algorithms for a class of counting problems. Our framework is based on the cluster expansion of the abstract polymer model formalism of Kotecký and Preiss. We apply our framework to obtain efficient algorithms for (1) approximating probability amplitudes of a class of quantum circuits close to the identity, (2) approximating expectation values of a class of quantum circuits with operators close to the identity, (3) approximating partition functions of a class of quantum spin systems at high temperature, and (4) approximating thermal expectation values of a class of quantum spin systems at high temperature with positive-semidefinite operators. Further, we obtain hardness of approximation results for approximating probability amplitudes of quantum circuits and partition functions of quantum spin systems. This establishes a computational complexity transition for these problems and shows that our algorithmic conditions are optimal under complexity-theoretic assumptions. Finally, we show that our algorithmic condition is almost optimal for expectation values and optimal for thermal expectation values in the sense of zero freeness. Published by the American Physical Society 2024

arXiv:2306.08974•PRX Quantum•Jan 16, 2024•9 citations

Polynomial-Time Approximation of Zero-Free Partition Functions

Penghui Yao, Yitong Yin, Xinyuan Zhang

Zero-free based algorithm is a major technique for deterministic approximate counting. In Barvinok's original framework[Bar17], by calculating truncated Taylor expansions, a quasi-polynomial time algorithm was given for estimating zero-free partition functions. Patel and Regts[PR17] later gave a refinement of Barvinok's framework, which gave a polynomial-time algorithm for a class of zero-free graph polynomials that can be expressed as counting induced subgraphs in bounded-degree graphs. In this paper, we give a polynomial-time algorithm for estimating classical and quantum partition functions specified by local Hamiltonians with bounded maximum degree, assuming a zero-free property for the temperature. Consequently, when the inverse temperature is close enough to zero by a constant gap, we have polynomial-time approximation algorithm for all such partition functions. Our result is based on a new abstract framework that extends and generalizes the approach of Patel and Regts.

arXiv:2201.12772•Leibniz international proceedings in informatics•Jan 1, 2022•0 citations

Fast Algorithms for Stoquastic Spin Systems

Ryan L. Mann

We establish a general framework for developing fast sampling and counting algorithms for stoquastic spin systems at high temperature. Our framework is based on a rapidly mixing Markov chain for polymer models and a subcritical percolation process for sampling individual polymers. We apply our framework to obtain fast algorithms for approximating the partition function and sampling from the thermal distribution of (1) general stoquastic spin systems, (2) ferromagnetic Heisenberg models, and (3) antiferromagnetic Heisenberg models on bipartite graphs. For the Heisenberg models, we obtain an improved bound on the inverse temperature by using their respective cycle and loop representations.

quant-pharXiv:2608.19489•Aug 21, 2026
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.
Long-range quantum systems, in which the interactions decay as 1 / r α , are of increasing interest due to the variety of experimental setups in which they naturally appear. Motivated by this, we study fundamental properties of long-range spin systems in thermal equilibrium, focusing on the weak regime of α > D . Our main result is a proof of analyticity of their partition functions at high temperatures, which allows us to construct a classical algorithm with subexponential runtime exp  ( O ( log 2  ( N / ϵ ) ) ) that approximates the log-partition function to small additive error ϵ . As by-products, we establish the equivalence of ensembles and the Gaussianity of the density of states, which we verify numerically in both the weak and strong long-range regimes. This also yields constraints on the appearance of various classes of phase transitions, including thermal, dynamical, and excited-state ones. Our main technical contribution is the extension to the quantum long-range regime of the convergence criterion for cluster expansions of Kotecký and Preiss.
We establish a general framework for developing approximation algorithms for a class of counting problems. Our framework is based on the cluster expansion of the abstract polymer model formalism of Kotecký and Preiss. We apply our framework to obtain efficient algorithms for (1) approximating probability amplitudes of a class of quantum circuits close to the identity, (2) approximating expectation values of a class of quantum circuits with operators close to the identity, (3) approximating partition functions of a class of quantum spin systems at high temperature, and (4) approximating thermal expectation values of a class of quantum spin systems at high temperature with positive-semidefinite operators. Further, we obtain hardness of approximation results for approximating probability amplitudes of quantum circuits and partition functions of quantum spin systems. This establishes a computational complexity transition for these problems and shows that our algorithmic conditions are optimal under complexity-theoretic assumptions. Finally, we show that our algorithmic condition is almost optimal for expectation values and optimal for thermal expectation values in the sense of zero freeness. Published by the American Physical Society 2024
Zero-free based algorithm is a major technique for deterministic approximate counting. In Barvinok's original framework[Bar17], by calculating truncated Taylor expansions, a quasi-polynomial time algorithm was given for estimating zero-free partition functions. Patel and Regts[PR17] later gave a refinement of Barvinok's framework, which gave a polynomial-time algorithm for a class of zero-free graph polynomials that can be expressed as counting induced subgraphs in bounded-degree graphs. In this paper, we give a polynomial-time algorithm for estimating classical and quantum partition functions specified by local Hamiltonians with bounded maximum degree, assuming a zero-free property for the temperature. Consequently, when the inverse temperature is close enough to zero by a constant gap, we have polynomial-time approximation algorithm for all such partition functions. Our result is based on a new abstract framework that extends and generalizes the approach of Patel and Regts.
We establish a general framework for developing fast sampling and counting algorithms for stoquastic spin systems at high temperature. Our framework is based on a rapidly mixing Markov chain for polymer models and a subcritical percolation process for sampling individual polymers. We apply our framework to obtain fast algorithms for approximating the partition function and sampling from the thermal distribution of (1) general stoquastic spin systems, (2) ferromagnetic Heisenberg models, and (3) antiferromagnetic Heisenberg models on bipartite graphs. For the Heisenberg models, we obtain an improved bound on the inverse temperature by using their respective cycle and loop representations.