Polynomial-Time Classical Simulation of Quantum Ferromagnets

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 $\epsilon$ using a classical randomized algorithm with runtime polynomial in ${\epsilon }^{-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.

Figure 1

Gadgets implementing the gates $X$, $f(t)$, $g(t)$ defined in Eq. (7). Edge weights take values 1 or $t$. To avoid clutter, weight-1 edges are left unlabeled.

Figure 2

A graph $\mathrm{\Gamma }$ satisfying $\text{PerfMatch}(\mathrm{\Gamma })=\mathrm{Tr}[G]$, where $G=f_2(d)X_3{g}_{13}(c)X_3{g}_{23}(b)g_{12}(a)$ is a circuit with $J=6$ gates and $n=3$ qubits.