Product-State Approximation Algorithms for the Transverse Field Ising Model

We study classical polynomial-time approximation algorithms for the transverse-field Ising model (TFIM) Hamiltonian, allowing a mixture of ferromagnetic and anti-ferromagnetic interactions between pairs of qbits, alongside transverse field terms with arbitrary non-negative weights. Our main results are a series of approximation algorithms (all approximation ratios with respect to the true quantum optimum): (i) a simple maximum of two product state rounding algorithm achieving an approximation ratio γapprox 0.71 , (ii) a strengthened rounding, inspired by the anticommutation property of the two X_i, Z_iZj observables achieving ratio γapprox 0.7860, and (iii) a further improvement by interpolation achieving ratio γapprox 0.8156. We also give an explicit (purely ferromagnetic) TFIM instance on three qbits for which every product state achieves at most 169/180approx 0.9389 of the true optimum, yielding an upper bound for all algorithms producing product state approximations, even in the purely ferromagnetic case.