Theorem 21 — Exponential-factor spectral TFIM approximation hardness
OpenTFIMPhaseDiagram.Classical.Supplement.theorem_21ising-modelp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityquantum-information
For each fixed nonzero real and each , there is such that approximating within the multiplicative factor is -hard. The input promise is precisely , with arbitrary symmetric interaction matrix and no longitudinal field, and the target is
The hardness predicate requires actual polynomial-time two-query reductions from every binary language, correct for every pair of estimates satisfying . A polynomial-time randomized approximation with per-instance success strictly greater than implies ; a polynomial-time quantum approximation with that success implies . The constant is chosen before the dimension or input matrix; both signs of the fixed nonzero field are retained.
Differences from the source:
- encoding: NP-hard approximation of the real symmetric-matrix promise problem → two nonadaptive polynomial-time reductions on encoded rational matrices and rational estimates; reason: the proof uses two partition queries; rational inputs already witness hardness of the full real domain as explained in Remark 31
- encoding: randomized and quantum polynomial-time approximation, NP=RP and NP contained in BQP → finite-bit randomized solvers, charged uniform finite-circuit solvers, and binary-language classes; reason: standard bit-complexity interpretation of the complexity-class consequences; all coin bits, generated gates and workspace are polynomially bounded
Preamble
import Definitions.Def_TFIMPhaseDiagram_Classical_Supplement_computation set_option autoImplicit false noncomputable section
Formal statement
namespace TFIMPhaseDiagram.Classical.Supplement
/-- Theorem 21, p.14. The fixed nonzero field may have either sign. Hardness
is witnessed on encoded rational instances of the real-input problem, with
uniform c and genuine two-query polynomial-time approximation reductions. -/
theorem theorem_21 (η b' : ℝ) (hη : η ≠ 0) (hb : η / Real.tanh η < b') :
∃ c : ℝ, 0 < c ∧ ApproxNPHard η b' c (fun _ => True) ∧
(RandomizedSpectralSolver η b' c (fun _ => True) → PvsNP.NP = RP) ∧
(QuantumSpectralSolver η b' c (fun _ => True) → PvsNP.NP ⊆ ShiBQP.BQP) := by sorry
end TFIMPhaseDiagram.Classical.Supplement
Source
Thuy-Duong (June) Vuong, A computational phase diagram for the transverse field Ising model, STOC 2027 submission #739 (October 2026); pinned source.pdf SHA256 02138c3ee0da2e11c9830e41e823dc009b55592cecb60f77602c2a404f2ecfc7, p. 14; proof pp. 19–22; Theorem 21