Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Remark 31 — Hardness with rational constant-bit entries and zero diagonal

Open
TFIMPhaseDiagram.Classical.Supplement.remark_31

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

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

For fixed η≠0\eta\ne0η=0 and b′>η/tanh⁡ηb'>\eta/\tanh\etab′>η/tanhη, the full hardness conclusion of Theorem 21 persists when both restrictions are imposed simultaneously: JJJ has zero diagonal and every entry is rational with bit length at most one constant B=B(η,b′)B=B(\eta,b')B=B(η,b′), independent of the dimension. Thus there are uniform c>0c>0c>0 and BBB for which

Z^=exp⁡(±cn)Z\widehat Z=\exp(\pm cn)ZZ=exp(±cn)Z

remains NP\mathsf{NP}NP-hard under the same strict spectral promise. Both consequences remain: randomized polynomial-time approximation implies NP=RP\mathsf{NP}=\mathsf{RP}NP=RP and quantum polynomial-time approximation implies NP⊆BQP\mathsf{NP}\subseteq\mathsf{BQP}NP⊆BQP. The source obtains these restrictions by choosing rational gadget parameters and subtracting the same scalar diagonal from both queried matrices; it preserves their partition-function ratio, rather than each individual partition function.

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
  • encoding: rational entries of parameter-dependent O(1) bit length and zero diagonal → one existential natural bound on sign, numerator and denominator bit lengths, together with every diagonal entry equal to zero; reason: the same fixed bound applies to every query and every dimension; canonical rational representation makes the condition precise
Preamble
import Definitions.Def_TFIMPhaseDiagram_Classical_Supplement_computation

set_option autoImplicit false
noncomputable section
Formal statement
namespace TFIMPhaseDiagram.Classical.Supplement

/-- Remark 31, p.22. Both zero diagonal and constant parameter-dependent
rational bit length hold simultaneously; neither restriction is dropped. -/
theorem remark_31 (η b' : ℝ) (hη : η ≠ 0) (hb : η / Real.tanh η < b') :
    ∃ (c : ℝ) (B : ℕ), 0 < c ∧
      ApproxNPHard η b' c (constantBitPromise B) ∧
      (RandomizedSpectralSolver η b' c (constantBitPromise B) → PvsNP.NP = RP) ∧
      (QuantumSpectralSolver η b' c (constantBitPromise B) → 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. 22; Remark 31

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