2026-08-21T16:28:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27457 2026-08-21T14:42:40Z ddc:004 open_access

Product-State Approximation Algorithms for the Transverse Field Ising Model Lipardi, Vincenzo Mestel, David Stamoulis, Georgios Ising model Hamiltonian Complexity Approximation Algorithms Semidefinite Programming We study classical polynomial-time approximation algorithms for the transverse field Ising model (TFIM), allowing a mixture of ferromagnetic and antiferromagnetic interactions between pairs of qubits, alongside transverse field terms with arbitrary non-negative weights. In this work, we first prove a second-order conic inequality based on the anticommutation property of the two competing terms (Ising Z_i Z_j vs. field X_i terms), and we use this inequality to strengthen the basic SDP relaxation of the problem. By producing two competing rounded product state solutions and taking the better of the two we achieve an approximation ratio γ≈ 0.7860. A further improvement by non-uniform interpolation achieves a ratio γ ≈ 0.82197. Finally, we give an explicit purely antiferromagnetic TFIM instance on three qubits for which every product state achieves at most 169/180≈ 0.9389 of the true optimum, yielding an upper bound for all algorithms producing product state approximations, even in the purely antiferromagnetic case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vincenzo Lipardi and David Mestel and Georgios Stamoulis 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.75 urn:nbn:de:0030-drops-274574 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.75 eng https://creativecommons.org/licenses/by/4.0/legalcode