Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 21 — Exponential-factor spectral TFIM approximation hardness

Open
TFIMPhaseDiagram.Classical.Supplement.theorem_21

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

ising-modelp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityquantum-information

For each fixed nonzero real η\etaη and each b′>η/tanh⁡ηb'>\eta/\tanh\etab′>η/tanhη, there is c=c(η,b′)>0c=c(\eta,b')>0c=c(η,b′)>0 such that approximating SpectralTFIM(η,b′)\mathrm{SpectralTFIM}(\eta,b')SpectralTFIM(η,b′) within the multiplicative factor exp⁡(cn)\exp(cn)exp(cn) is NP\mathsf{NP}NP-hard. The input promise is precisely η/tanh⁡η<Δ(J)<b′\eta/\tanh\eta<\Delta(J)<b'η/tanhη<Δ(J)<b′, with arbitrary symmetric interaction matrix and no longitudinal field, and the target is

Z(J)=Tr⁡exp⁡ ⁣(12∑ijJijZiZj+η∑iXi).Z(J)=\operatorname{Tr}\exp\!\left(\tfrac12\sum_{ij}J_{ij}Z_iZ_j+\eta\sum_iX_i\right).Z(J)=Trexp(21​ij∑​Jij​Zi​Zj​+ηi∑​Xi​).

The hardness predicate requires actual polynomial-time two-query reductions from every binary NP\mathsf{NP}NP language, correct for every pair of estimates satisfying Z^=exp⁡(±cn)Z\widehat Z=\exp(\pm cn)ZZ=exp(±cn)Z. A polynomial-time randomized approximation with per-instance success strictly greater than 2/32/32/3 implies NP=RP\mathsf{NP}=\mathsf{RP}NP=RP; a polynomial-time quantum approximation with that success implies NP⊆BQP\mathsf{NP}\subseteq\mathsf{BQP}NP⊆BQP. 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

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me