arXiv:2004.11568 · Journal of Mathematical Physics

Efficient algorithms for approximating quantum partition functions

Ryan L. Mann, Tyler Helmuth

Published Feb 1, 2021• 17 citations

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.

DOI: 10.1063/5.0013689

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.21140Physical Review AJan 30, 20260 citations

Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature

Tyler Helmuth, Ryan L. Mann

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:2201.06533QuantumOct 25, 20236 citations

Efficient Quantum Monte Carlo through Cluster Expansions

Jorge Sánchez-Segovia, Álvaro M. Alhambra

quant-pharXiv:2610.03893Oct 6, 20260 citations

Polynomial-Time Approximation of Zero-Free Partition Functions

Penghui Yao, Yitong Yin, Xinyuan Zhang

arXiv:2201.12772Leibniz international proceedings in informaticsJan 1, 20220 citations

Algorithmic Cluster Expansions for Quantum Problems

Ryan L. Mann, Romy Minko

arXiv:2306.08974PRX QuantumJan 16, 20249 citations

Fast mixing of all-to-all quantum systems at high temperatures

Thiago Bergamaschi

quant-pharXiv:2606.26090Jun 25, 20260 citations

arXiv:2004.11568 · Journal of Mathematical Physics

Efficient algorithms for approximating quantum partition functions

Ryan L. Mann, Tyler Helmuth

Published Feb 1, 2021• 17 citations

arXiv HTML PDF

Abstract

DOI: 10.1063/5.0013689

Related papers

Efficient Algorithms for Weakly-Interacting Quantum Spin Systems

Ryan L. Mann, Gabriel Waite

quant-pharXiv:2601.21140Physical Review AJan 30, 20260 citations

Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature

Tyler Helmuth, Ryan L. Mann

arXiv:2201.06533QuantumOct 25, 20236 citations

Efficient Quantum Monte Carlo through Cluster Expansions

Jorge Sánchez-Segovia, Álvaro M. Alhambra

The sign problem remains a major obstacle to extending the success of Monte Carlo methods to generic quantum many-body systems. A powerful alternative relies on cluster expansions, which provide convergent representations of free energies and related quantities, with applications ranging from tensor network contractions to quantum dynamics and circuits. Within their convergence regime, these expansions often yield deterministic polynomial-time algorithms. However, such methods require exhaustive enumeration of connected clusters, leading to a computational overhead of $(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}$ , where $N$ is the system size, $\varepsilon$ the desired precision, and $Δ$ the interaction-graph degree. This becomes particularly severe in long-range systems, where $Δ\equiv N$ , resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime $\tilde{\mathcal{O}}(N^4\varepsilon^{-3})$ . For quantum partition functions at temperatures $β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)$ , this improves to $\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})$ , where $D$ is the lattice dimension. The framework directly applies to long-range quantum systems with interactions $\propto1/r^α$ , including $2$ -local models with $α>2D$ .The sign problem remains a major obstacle to extending the success of Monte Carlo methods to generic quantum many-body systems. A powerful alternative relies on cluster expansions, which provide convergent representations of free energies and related quantities, with applications ranging from tensor network contractions to quantum dynamics and circuits. Within their convergence regime, these expansions often yield deterministic polynomial-time algorithms. However, such methods require exhaustive enumeration of connected clusters, leading to a computational overhead of $(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}$, where $N$ is the system size, $\varepsilon$ the desired precision, and $Δ$ the interaction-graph degree. This becomes particularly severe in long-range systems, where $Δ\equiv N$, resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime $\tilde{\mathcal{O}}(N^4\varepsilon^{-3})$. For quantum partition functions at temperatures $β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)$, this improves to $\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})$, where $D$ is the lattice dimension. The framework directly applies to long-range quantum systems with interactions $\propto1/r^α$, including $2$-local models with $α>2D$.

quant-pharXiv:2610.03893Oct 6, 20260 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.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.12772Leibniz international proceedings in informaticsJan 1, 20220 citations

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 2024We 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.08974PRX QuantumJan 16, 20249 citations

Fast mixing of all-to-all quantum systems at high temperatures

Thiago Bergamaschi

It is shown that arbitrary quantum $k$ -local Hamiltonians with bounded strength interactions admit a quantum Gibbs sampler [CKG23] with a system-size independent spectral gap, at sufficiently high temperatures. As a consequence, such systems admit fully-polynomial time quantum approximation algorithms for partition functions and global expectation values.It is shown that arbitrary quantum $k$-local Hamiltonians with bounded strength interactions admit a quantum Gibbs sampler [CKG23] with a system-size independent spectral gap, at sufficiently high temperatures. As a consequence, such systems admit fully-polynomial time quantum approximation algorithms for partition functions and global expectation values.

quant-pharXiv:2606.26090Jun 25, 20260 citations

(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}

, where

N

is the system size,

\varepsilon

the desired precision, and

Δ

the interaction-graph degree. This becomes particularly severe in long-range systems, where

Δ\equiv N

, resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime

\tilde{\mathcal{O}}(N^4\varepsilon^{-3})

. For quantum partition functions at temperatures

β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)

, this improves to

\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})

, where

D

is the lattice dimension. The framework directly applies to long-range quantum systems with interactions

\propto1/r^α

, including

2

-local models with

α>2D

It is shown that arbitrary quantum

k

-local Hamiltonians with bounded strength interactions admit a quantum Gibbs sampler [CKG23] with a system-size independent spectral gap, at sufficiently high temperatures. As a consequence, such systems admit fully-polynomial time quantum approximation algorithms for partition functions and global expectation values.