2026-08-25T11:01:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27298 2026-08-25T07:42:36Z ddc:004 open_access

A Sharp Computational Phase Transition for the Partition Function of the Transverse-Field Ising Model Sinclair, Alistair Vuong, Thuy-Duong Computational phase transition partition function transverse-field Ising sampling counting 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alistair Sinclair and Thuy-Duong Vuong 2026 Is Part Of LIPIcs, Volume 389, 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2026.1 urn:nbn:de:0030-drops-272986 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2026.1 eng https://creativecommons.org/licenses/by/4.0/legalcode