Remark 31 — Hardness with rational constant-bit entries and zero diagonal
OpenTFIMPhaseDiagram.Classical.Supplement.remark_31ising-modelp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityquantum-information
For fixed and , the full hardness conclusion of Theorem 21 persists when both restrictions are imposed simultaneously: has zero diagonal and every entry is rational with bit length at most one constant , independent of the dimension. Thus there are uniform and for which
remains -hard under the same strict spectral promise. Both consequences remain: randomized polynomial-time approximation implies and quantum polynomial-time approximation implies . 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