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:2601.13106 · Leibniz international proceedings in informatics

Product-State Approximation Algorithms for the Transverse Field Ising Model

Vincenzo Lipardi, David Mestel, Georgios Stamoulis

quant-phcs.DSSubmitted Jan 19, 2026• Announced Jan 20, 2026• 0 citations
arXivHTMLPDF

Abstract

We study classical polynomial-time approximation algorithms for the transverse-field Ising model (TFIM) Hamiltonian, allowing a mixture of ferromagnetic and anti-ferromagnetic interactions between pairs of qbits, alongside transverse field terms with arbitrary non-negative weights. Our main results are a series of approximation algorithms (all approximation ratios with respect to the true quantum optimum): (i) a simple maximum of two product state rounding algorithm achieving an approximation ratio $γ\approx 0.71$ , (ii) a strengthened rounding, inspired by the anticommutation property of the two $X_i, Z_iZ_j$ observables achieving ratio $γ\approx 0.7860$, and (iii) a further improvement by interpolation achieving ratio $γ\approx 0.8156$. We also give an explicit (purely ferromagnetic) TFIM instance on three qbits for which every product state achieves at most $169/180\approx 0.9389$ of the true optimum, yielding an upper bound for all algorithms producing product state approximations, even in the purely ferromagnetic case.

Related papers

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

Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut

Sevag Gharibian, Ojas Parekh

Approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-feromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal; we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively.

arXiv:1909.08846•Leibniz international proceedings in informatics•Jan 1, 2019•16 citations

Quantum annealing of the random-field Ising model by transverse ferromagnetic interactions

Sei Suzuki, Hidetoshi Nishimori, Masuo Suzuki

We introduce transverse ferromagnetic interactions, in addition to a simple transverse field, to accelerate the convergence of quantum annealing of the random-field Ising model. The conventional approach using only the transverse-field term is known to be plagued by slow convergence when the true ground state has strong ferromagnetic characteristics for the random-field Ising model. The transverse ferromagnetic interactions are shown to improve the performance significantly in such cases. This conclusion is drawn from the analyses of the energy eigenvalues of instantaneous stationary states as well as by the very fast algorithm of Bethe-type mean-field annealing adopted to quantum systems. The present study highlights the importance of a flexible choice of the type of quantum fluctuations to achieve the best possible performance in quantum annealing. The existence of such flexibility is an outstanding advantage of quantum annealing over simulated annealing.

arXiv:quant-ph/0702214•Physical Review E•May 16, 2007•36 citations

Stochastic series expansion method for quantum Ising models with arbitrary interactions

Anders W. Sandvik

A quantum Monte Carlo algorithm for the transverse Ising model with arbitrary short- or long-range interactions is presented. The algorithm is based on sampling the diagonal matrix elements of the power-series expansion of the density matrix (stochastic series expansion), and avoids the interaction summations necessary in conventional methods. In the case of long-range interactions, the scaling of the computation time with the system size N is therefore reduced from N2 to N ln(N). The method is tested on a one-dimensional ferromagnet in a transverse field, with interactions decaying as 1/r(2).

arXiv:cond-mat/0303597•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Nov 11, 2003•166 citations

Polynomial-Time Classical Simulation of Quantum Ferromagnets

Sergey B. Bravyi, David Gosset

We consider a family of quantum spin systems which includes, as special cases, the ferromagnetic XY model and ferromagnetic Ising model on any graph, with or without a transverse magnetic field. We prove that the partition function of any model in this family can be efficiently approximated to a given relative error ε using a classical randomized algorithm with runtime polynomial in ε^{-1}, system size, and inverse temperature. As a consequence, we obtain a polynomial time algorithm which approximates the free energy or ground energy to a given additive error. We first show how to approximate the partition function by the perfect matching sum of a finite graph with positive edge weights. Although the perfect matching sum is not known to be efficiently approximable in general, the graphs obtained by our method have a special structure which facilitates efficient approximation via a randomized algorithm due to Jerrum and Sinclair.

arXiv:1612.05602•Physical Review Letters•Sep 8, 2017•29 citations

Quantum cluster algorithm for frustrated Ising models in a transverse field

Sounak Biswas, Geet Rakala, Kedar Damle

Working within the stochastic series expansion framework, we introduce and characterize a plaquette-based quantum cluster algorithm for quantum Monte Carlo simulations of transverse field Ising models with frustrated Ising exchange interactions. As a demonstration of the capabilities of this algorithm, we show that a relatively small ferromagnetic next-nearest-neighbor coupling drives the transverse field Ising antiferromagnet on the triangular lattice from an antiferromagnetic three-sublattice ordered state at low temperature to a ferrimagnetic three-sublattice ordered state.

arXiv:1512.00931•Physical review. B./Physical review. B•Jun 1, 2016•14 citations
We study classical polynomial-time approximation algorithms for the transverse-field Ising model (TFIM) Hamiltonian, allowing a mixture of ferromagnetic and anti-ferromagnetic interactions between pairs of qbits, alongside transverse field terms with arbitrary non-negative weights.
Our main results are a series of approximation algorithms (all approximation ratios with respect to the true quantum optimum): (i) a simple maximum of two product state rounding algorithm achieving an approximation ratio γ≈0.71γ\approx 0.71γ≈0.71 , (ii) a strengthened rounding, inspired by the anticommutation property of the two Xi,ZiZjX_i, Z_iZ_jXi​,Zi​Zj​ observables achieving ratio γ≈0.7860γ\approx 0.7860γ≈0.7860, and (iii) a further improvement by interpolation achieving ratio γ≈0.8156γ\approx 0.8156γ≈0.8156. We also give an explicit (purely ferromagnetic) TFIM instance on three qbits for which every product state achieves at most 169/180≈0.9389169/180\approx 0.9389169/180≈0.9389 of the true optimum, yielding an upper bound for all algorithms producing product state approximations, even in the purely ferromagnetic case.
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.
Approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-feromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal; we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively.
We introduce transverse ferromagnetic interactions, in addition to a simple transverse field, to accelerate the convergence of quantum annealing of the random-field Ising model. The conventional approach using only the transverse-field term is known to be plagued by slow convergence when the true ground state has strong ferromagnetic characteristics for the random-field Ising model. The transverse ferromagnetic interactions are shown to improve the performance significantly in such cases. This conclusion is drawn from the analyses of the energy eigenvalues of instantaneous stationary states as well as by the very fast algorithm of Bethe-type mean-field annealing adopted to quantum systems. The present study highlights the importance of a flexible choice of the type of quantum fluctuations to achieve the best possible performance in quantum annealing. The existence of such flexibility is an outstanding advantage of quantum annealing over simulated annealing.
A quantum Monte Carlo algorithm for the transverse Ising model with arbitrary short- or long-range interactions is presented. The algorithm is based on sampling the diagonal matrix elements of the power-series expansion of the density matrix (stochastic series expansion), and avoids the interaction summations necessary in conventional methods. In the case of long-range interactions, the scaling of the computation time with the system size N is therefore reduced from N2 to N ln(N). The method is tested on a one-dimensional ferromagnet in a transverse field, with interactions decaying as 1/r(2).
We consider a family of quantum spin systems which includes, as special cases, the ferromagnetic XY model and ferromagnetic Ising model on any graph, with or without a transverse magnetic field. We prove that the partition function of any model in this family can be efficiently approximated to a given relative error ε using a classical randomized algorithm with runtime polynomial in ε^{-1}, system size, and inverse temperature. As a consequence, we obtain a polynomial time algorithm which approximates the free energy or ground energy to a given additive error. We first show how to approximate the partition function by the perfect matching sum of a finite graph with positive edge weights. Although the perfect matching sum is not known to be efficiently approximable in general, the graphs obtained by our method have a special structure which facilitates efficient approximation via a randomized algorithm due to Jerrum and Sinclair.
Working within the stochastic series expansion framework, we introduce and characterize a plaquette-based quantum cluster algorithm for quantum Monte Carlo simulations of transverse field Ising models with frustrated Ising exchange interactions. As a demonstration of the capabilities of this algorithm, we show that a relatively small ferromagnetic next-nearest-neighbor coupling drives the transverse field Ising antiferromagnet on the triangular lattice from an antiferromagnetic three-sublattice ordered state at low temperature to a ferrimagnetic three-sublattice ordered state.