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=21∑i,j∈[n]JijZiZj+∑i=1nhizZi+η∑iXi 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
β≥0 satisfies
Δ(J)⋅ηtanh(βη)≤1, we give a randomized classical algorithm that approximates the partition function
Z(β)=Tr(e−βH) to a given relative error
ε∈(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
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, 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∈{I,X}⊗n, the algorithm further achieves arbitrarily small relative error.
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∗(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~)) time for the tree tensor network are given which are of interest in quantum computation, given rank decomposition of a subdivided graph
G~ with width
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 present a quasi-polynomial time classical algorithm that estimates the partition function of quantum many-body systems at temperatures above the thermal phase transition point. It is known that in the worst case, the same problem is NP-hard below this point. Together with our work, this shows that the transition in the phase of a quantum system is also accompanied by a transition in the hardness of approximation. We also show that in a system of n particles above the phase transition point, the correlation between two observables whose distance is at least Ω(logn) decays exponentially. We can improve the factor of logn to a constant when the Hamiltonian has commuting terms or is on a 1D chain. The key to our results is a characterization of the phase transition and the critical behavior of the system in terms of the complex zeros of the partition function. Our work extends a seminal work of Dobrushin and Shlosman on the equivalence between the decay of correlations and the analyticity of the free energy in classical spin models. On the algorithmic side, our result extends the scope of a recent approach due to Barvinok for solving classical counting problems to quantum many-body systems.
Abstract We present a quantum Monte Carlo algorithm for the simulation of general quantum and classical many-body models within a single unifying framework. The algorithm builds on a power series expansion of the quantum partition function in its off-diagonal terms and is both parameter-free and Trotter error-free. In our approach, the quantum dimension consists of products of elements of a permutation group. As such, it allows for the study of a very wide variety of models on an equal footing. To demonstrate the utility of our technique, we use it to clarify the emergence of the sign problem in the simulations of non-stoquastic physical models. We showcase the flexibility of our algorithm and the advantages it offers over existing state-of-the-art by simulating transverse-field Ising model Hamiltonians and comparing the performance of our technique against that of the stochastic series expansion algorithm. We also study a transverse-field Ising model augmented with randomly chosen two-body transverse-field interactions.
The quantum dynamics of many-qubit systems is an outstanding problem that has recently driven significant advances in both numerical methods and programmable quantum processing units. In this work, we employ a comprehensive toolbox of state-of-the-art numerical approaches to classically simulate the dynamics of the two-dimensional transverse field Ising model. Our methods include three different tensor network techniques -- matrix product states, tree-tensor networks, and two-dimensional tensor-networks under the belief propagation approximation -- as well as time-dependent variational Monte Carlo with Neural Quantum States. We focus on two paradigmatic dynamical protocols: (i) quantum annealing through a critical point and (ii) post-quench dynamics. Our extensive results show the quantitative predictions of various state-of-the-art numerical methods providing a benchmark for future numerical investigations and experimental studies with the aim to push the limitations on classical and QPUs. In particular, our work connects classical simulability to different regimes associated with quantum dynamics in Rydberg arrays - namely, quasi-adiabatic dynamics, the Kibble-Zurek mechanism, and quantum quenches.
The discovery of dynamical quantum phase transitions (DQPTs) has fundamentally challenged the traditional view that phase transitions only occur in thermal equilibrium. Experimental platforms and 1D numerical methods, like matrix product states (MPS), have made great progress. However, exploring true 2D DQPTs remains difficult due to finite-size limitations and the geometric biases of quasi-1D cylinder mappings. Here, we bypass these limitations by deploying a tree tensor network (TTN) approach. This allows us to directly compute the quench dynamics of the transverse-field Ising model (TFIM) on an open 2D square lattice. Because the TTN architecture naturally mirrors 2D lattice connectivity, we can extract the global Loschmidt echo. Our simulations reveal that while deep quenches yield standard DQPTs, quenching within the ferromagnetic phase produces an anomalous dynamical response. In this regime, the rate function exhibits sharp non-analytic peaks even as the macroscopic order parameter maintains its initial sign. This decoupled behavior strongly indicates that local spin excitations drive 2D DQPTs, rather than the macroscopic domain-wall motions seen in 1D chains. These results provide a quantitative numerical baseline for understanding non-equilibrium quantum matter in higher dimensions.