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

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Parameterized Algorithms to Compute Ising Partition Function

Hidefumi Hiraishi, Hiroshi IMAI, Yoichi Iwata, Bingkai Lin

Published Aug 31, 2018• 0 citations
Publisher

Abstract

Computing the partition function of the Ising model on a graph has been investigated from both sides of computer science and statistical physics, with producing fertile results of P cases, FPTAS/FPRAS cases, inapproximability and intractability. Recently, measurement-based quantum computing as well as quantum annealing open up another bridge between two fields by relating a tree tensor network representing a quantum graph state to a rank decomposition of the graph. This paper makes this bridge wider in both directions. An $O^*(2^{ \frac{\omega}{2} bw(G)})$-time algorithm is developed for the partition function on n-vertex graph G with branch decomposition of width bw(G), where O* ignores a polynomial factor in n and ω is the matrix multiplication parameter less than 2.37287. Related algorithms of $O^*(4^{rw(\tilde{G})})$ time for the tree tensor network are given which are of interest in quantum computation, given rank decomposition of a subdivided graph $\tilde{G}$ with width $rw(\tilde{G})$. These algorithms are parameter-exponential, i.e., O*(cp) for constant c and parameter p, and such an algorithm is not known for a more general case of computing the Tutte polynomial in terms of bw(G) (the current best time is O*(min{2n, bw(G)O(bw(G))})) with a negative result in terms of the clique-width, related to the rank-width, under ETH.

DOI
10.1587/transfun.e101.a.1398

Related papers

Quantum algorithm for an additive approximation of Ising partition functions

Akira Matsuo, Keisuke Fujii, Nobuyuki Imoto

We investigate quantum-computational complexity of calculating partition functions of Ising models. We construct a quantum algorithm for an additive approximation of Ising partition functions on square lattices. To this end, we utilize the overlap mapping developed by M. Van den Nest, W. D\"ur, and H. J. Briegel [Phys. Rev. Lett. 98, 117207 (2007)] and its interpretation through measurement-based quantum computation (MBQC). We specify an algorithmic domain, on which the proposed algorithm works, and an approximation scale, which determines the accuracy of the approximation. We show that the proposed algorithm performs a nontrivial task, which would be intractable on any classical computer, by showing that the problem that is solvable by the proposed quantum algorithm is BQP-complete. In the construction of the BQP-complete problem coupling strengths and magnetic fields take complex values. However, the Ising models that are of central interest in statistical physics and computer science consist of real coupling strengths and magnetic fields. Thus we extend the algorithmic domain of the proposed algorithm to such a real physical parameter region and calculate the approximation scale explicitly. We found that the overlap mapping and its MBQC interpretation improve the approximation scale exponentially compared to a straightforward constant-depth quantum algorithm. On the other hand, the proposed quantum algorithm also provides partial evidence that there exist no efficient classical algorithm for a multiplicative approximation of the Ising partition functions even on the square lattice. This result supports the observation that the proposed quantum algorithm also performs a nontrivial task in the physical parameter region.

arXiv:1405.2749•Physical Review A•Aug 5, 2014•17 citations

A Sharp Computational Phase Transition for the Partition Function of the Transverse-Field Ising Model

Alistair Sinclair, Thuy-Duong Vuong

We study the problem of approximating the partition function of the transverse-field Ising model (TFIM), a widely studied quantum many-body model with important applications in quantum simulation and quantum annealing. Despite its fundamental importance, the algorithmic landscape for computing the TFIM partition function has remained poorly understood beyond restricted parameter regimes. We provide a precise characterization of the temperature regimes in which efficient approximation is possible, establishing a sharp computational phase transition. Let J denote the symmetric interaction matrix and Δ(J) = λ_{max}(J)-λ_{min}(J) denote its spectral width. We show that, for all inverse temperatures β ∈ [0,1/Δ(J)], there exists an efficient classical randomized algorithm that approximates the partition function tr(e^{-β H}) to within an arbitrarily small multiplicative factor. To obtain this result, we apply the standard Trotter decomposition to map the quantum model to a classical spin system, and then leverage new techniques in Markov chain analysis to derive an efficient algorithm that samples from and computes the partition function of the resulting distribution. This temperature threshold is tight: for β > 1/Δ(J), we show that there exists interaction matrix J for which approximating the partition function, even within an exponential factor, is NP-hard and thus is unlikely to admit an efficient classical or quantum algorithm.

Leibniz international proceedings in informatics•Jan 1, 2026•0 citations

A computational phase diagram for the transverse field Ising model

Thuy-Duong Vuong

We study the transverse field Ising model, defined by the Hamiltonian $H =\frac{1}{2}\sum_{i, j\in [n]} J_{ij} Z_i Z_j +\sum_{i=1}^n h_i^z Z_i + η\sum_{i} X_i$ where $J $ is the symmetric interaction matrix, and $η$ is the transverse field strength. Let $Δ(J)=λ_{\max}(J)-λ_{\min}(J)$ be the spectral width of $J.$ When the inverse temperature $β\geq0$ satisfies $Δ(J)\cdot\frac{\tanh(βη)}η\leq1$, we give a randomized classical algorithm that approximates the partition function $Z(β)=\operatorname{Tr}(e^{-βH})$ to a given relative error $ε\in(0,1)$ in time polynomial in $n$, $β$, the model parameters, and $ε^{-1}$. When $ Δ(J) \cdot \frac{\tanh(βη)}η > 1 ,$ we show that approximating $ Z(β)$ within an $\exp(o(n))$-multiplicative factor is $\textbf{NP}$-hard, and thus unlikely to admit an efficient classical or quantum algorithms under standard complexity theoretic assumptions. Furthermore, in the regime $Δ(J)\cdot \frac{\tanh(βη)}η\leq 1,$ we provide an efficient randomized classical algorithm that approximates Pauli string observables of the Gibbs state $ ρ_β= \frac{e^{-βH}}{\operatorname{Tr}(e^{-βH})}$ within an arbitrarily small additive error. In the special case when the observable is also diagonal in the $X$-basis, i.e. $P \in \{I, X\}^{\otimes n}$, the algorithm further achieves arbitrarily small relative error.

quant-pharXiv:2610.02079•Oct 2, 2026•0 citations

The complexity of approximating the complex-valued Potts model

Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos

Abstract We study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q $$\geq$$ ≥ 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations.

Computational Complexity•Feb 2, 2022•5 citations

Computing Classical Partition Functions: From Onsager and Kaufman to Quantum Algorithms

Roberto Gargiulo, Matteo Rizzi, Robert Zeier

The computation of classical Ising partition functions, coming from statistical physics, is a natural generalization of binary optimization. This is a notoriously hard problem in general, which makes it an especially interesting task to consider in the search for practical quantum advantage in near term quantum computers. In this work we view classical Ising models (on certain graphs) as quantum imaginary time evolution, which is enabled by the use of the transfer matrix mapping. We study this mapping from two points of view: (1) following Onsager and Kaufman’s original solution of the 2D Ising model, which serves as a starting point, we consider more general models and the possibility of a similar Lie-theoretic solution; (2) we consider quantum algorithms for the computation of partition functions and thermal averages via transfer matrices, which can be implemented either with block encodings inside larger unitaries or by approximating the state trajectories with unitary operators.

•Jun 19, 2024•3 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$.

quant-pharXiv:2610.03893•Oct 6, 2026•0 citations
Computing the partition function of the Ising model on a graph has been investigated from both sides of computer science and statistical physics, with producing fertile results of P cases, FPTAS/FPRAS cases, inapproximability and intractability. Recently, measurement-based quantum computing as well as quantum annealing open up another bridge between two fields by relating a tree tensor network representing a quantum graph state to a rank decomposition of the graph. This paper makes this bridge wider in both directions. An O∗(2ω2bw(G))O^*(2^{ \frac{\omega}{2} bw(G)})O∗(22ω​bw(G))-time algorithm is developed for the partition function on n-vertex graph G with branch decomposition of width bw(G), where O* ignores a polynomial factor in n and ω is the matrix multiplication parameter less than 2.37287. Related algorithms of O∗(4rw(G~))O^*(4^{rw(\tilde{G})})O∗(4rw(G~)) time for the tree tensor network are given which are of interest in quantum computation, given rank decomposition of a subdivided graph G~\tilde{G}G~ with width rw(G~)rw(\tilde{G})rw(G~). These algorithms are parameter-exponential, i.e., O*(cp) for constant c and parameter p, and such an algorithm is not known for a more general case of computing the Tutte polynomial in terms of bw(G) (the current best time is O*(min{2n, bw(G)O(bw(G))})) with a negative result in terms of the clique-width, related to the rank-width, under ETH.
We investigate quantum-computational complexity of calculating partition functions of Ising models. We construct a quantum algorithm for an additive approximation of Ising partition functions on square lattices. To this end, we utilize the overlap mapping developed by M. Van den Nest, W. D\"ur, and H. J. Briegel [Phys. Rev. Lett. 98, 117207 (2007)] and its interpretation through measurement-based quantum computation (MBQC). We specify an algorithmic domain, on which the proposed algorithm works, and an approximation scale, which determines the accuracy of the approximation. We show that the proposed algorithm performs a nontrivial task, which would be intractable on any classical computer, by showing that the problem that is solvable by the proposed quantum algorithm is BQP-complete. In the construction of the BQP-complete problem coupling strengths and magnetic fields take complex values. However, the Ising models that are of central interest in statistical physics and computer science consist of real coupling strengths and magnetic fields. Thus we extend the algorithmic domain of the proposed algorithm to such a real physical parameter region and calculate the approximation scale explicitly. We found that the overlap mapping and its MBQC interpretation improve the approximation scale exponentially compared to a straightforward constant-depth quantum algorithm. On the other hand, the proposed quantum algorithm also provides partial evidence that there exist no efficient classical algorithm for a multiplicative approximation of the Ising partition functions even on the square lattice. This result supports the observation that the proposed quantum algorithm also performs a nontrivial task in the physical parameter region.
We study the problem of approximating the partition function of the transverse-field Ising model (TFIM), a widely studied quantum many-body model with important applications in quantum simulation and quantum annealing. Despite its fundamental importance, the algorithmic landscape for computing the TFIM partition function has remained poorly understood beyond restricted parameter regimes. We provide a precise characterization of the temperature regimes in which efficient approximation is possible, establishing a sharp computational phase transition. Let J denote the symmetric interaction matrix and Δ(J) = λ_{max}(J)-λ_{min}(J) denote its spectral width. We show that, for all inverse temperatures β ∈ [0,1/Δ(J)], there exists an efficient classical randomized algorithm that approximates the partition function tr(e^{-β H}) to within an arbitrarily small multiplicative factor. To obtain this result, we apply the standard Trotter decomposition to map the quantum model to a classical spin system, and then leverage new techniques in Markov chain analysis to derive an efficient algorithm that samples from and computes the partition function of the resulting distribution. This temperature threshold is tight: for β > 1/Δ(J), we show that there exists interaction matrix J for which approximating the partition function, even within an exponential factor, is NP-hard and thus is unlikely to admit an efficient classical or quantum algorithm.
We study the transverse field Ising model, defined by the Hamiltonian H=12∑i,j∈[n]JijZiZj+∑i=1nhizZi+η∑iXiH =\frac{1}{2}\sum_{i, j\in [n]} J_{ij} Z_i Z_j +\sum_{i=1}^n h_i^z Z_i + η\sum_{i} X_iH=21​∑i,j∈[n]​Jij​Zi​Zj​+∑i=1n​hiz​Zi​+η∑i​Xi​ where $J $ is the symmetric interaction matrix, and ηηη is the transverse field strength. Let Δ(J)=λmax⁡(J)−λmin⁡(J)Δ(J)=λ_{\max}(J)-λ_{\min}(J)Δ(J)=λmax​(J)−λmin​(J) be the spectral width of J.J.J. When the inverse temperature β≥0β\geq0β≥0 satisfies Δ(J)⋅tanh⁡(βη)η≤1Δ(J)\cdot\frac{\tanh(βη)}η\leq1Δ(J)⋅ηtanh(βη)​≤1, we give a randomized classical algorithm that approximates the partition function Z(β)=Tr⁡(e−βH)Z(β)=\operatorname{Tr}(e^{-βH})Z(β)=Tr(e−βH) to a given relative error ε∈(0,1)ε\in(0,1)ε∈(0,1) in time polynomial in nnn, βββ, the model parameters, and ε−1ε^{-1}ε−1. When $ Δ(J) \cdot \frac{\tanh(βη)}η > 1 ,$ we show that approximating $ Z(β)$ within an exp⁡(o(n))\exp(o(n))exp(o(n))-multiplicative factor is NP\textbf{NP}NP-hard, and thus unlikely to admit an efficient classical or quantum algorithms under standard complexity theoretic assumptions. Furthermore, in the regime Δ(J)⋅tanh⁡(βη)η≤1,Δ(J)\cdot \frac{\tanh(βη)}η\leq 1,Δ(J)⋅ηtanh(βη)​≤1, we provide an efficient randomized classical algorithm that approximates Pauli string observables of the Gibbs state $ ρ_β= \frac{e^{-βH}}{\operatorname{Tr}(e^{-βH})}$ within an arbitrarily small additive error. In the special case when the observable is also diagonal in the XXX-basis, i.e. P∈{I,X}⊗nP \in \{I, X\}^{\otimes n}P∈{I,X}⊗n, the algorithm further achieves arbitrarily small relative error.
Abstract We study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q ≥\geq≥ ≥ 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations.
The computation of classical Ising partition functions, coming from statistical physics, is a natural generalization of binary optimization. This is a notoriously hard problem in general, which makes it an especially interesting task to consider in the search for practical quantum advantage in near term quantum computers. In this work we view classical Ising models (on certain graphs) as quantum imaginary time evolution, which is enabled by the use of the transfer matrix mapping. We study this mapping from two points of view: (1) following Onsager and Kaufman’s original solution of the 2D Ising model, which serves as a starting point, we consider more general models and the possibility of a similar Lie-theoretic solution; (2) we consider quantum algorithms for the computation of partition functions and thermal averages via transfer matrices, which can be implemented either with block encodings inside larger unitaries or by approximating the state trajectories with unitary operators.
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ε−1)O(log⁡Δ)(N\varepsilon^{-1})^{\mathcal{O}(\logΔ)}(Nε−1)O(logΔ), where NNN is the system size, ε\varepsilonε the desired precision, and ΔΔΔ the interaction-graph degree. This becomes particularly severe in long-range systems, where Δ≡NΔ\equiv NΔ≡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 O~(N4ε−3)\tilde{\mathcal{O}}(N^4\varepsilon^{-3})O~(N4ε−3). For quantum partition functions at temperatures β≤βsampling≡O(1)β\leqβ_{\mathrm{sampling}}\equiv\mathcal{O}(1)β≤βsampling​≡O(1), this improves to O~(N3+1/Dε−3)\tilde{\mathcal{O}}(N^{3+1/D}\varepsilon^{-3})O~(N3+1/Dε−3), where DDD is the lattice dimension. The framework directly applies to long-range quantum systems with interactions ∝1/rα\propto1/r^α∝1/rα, including 222-local models with α>2Dα>2Dα>2D.