Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Uniform finite circuits, bit computation, spectral reductions and conditional marginals

Definition
TFIMPhaseDiagram_Classical_Supplement_computation

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

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

Binary words encode integers by a self-delimiting length and binary payload, rationals by sign, numerator and denominator, and dense symmetric-matrix inputs in row order. Classical bit computation uses actual finite multistack machines with step-count witnesses from Mathlib, on the same binary languages as the published NP\mathsf{NP}NP and BQP\mathsf{BQP}BQP definitions. The local RP\mathsf{RP}RP has polynomially many unbiased random bits, a polynomial-time machine, no false acceptance and acceptance probability at least 2/32/32/3 on members.

A finite quantum program is a list of addressed H,T,CNOTH,T,\mathrm{CNOT}H,T,CNOT gates. Execution multiplies the actual embedded gate matrices in execution order on the zero basis state, then traces out workspace qubits. All gates, output qubits and ancillas are charged, separately from classical generation; invalid decoded instructions are identity. For the real-arithmetic formulation, the published charged RAM prints such a circuit in its natural registers. The averaged state is an entrywise integral of its actual reduced density matrices, with integrability required by the preparation predicate. For the bit formulation, an actual multistack machine prints a self-delimiting circuit code. Computational-basis measurement and rational output decoding define the approximation success probability.

The spectral promise is η/tanh⁡η<Δ(J)<b′\eta/\tanh\eta<\Delta(J)<b'η/tanhη<Δ(J)<b′ for symmetric JJJ, n≥1n\ge1n≥1, with target Tr⁡exp⁡(12∑ijJijZiZj+η∑iXi)\operatorname{Tr}\exp(\tfrac12\sum_{ij}J_{ij}Z_iZ_j+\eta\sum_iX_i)Trexp(21​∑ij​Jij​Zi​Zj​+η∑i​Xi​). A hardness witness supplies two polynomial-time query printers and a polynomial-time decision postprocessor for every binary NP\mathsf{NP}NP language, correct on every pair of accurate answers. Rational inputs witness hardness of the real problem; the constant-bit restriction also requires zero diagonal.

For Theorem 34, partial assignments are functions to optional bits, where absence means an unassigned spin. Their diagonal projectors equal the source products, including the identity for the empty assignment. The bundle uses the actual half exponential U=exp⁡((H+A)/2)U=\exp((H+A)/2)U=exp((H+A)/2) and

q(ℓ,r)=Re⁡Tr⁡(PℓUPrU)Tr⁡(U2).q(\ell,r)=\operatorname{Re}\frac{\operatorname{Tr}(P_\ell U P_r U)}{\operatorname{Tr}(U^2)}.q(ℓ,r)=ReTr(U2)Tr(Pℓ​UPr​U)​.

A marginal estimator is an executed finite-bit machine on every partial pair and every padded random tape, with nonnegative estimates, the exact source relative accuracy e2/(256n)e^2/(256n)e2/(256n) and failure e/(16⋅4n)e/(16\cdot4^n)e/(16⋅4n). Circuit generation takes unary resource bounds so its polynomial time is charged in those bounds. Arbitrary real target accuracies are passed through a logarithmic binary precision index without restricting their domain. The source's even Trotter mesh is defined exactly, using 2⌈500max⁡{nc2/ϵ,(nc/ϵ)3/2}⌉2\lceil500\max\{nc^2/\epsilon,(nc/\epsilon)^{3/2}\}\rceil2⌈500max{nc2/ϵ,(nc/ϵ)3/2}⌉.

Definition code
import Definitions.Def_TFIMPhaseDiagram_Classical_ram
import Definitions.Def_TFIMPhaseDiagram_Classical_traceSetup
import Definitions.Def_PvsNP
import Definitions.Def_ShiBQP_Core

set_option autoImplicit false
open MeasureTheory
open scoped BigOperators
noncomputable section

namespace TFIMPhaseDiagram.Classical.Supplement
attribute [local instance] Classical.propDecidable
abbrev Word := List Bool

/-- Self-delimiting binary integers: unary length, separator, binary payload. -/
def natCode (n : ℕ) : Word := List.replicate (Nat.bits n).length true ++ [false] ++ Nat.bits n
def readNat (w : Word) : ℕ × Word :=
  let k := (w.takeWhile id).length
  ((((w.drop (k+1)).take k).foldr (fun b a => (if b then 1 else 0)+2*a) 0), w.drop (2*k+1))
def readNats : ℕ → Word → List ℕ
  | 0, _ => []
  | k+1, w => if w = [] then [] else (readNat w).1 :: readNats k (readNat w).2

def ratCode (q : ℚ) : Word := (decide (q < 0)) :: (natCode q.num.natAbs ++ natCode q.den)
def readRat (w : Word) : ℚ × Word :=
  let p := readNat (w.drop 1)
  let q := readNat p.2
  ((if w.headD false then -1 else 1) * (p.1 : ℚ) / max 1 q.1, q.2)
def estimate (w : Word) : ℝ := (readRat w).1

def pairCode (p : Word × Word) : Word :=
  List.replicate p.1.length true ++ [false] ++ p.1 ++ p.2

/-- Runtime is supplied by an actual finite multistack machine, not by a free cost label. -/
abbrev BitMachine (f : Word → Word) :=
  Turing.TM2ComputableInTime (id : Word → Word) (id : Word → Word) f

def PolyTimeWords (f : Word → Word) : Prop := PvsNP.PolyTimeComputable f

/-- Raw Clifford+T circuit code: (0,i,_) is H_i, (1,i,_) is T_i,
(2,i,j) is CNOT(i,j). Invalid addresses/tags act as identity. This total decoder
never produces a nonunitary gate or postselection. -/
structure FiniteCircuit where
  ancillas : ℕ
  gates : List (ℕ × ℕ × ℕ)

def triples : List ℕ → List (ℕ × ℕ × ℕ)
  | a :: i :: j :: rest => (a,i,j) :: triples rest
  | _ => []
def circuitDecode (w : Word) : FiniteCircuit :=
  let p := readNat w
  ⟨p.1, triples (readNats p.2.length p.2)⟩
def circuitCode (c : FiniteCircuit) : Word :=
  natCode c.ancillas ++ c.gates.flatMap (fun g => natCode g.1 ++ natCode g.2.1 ++ natCode g.2.2)

def singleGate {m : ℕ} (U : Matrix Bool Bool ℂ) (i : Fin m) : QMat m :=
  fun y z => if ∀ j, j ≠ i → y j = z j then U (y i) (z i) else 0

def gateMatrix (m : ℕ) (g : ℕ × ℕ × ℕ) : QMat m :=
  if hi : g.2.1 < m then
    let i : Fin m := ⟨g.2.1,hi⟩
    if g.1 = 0 then singleGate QAlgorithms.hadamard i
    else if g.1 = 1 then singleGate QAlgorithms.gateT i
    else if hj : g.2.2 < m then
      let j : Fin m := ⟨g.2.2,hj⟩
      if g.1 = 2 ∧ i ≠ j then
        fun y z => if y = Function.update z j (xor (z j) (z i)) then 1 else 0
      else 1
    else 1
  else 1

def circuitUnitary (n : ℕ) (c : FiniteCircuit) : QMat (n+c.ancillas) :=
  (c.gates.map (gateMatrix (n+c.ancillas))).reverse.prod

def circuitAmplitude (n : ℕ) (c : FiniteCircuit) (z : Bits (n+c.ancillas)) : ℂ :=
  circuitUnitary n c z (fun _ => false)

/-- Actual execution on |0...0>, followed by tracing out all workspace qubits. -/
def circuitDensity (n : ℕ) (c : FiniteCircuit) : QMat n :=
  fun x y => ∑ a : Bits c.ancillas,
    circuitAmplitude n c (Fin.append x a) * star (circuitAmplitude n c (Fin.append y a))
def circuitCost (n : ℕ) (c : FiniteCircuit) : ℕ := n+c.ancillas+c.gates.length

def bitList {n : ℕ} (x : Bits n) : Word := (List.finRange n).map x
/-- A deterministic classical compiler prints a finite circuit; its output register
is measured in the computational basis, then decoded as a rational number. -/
def quantumEstimateProbability (code : Word) (A : ℝ → Prop) : ℝ :=
  let p := readNat code
  let n := p.1
  let c := circuitDecode p.2
  ∑ x : Bits n, if A (estimate (bitList x)) then (circuitDensity n c x x).re else 0

/-- Uniform one-sided randomized polynomial time over the same languages as PvsNP.NP. -/
def RP : Set (Language Bool) :=
  {L | ∃ (f : Word → Word) (p : Polynomial ℕ), PolyTimeWords f ∧ ∀ w : Word,
    let R := p.eval w.length
    (w ∈ L → (2:ℝ)/3 ≤ (∑ ω : Bits R,
      if (f (pairCode (w,bitList ω))).headD false then (1:ℝ) else 0) / 2^R) ∧
    (w ∉ L → ∀ ω : Bits R, (f (pairCode (w,bitList ω))).headD false = false)}

structure RationalInstance where
  n : ℕ
  J : Matrix (Fin n) (Fin n) ℚ

def instanceCode (I : RationalInstance) : Word :=
  natCode I.n ++ (List.finRange I.n).flatMap (fun i =>
    (List.finRange I.n).flatMap (fun j => ratCode (I.J i j)))
def realJ (I : RationalInstance) : Matrix (Fin I.n) (Fin I.n) ℝ := fun i j => I.J i j

def spectralPromise (η b' : ℝ) (I : RationalInstance) : Prop :=
  0 < I.n ∧ (realJ I).IsSymm ∧ η / Real.tanh η < spectralWidth (realJ I) ∧
    spectralWidth (realJ I) < b'
def spectralTarget (η : ℝ) (I : RationalInstance) : ℂ :=
  partition (realJ I) (fun _ => 0) (fun _ => η)
def goodSpectralAnswer (η c : ℝ) (I : RationalInstance) (w : Word) : Prop :=
  ExpApprox (c*I.n) (estimate w) (spectralTarget η I)
def rationalBits (q : ℚ) : ℕ := (Nat.bits q.num.natAbs).length + (Nat.bits q.den).length + 1
def constantBitPromise (B : ℕ) (I : RationalInstance) : Prop :=
  (∀ i, I.J i i = 0) ∧ ∀ i j, rationalBits (I.J i j) ≤ B

/-- Concrete nonadaptive two-query polynomial-time approximation reduction.
The query printers and decision postprocessor are genuine bit machines. Every
accurate pair of replies must decide the input, not just a favorable oracle. -/
def ApproxNPHard (η b' c : ℝ) (restriction : RationalInstance → Prop) : Prop :=
  ∀ L : Language Bool, L ∈ PvsNP.NP →
    ∃ (Q₁ Q₂ : Word → RationalInstance) (D : Word → Word),
      Nonempty (Turing.TM2ComputableInPolyTime (id : Word → Word) instanceCode Q₁) ∧
      Nonempty (Turing.TM2ComputableInPolyTime (id : Word → Word) instanceCode Q₂) ∧
      PolyTimeWords D ∧
      (∀ w, spectralPromise η b' (Q₁ w) ∧ restriction (Q₁ w) ∧
        spectralPromise η b' (Q₂ w) ∧ restriction (Q₂ w)) ∧
      ∀ w a₁ a₂, goodSpectralAnswer η c (Q₁ w) a₁ → goodSpectralAnswer η c (Q₂ w) a₂ →
        (w ∈ L ↔ (D (pairCode (w,pairCode (a₁,a₂)))).headD false = true)

def RandomizedSpectralSolver (η b' c : ℝ) (restriction : RationalInstance → Prop) : Prop :=
  ∃ (f : Word → Word) (p : Polynomial ℕ), PolyTimeWords f ∧
    ∀ I, spectralPromise η b' I → restriction I →
      let R := p.eval (instanceCode I).length
      (2:ℝ)/3 < (∑ ω : Bits R,
        if goodSpectralAnswer η c I (f (pairCode (instanceCode I,bitList ω))) then (1:ℝ) else 0) / 2^R

def quantumWordCost (code : Word) : ℕ :=
  let p := readNat code
  p.1 + (circuitDecode p.2).ancillas + (circuitDecode p.2).gates.length

def QuantumSpectralSolver (η b' c : ℝ) (restriction : RationalInstance → Prop) : Prop :=
  ∃ (f : Word → Word) (C d : ℕ), PolyTimeWords f ∧
    (∀ w, quantumWordCost (f w) ≤ C*(1+w.length)^d) ∧
    ∀ I, spectralPromise η b' I → restriction I →
      (2:ℝ)/3 < quantumEstimateProbability (f (instanceCode I))
        (fun a => ExpApprox (c*I.n) a (spectralTarget η I))

/-- Ancilla and gate counts are charged as well as classical generation. The real
compiler is the published finite RAM, whose natural registers contain a circuit. -/
def ramCircuit (P : RAMProgram) (input : List ℝ) (budget : ℕ)
    (ω : MatMulTimeLP.Tape) : FiniteCircuit :=
  let s := ramState P input ω budget
  ⟨s.N 0, (List.range (s.N 1)).map (fun j => (s.N (3*j+2),s.N (3*j+3),s.N (3*j+4)))⟩
def quantumInput {n : ℕ} (J : Matrix (Fin n) (Fin n) ℝ) (h η : Fin n → ℝ) (e : ℝ) : List ℝ :=
  [(n:ℝ),e] ++ MatMulTimeLP.matToList J ++ MatMulTimeLP.vecToList h ++ MatMulTimeLP.vecToList η

def averagedRAMState (n : ℕ) (P : RAMProgram) (input : List ℝ) (budget : ℕ) : QMat n :=
  fun x y => ∫ ω, circuitDensity n (ramCircuit P input budget ω) x y ∂MatMulTimeLP.tapeLaw

def PreparesReal {n : ℕ} (P : RAMProgram) (input : List ℝ) (B : ℕ) (ρ : QMat n) (e : ℝ) : Prop :=
  Admissible P ∧ HaltsWithin P input B ∧
  (∀ ω, circuitCost n (ramCircuit P input B ω) ≤ B) ∧
  (∀ x y, Integrable (fun ω => circuitDensity n (ramCircuit P input B ω) x y) MatMulTimeLP.tapeLaw) ∧
  schattenOne (averagedRAMState n P input B - ρ) ≤ e

def prepBudget {n : ℕ} (C d : ℕ) (J : Matrix (Fin n) (Fin n) ℝ)
    (h η : Fin n → ℝ) (e : ℝ) : ℕ :=
  C * ⌈(1+n+maxEntry J+maxField h+maxField η+e⁻¹)^d⌉₊

def precisionBits (e : ℝ) : ℕ := ⌈Real.log (1/e) / Real.log 2⌉₊+1

def rationalInput {n : ℕ} (J : Matrix (Fin n) (Fin n) ℚ) (h η : Fin n → ℚ) (k : ℕ) : Word :=
  natCode n ++ natCode k ++ (List.finRange n).flatMap (fun i =>
    (List.finRange n).flatMap (fun j => ratCode (J i j))) ++
    (List.finRange n).flatMap (fun i => ratCode (h i) ++ ratCode (η i))
def inputBitsBound {n : ℕ} (b : ℕ) (J : Matrix (Fin n) (Fin n) ℚ) (h η : Fin n → ℚ) : Prop :=
  (∀ i j, rationalBits (J i j) ≤ b) ∧ (∀ i, rationalBits (h i) ≤ b ∧ rationalBits (η i) ≤ b)

/-- Empty spins are genuinely unassigned; no conditioning on zero mass is assumed. -/
abbrev PartialSpins (n : ℕ) := Fin n → Option Bool

def partialProjector {n : ℕ} (a : PartialSpins n) : QMat n :=
  Matrix.diagonal (fun x => if ∀ i, ∀ v, a i = some v → x i = v then 1 else 0)
def gibbsOf {n : ℕ} (H : QMat n) : QMat n :=
  (Matrix.trace (matrixExp H))⁻¹ • matrixExp H
def halfExponential {n : ℕ} (H R : QMat n) : QMat n := matrixExp ((1/2:ℂ) • (H+R))
def marginal {n : ℕ} (H R : QMat n) (l r : PartialSpins n) : ℝ :=
  let U := halfExponential H R
  (Matrix.trace (partialProjector l * U * partialProjector r * U) / Matrix.trace (U*U)).re

def partialCode {n : ℕ} (a : PartialSpins n) : Word :=
  (List.finRange n).flatMap (fun i =>
    match a i with
    | none => [false,false]
    | some false => [true,false]
    | some true => [true,true])
def estimatorInput {n : ℕ} (l r : PartialSpins n) (ω : Word) : Word :=
  natCode n ++ partialCode l ++ partialCode r ++ ω

/-- The finite-precision estimator promised in footnote 14. Every random tape
and every pair of partial configurations is executed by the supplied bit machine. -/
def MarginalEstimator {n : ℕ} (f : Word → Word) (M : BitMachine f) (T R : ℕ)
    (H A : QMat n) (e : ℝ) : Prop :=
  R ≤ T ∧ (∀ l r : PartialSpins n, ∀ ω : Bits R,
    M.time (estimatorInput l r (bitList ω)).length ≤ T ∧
    0 ≤ estimate (f (estimatorInput l r (bitList ω)))) ∧
  ∀ l r : PartialSpins n,
    1-e/(16*4^n) ≤ (∑ ω : Bits R,
      if ExpApprox (e^2/(256*n)) (estimate (f (estimatorInput l r (bitList ω))))
        (marginal H A l r) then (1:ℝ) else 0) / 2^R

def compilerInput (n T R k : ℕ) : Word :=
  List.replicate n true ++ [false] ++ List.replicate T true ++ [false] ++
    List.replicate R true ++ [false] ++ List.replicate k true

/-- Exact source proof parameters, including the even mesh and zero-safe error allocations. -/
def bridgeAccuracy (n : ℕ) (e : ℝ) : ℝ := e^2/(256*n)
def bridgeFailure (n : ℕ) (e : ℝ) : ℝ := e/(16*4^n)
def prepMesh {n : ℕ} (J : Matrix (Fin n) (Fin n) ℝ) (h η : Fin n → ℝ) (e : ℝ) : ℕ :=
  let c := rowNorm J + maxField h + maxField η + 1
  let ε := bridgeAccuracy n e
  2 * ⌈500 * max ((n:ℝ)*c^2/ε) (Real.rpow ((n:ℝ)*c/ε) (3/2))⌉₊

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, pp. 5, 14, 19–22, 31–34, 37; computational model, SpectralTFIM, Theorems 17, 21, 34 and 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