A computational phase diagram for the transverse field Ising model

Abstract

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+\eta {\sum }_i{X}_i$ where $J$ is the symmetric interaction matrix, and $\eta$ is the transverse field strength. Let $\Delta (J)={\lambda }_{\max }(J)-{\lambda }_{\min }(J)$ be the spectral width of $J.$ When the inverse temperature $\beta \ge 0$ satisfies $\Delta (J)\cdot \frac{\tanh (\beta \eta )}{\eta }\le 1$, we give a randomized classical algorithm that approximates the partition function $Z(\beta )=\mathrm{Tr}(e^{-\beta H})$ to a given relative error $\epsilon \in (0,1)$ in time polynomial in $n$, $\beta$, the model parameters, and ${\epsilon }^{-1}$. When $\Delta (J)\cdot \frac{\tanh (\beta \eta )}{\eta }>1,$ we show that approximating $Z(\beta )$ within an $\exp (o(n))$-multiplicative factor is $\text{NP}$-hard, and thus unlikely to admit an efficient classical or quantum algorithms under standard complexity theoretic assumptions. Furthermore, in the regime $\Delta (J)\cdot \frac{\tanh (\beta \eta )}{\eta }\le 1,$ we provide an efficient randomized classical algorithm that approximates Pauli string observables of the Gibbs state ${\rho }_{\beta }=\frac{e^{-\beta H}}{\mathrm{Tr}(e^{-\beta 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.