Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Construction for Theorem 7.4, part 5: input parser, generator and the construction `constructQ`

Definition
TwoFoldOPI_CL_Part05

by sragavan · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

lean-formalizationquantum-algorithmstwo-fold-opi-construction

Definitions underlying the formal construction behind the algorithmic part of Theorem 7.4, part 5 (imports part 4). It contains the parser of the binary instance encoding, the construction constructQ\texttt{constructQ}constructQ (the bottom-case program when C⊥={0}C^\perp=\{0\}C⊥={0}, the quantum program otherwise), and the generator Gen.gen\texttt{Gen.gen}Gen.gen that maps a zero-padded input prefix to the packed serialization of the constructed program, as well as its pre-serialization form (header, node list, root).

The bundle contains only definitions together with the structural lemmas these definitions require.

Definition code
import Definitions.Def_TwoFoldOPI_CL_Part04
import Definitions.Def_TwoFoldOPI_Input

set_option maxHeartbeats 400000
set_option linter.all false

-- ===== OPI.Parse =====
section

/-!
# Parsing and deciding `TwoFoldOPI.Input.encode`, with polynomial realizers

The input is `w = (x.encode ++ 0^s).take s`. The parser threads a state `(cap, rest, ok)` with
`cap = |w| + 1` through readers for self-delimiting numbers (saturated at `cap`), lists of numbers
and bit blocks. Each reader has the extension property (`RdExt`): a successful read is unchanged by
appending input. Since the parse of `x.encode ++ L` ends exactly at `L` whenever `p, d, m, r < cap`,
a proper prefix of an encoding never parses completely with a scale below `cap`.

* `parseI`, `parseI_pr`, `parseI_spec`;
* `decideI`, `decideI_pr`, `decideI_spec`.
-/

namespace OPI.Parse

open OPI OPI.W6 OPI.W6.IsPR OAI.ThreeMachine.StackCompiler

/-- Number of leading pairs `1β` (positions `0, 2, 4, …` holding `true`). -/
def numPairs (l : List Bool) : ℕ :=
  ((List.range (l.length + 1)).filter
    (fun i => (List.range (i + 1)).all (fun j => l.getD (2 * j) false))).length









/-- Read a self-delimiting binary number, saturated at `cap`. -/
def rdNum (cap : ℕ) (l : List Bool) : ℕ × List Bool × Bool :=
  (bitsValS cap ((List.range (numPairs l)).map (fun i => l.getD (2 * i + 1) false)).reverse,
    l.drop (2 * numPairs l + 2), decide (2 * numPairs l + 2 ≤ l.length))

/-- Extension property of a reader: a successful read is unchanged by appending more input. -/
def RdExt {γ : Type} (R : List Bool → γ × List Bool × Bool) : Prop :=
  ∀ l v r, R l = (v, r, true) → ∀ L, R (l ++ L) = (v, r ++ L, true)

























variable {α : Type} [Coding α]







/-! ### Reading several numbers, and blocks -/

/-- One step of reading numbers: append the next number. -/
def numStep (cap : ℕ) (st : List ℕ × List Bool × Bool) : List ℕ × List Bool × Bool :=
  (st.1 ++ [(rdNum cap st.2.1).1], (rdNum cap st.2.1).2.1, st.2.2 && (rdNum cap st.2.1).2.2)

/-- Read `k` self-delimiting numbers, each saturated at `cap`. -/
def rdNums (cap k : ℕ) (l : List Bool) : List ℕ × List Bool × Bool :=
  (List.range k).foldl (fun st _ => numStep cap st) ([], l, true)

/-- Read a block of `b` bits. -/
def rdBlk (b : ℕ) (l : List Bool) : List Bool × List Bool × Bool :=
  (l.take b, l.drop b, decide (b ≤ l.length))




















/-! ### `⌈log₂ p⌉`, saturated powers, chopping into blocks -/

/-- `Nat.clog 2 p`, as the number of `k < p` with `2^k < p`. -/
def clogC (p : ℕ) : ℕ := ((List.range p).filter (fun k => decide (2 ^ k ≤ p - 1))).length









/-- `min (p^d) cap`, by saturating multiplication. -/
def powS (cap p d : ℕ) : ℕ := (List.range d).foldl (fun v _ => min (v * p) cap) (min 1 cap)





/-- Cut a list into `n` consecutive blocks of length `b`. -/
def chop {β : Type} (b n : ℕ) (l : List β) : List (List β) :=
  (List.range n).map (fun k => (l.drop (k * b)).take b)










/-! ### Stages: readers threaded through the state `(cap, rest, ok)` -/

/-- The reader state: the saturation cap, the remaining input, and the success flag. -/
abbrev St := ℕ × List Bool × Bool

/-- Run a reader on the state, pushing its value onto the accumulated values. -/
def thenR {γ : Type} (R : ℕ → α → List Bool → γ × List Bool × Bool) (x : α × St) : (γ × α) × St :=
  (((R x.2.1 x.1 x.2.2.1).1, x.1),
    (x.2.1, (R x.2.1 x.1 x.2.2.1).2.1, x.2.2.2 && (R x.2.1 x.1 x.2.2.1).2.2))





/-- Extension property of a stage. -/
def StExt {β : Type} (F : α × St → β × St) : Prop :=
  ∀ a cap l ok b cap' r, F (a, cap, l, ok) = (b, cap', r, true) →
    ok = true ∧ cap' = cap ∧ ∀ L, F (a, cap, l ++ L, true) = (b, cap, r ++ L, true)






/-- Stage: read a number. -/
def sNum : α × St → (ℕ × α) × St := thenR (fun c _ l => rdNum c l)

/-- Stage: read `kf a` numbers. -/
def sNums (kf : α → ℕ) : α × St → (List ℕ × α) × St := thenR (fun c a l => rdNums c (kf a) l)

/-- Stage: read a block of `bf a` bits. -/
def sBlk (bf : α → ℕ) : α × St → (List Bool × α) × St := thenR (fun _ a l => rdBlk (bf a) l)



















/-! ### The parser -/

/-- Values after reading `d` (and `p`). -/
abbrev V2 := ℕ × ℕ × Unit
/-- Values after reading the bit `gen` (as a block). -/
abbrev V6 := List Bool × ℕ × ℕ × List ℕ × V2
/-- Values after reading the block of `H`. -/
abbrev V7 := List Bool × V6
/-- All values read: `t, β, H, gen, r, m, coefficients, d, p`. -/
abbrev V9 := ℕ × List Bool × V7

/-- Number of coefficients: `d + 1`. -/
def kfC (a : V2) : ℕ := a.1 + 1

/-- Bits of `H`: `r · m · d · ⌈log₂ p⌉`. -/
def bfH (a : V6) : ℕ := a.2.1 * a.2.2.1 * (a.2.2.2.2.1 * clogC a.2.2.2.2.2.1)

/-- Bits of `β`: `m · d · ⌈log₂ p⌉`. -/
def bfB (a : V7) : ℕ := a.2.2.2.1 * (a.2.2.2.2.2.1 * clogC a.2.2.2.2.2.2.1)

/-- The first two stages: `p, d`. -/
def c2 (x : Unit × St) : V2 × St := sNum (sNum x)

/-- The first five stages: `p, d, f_0..f_d, m, r`. -/
def c5 (x : Unit × St) : (ℕ × ℕ × List ℕ × V2) × St := sNum (sNum (sNums kfC (c2 x)))

/-- The reading stages, in order: `p, d, f_0..f_d, m, r, gen, H, β, t`. -/
def core (x : Unit × St) : V9 × St :=
  sNum (sBlk bfB (sBlk bfH (sBlk (fun _ => 1) (c5 x))))





/-- Parsed instance: `p, d, coefficients of f, m, r, gen, H (rows of blocks), β (blocks), t`, and
the flag "the input held a complete encoding". -/
abbrev ParsedI := ℕ × ℕ × List ℕ × ℕ × ℕ × Bool × List (List (List Bool)) × List (List Bool) × ℕ × Bool

/-- Assemble the parsed record from the values read. -/
def outI (y : V9 × St) : ParsedI :=
  (y.1.2.2.2.2.2.2.2.2.1, y.1.2.2.2.2.2.2.2.1, y.1.2.2.2.2.2.2.1, y.1.2.2.2.2.2.1, y.1.2.2.2.2.1,
    y.1.2.2.2.1.headD false,
    (chop (y.1.2.2.2.2.2.1 * (y.1.2.2.2.2.2.2.2.1 * clogC y.1.2.2.2.2.2.2.2.2.1)) y.1.2.2.2.2.1
      y.1.2.2.1).map (chop (y.1.2.2.2.2.2.2.2.1 * clogC y.1.2.2.2.2.2.2.2.2.1) y.1.2.2.2.2.2.1),
    chop (y.1.2.2.2.2.2.2.2.1 * clogC y.1.2.2.2.2.2.2.2.2.1) y.1.2.2.2.2.2.1 y.1.2.1,
    y.1.1, y.2.2.2)





/-- **The parser** of `TwoFoldOPI.Input.encode` (numbers saturated at the input length plus one). -/
def parseI (w : List Bool) : ParsedI := outI (core ((), w.length + 1, w, true))

/-- The scale `m + r + q + t` of a parsed record, `q` saturated at `cap`. -/
def scaleP (cap : ℕ) (P : ParsedI) : ℕ :=
  P.2.2.2.1 + P.2.2.2.2.1 + powS cap P.1 P.2.1 + P.2.2.2.2.2.2.2.2.1

/-- The verdict on a parsed record, for an input of length `n`. -/
def decP (n : ℕ) (P : ParsedI) : List Bool :=
  [P.2.2.2.2.2.2.2.2.2 && decide (scaleP (n + 1) P ≤ n)]

/-- **The decider**: a complete encoding of an instance of scale at most the input length. -/
def decideI (w : List Bool) : List Bool := decP w.length (parseI w)






/-! ### Correctness on encodings -/

section Spec

open TwoFoldOPI QAlgorithms.LocalHamiltonian

/-- The coefficient values `f_0, …, f_d`. -/
def coeffsL (x : Input) : List ℕ := List.ofFn (fun j : Fin (x.F.f.natDegree + 1) => (x.F.f.coeff j).val)

/-- The rows of `H`, as lists of bit blocks. -/
noncomputable def Hrows (x : Input) : List (List (List Bool)) :=
  List.ofFn fun i => List.ofFn fun j => List.ofFn (elemBits x.F (x.H i j))

/-- The entries of `β`, as bit blocks. -/
noncomputable def βblks (x : Input) : List (List Bool) :=
  List.ofFn fun i => List.ofFn (elemBits x.F (x.β i))









































end Spec

end OPI.Parse
end

-- ===== OPI.IRGenDef =====
section

/-!
# The generator on natural-number data

From the parsed input (`Parse.parseI`) and the input length `n`, `genOut` computes the packed
serialization of the constructed program: the bottom program if the dual code is trivial (`kd = 0`),
the quantum program otherwise.
-/

namespace OPI

namespace Gen

open Lay TD RRefC FM SymEnc

/-- Field-negation in coordinates. -/
def negC (p e : ℕ) (a : List ℕ) : List ℕ := subL p (zeroL e) a

/-- The derived numbers of an instance. -/
structure Nums where
  p : ℕ
  e : ℕ
  fl : List ℕ
  m : ℕ
  gen : Bool
  Hc : List (List (List ℕ))
  βb : List (List Bool)
  T : ℕ
  w : ℕ
  L : ℕ
  q : ℕ
  Nb : ℕ

/-- Read the derived numbers. -/
def numsOf (n : ℕ) (P : Parse.ParsedI) : Nums :=
  let p := P.1; let e := P.2.1; let w := Parse.clogC p
  let q := Parse.powS (n + 1) p e
  { p := p, e := e, fl := P.2.2.1, m := P.2.2.2.1, gen := P.2.2.2.2.2.1,
    Hc := P.2.2.2.2.2.2.1.map (fun row => row.map (decLS p e w)), βb := P.2.2.2.2.2.2.2.1,
    T := P.2.2.2.2.2.2.2.2.1, w := w, L := e * w, q := q, Nb := 8 * q ^ 8 }

/-- The kernel dimension. -/
def kdN (u : Nums) : ℕ := kdC u.p u.e u.fl u.Nb u.m u.gen u.Hc

/-- Gradient width parameter `BB`. -/
def BBN (u : Nums) : ℕ := Bpar u.T u.m u.L

/-- The layout tuple. -/
def XN (u : Nums) : ParN :=
  (u.m, u.L, u.e, u.w, 2 * BBN u, 2 * BBN u - 1 + 1, nIds u.m (kdN u) (kdN u * kdN u))

/-- The coordinates of `β`. -/
def βcN (u : Nums) : List (List ℕ) := u.βb.map (decLS u.p u.e u.w)

/-- The basis coordinates. -/
def GcN (u : Nums) : List (List (List ℕ)) := GC u.p u.e u.fl u.Nb u.m u.gen u.Hc
def bWcN (u : Nums) : List (List (List ℕ)) := bWC u.p u.e u.fl u.Nb u.m u.gen u.Hc
def pivN (u : Nums) : List ℕ := pivC u.p u.e u.fl u.Nb u.m u.gen u.Hc

/-- The jobs. -/
def jobsN (u : Nums) : List (List ℕ × PTab) :=
  allJobsN ((List.range u.m).map (RrN (XN u))) (pivN u) (resAllX (XN u))
    ((List.range u.m).map (fun i => bRegN (XN u) i 0)) (validTabN u.p u.e u.w u.L u.Nb)
    (ltTabN u.p u.w u.Nb) ((βcN u).map (fun bc => memTabN u.p u.e u.w bc u.L u.Nb))

/-- The shift tables of the linear map. -/
def TGN (u : Nums) : List (List (PTab × PTab)) :=
  (List.range (kdN u)).map (fun j => (List.range u.m).map (fun i =>
    let g := ((GcN u).getD j []).getD i []
    (fsTabN u.p u.e u.w u.fl g (u.L + u.L) u.L u.Nb, fsTabN u.p u.e u.w u.fl (negC u.p u.e g) (u.L + u.L) u.L u.Nb)))

/-- The shared data of the `QFT_q` gadgets. -/
def shN (u : Nums) : QSh :=
  (totalN (XN u), 2 * BBN u - 1 + 1, u.p, rlTabN u.p u.e u.w u.fl u.L 0 u.Nb, rlinvTabN u.p u.e u.w u.fl u.L 0 u.Nb,
    phaseTabN u.p u.w (2 * BBN u - 1 + 1) u.Nb, qftTabsN (2 * BBN u - 1 + 1) (2 * BBN u),
    csTabsN u.p u.w (2 * BBN u) u.Nb, subTabN u.p u.w (u.w + 1 + u.w) (u.w + 1) u.Nb,
    addTabN u.p u.w (u.w + 1 + u.w) (u.w + 1) u.Nb)

/-- The compiled decoder tables. -/
def clsN (u : Nums) : List (ℕ × List ℕ × PTab) :=
  (progI u.m (kdN u + kdN u * kdN u) (kdN u) (fun j o => matI u.e (kdN u) u.m (GcN u) j o)
    (RelinProg.a0src u.m (kdN u) (kdN u * kdN u)) (a0opI u.e (kdN u) (kdN u * kdN u) u.m (GcN u) (bWcN u))).map
    (fun x => (x.1, x.2.1, progTabN u.p u.e u.fl u.Nb u.w u.L x u.Nb))

/-- The trial circuit. -/
def CfN (u : Nums) : List (List ℕ) :=
  let X := XN u; let kd := kdN u; let nI := nIds u.m kd (kd * kd); let B := GEP.Bd u.m (kd + kd * kd)
  trialCN
    (decCircN (shN u) (cswTabN u.L (1 + (u.L + u.L)) u.Nb) (cswTabN u.L (1 + 2 * u.L) u.Nb)
      ((List.range u.m).map (fun i => cDataN X (pTabN u.p u.e u.w ((βcN u).getD i []) u.L 0 u.Nb) i))
      (clsCN (RSN X u.m B nI) (blkN X 27) (offN X 28) (clsN u)))
    (subAllCN ((List.range u.m).map (fun i => rsOfN X u.m B nI (RelinProg.outId (m := u.m) (k := kd) (k2 := kd * kd) i)))
      ((List.range u.m).map (RrN X)) (blkN X 12) (blkN X 13) (offN X 14)
      (fsTabN u.p u.e u.w u.fl (negC u.p u.e (oneL u.e)) (u.L + u.L) u.L u.Nb)
      (fsTabN u.p u.e u.w u.fl (oneL u.e) (u.L + u.L) u.L u.Nb))

/-- The number of repeat-until-success jobs. -/
def numJobsN (u : Nums) : ℕ := kdN u + u.m * (2 * u.e) + u.m

/-- The quantum segment. -/
def qSegG (u : Nums) : ISeg :=
  let M := u.m * u.L
  qSegN (XN u) (2 * BBN u - 1 + 1) M M M (u.T + 3) (2 * u.q * (u.T + 10 + numJobsN u))
    (2 * u.T + 6 + (2 * BBN u - 1)) (kdN u) (jobsN u) (pivN u) (TGN u)
    (zTabN u.p u.e u.w (2 * BBN u - 1 + 1) u.fl u.Nb) (CfN u) (List.range M)

/-- The quantum serialization. -/
def quantOut (u : Nums) : List Bool :=
  serOut [0, totalN (XN u) + (2 * BBN u - 1 + 1), u.m * u.L + 1, u.m * u.L]
    ([failI] ++ qSegG u 0 1) ((qSegG u).entry 0 1)

/-- The bottom serialization. -/
def botOut (u : Nums) : List Bool :=
  serOut [0, 0, u.m * u.L, u.m * u.L] (botDag u.L (botBits u.p u.e u.w u.βb)) (botRoot u.L (botBits u.p u.e u.w u.βb))

/-- **The generator output.** -/
def genOut (n : ℕ) (P : Parse.ParsedI) : List Bool :=
  let u := numsOf n P
  if kdN u = 0 then botOut u else quantOut u

/-- **The generator.** -/
def gen (w : List Bool) : List Bool := genOut w.length (Parse.parseI w)

end Gen

end OPI
end

-- ===== OPI.Leaf =====
section

/-!
# The leaf statement (without the resources bound and uniformity)
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI TwoFoldOPI

namespace Leaf

open Lay SymEnc















/-- The program for `D = ⊥`. -/
noncomputable def botPacked (x : Input) : PackedMembershipProgram :=
  ⟨0, fun _ => 0, fun _ => false, 0, x.m * bitsPerSymbol x.F, x.m * bitsPerSymbol x.F, Bot.progBot x.F x.m x.β⟩

/-- The quantum program. -/
noncomputable def quantPacked (x : Input) : PackedMembershipProgram :=
  ⟨0, fun _ => 0, fun _ => false, _, x.m * bitsPerSymbol x.F + 1, x.m * bitsPerSymbol x.F,
    progFinal x.F x.m x.gen x.H x.t x.β (Fin.last _) (Fin.last _) (Fin.last _) Fin.castSucc (Fin.castSucc_injective _)⟩

/-- **The construction.** -/
noncomputable def constructQ (x : Input) : PackedMembershipProgram :=
  if kdOf x.F x.m x.gen x.H = 0 then botPacked x else quantPacked x





end Leaf

end OPI
end

-- ===== OPI.IRGenSpec =====
section

/-!
# Correctness of the generator: the derived numbers and the bottom case
-/

namespace OPI

namespace Gen

open QAlgorithms QAlgorithms.OPI TwoFoldOPI Lay TD RRefC FM SymEnc

/-- The parsed record of an input. -/
noncomputable def parsedOf (x : Input) : Parse.ParsedI :=
  (x.F.p, x.F.f.natDegree, List.ofFn (fun j : Fin (x.F.f.natDegree + 1) => (x.F.f.coeff j).val),
    x.m, x.r, x.gen, (List.ofFn fun i => List.ofFn fun j => List.ofFn (elemBits x.F (x.H i j))),
    (List.ofFn fun i => List.ofFn (elemBits x.F (x.β i))), x.t, true)

section
variable (x : Input) (n : ℕ) (hq : x.F.p ^ x.F.f.natDegree ≤ n)
include hq

















end

end Gen

end OPI
end

-- ===== OPI.IRGenDag =====
section

/-!
# The generator before serialization: header, DAG, root
-/

namespace OPI

namespace Gen

open Lay

/-- Header, DAG and root of the constructed program. -/
def genDag (n : ℕ) (P : Parse.ParsedI) : List ℕ × List INode × ℕ :=
  let u := numsOf n P
  if kdN u = 0 then
    ([0, 0, u.m * u.L, u.m * u.L], botDag u.L (botBits u.p u.e u.w u.βb), botRoot u.L (botBits u.p u.e u.w u.βb))
  else
    ([0, totalN (XN u) + (2 * BBN u - 1 + 1), u.m * u.L + 1, u.m * u.L], [failI] ++ qSegG u 0 1, (qSegG u).entry 0 1)



/-- The generator before serialization. -/
def genD (w : List Bool) : List ℕ × List INode × ℕ := genDag w.length (Parse.parseI w)



end Gen

end OPI
end

-- ===== OPI.ResBDepth =====
section

/-!
# Resource bound from a DAG representation (depth bound)

If node `i` of a first-order DAG represents `P : Prog N c out`, every execution leaf of `P`
charges at most `(i + 1) + h` in total, where `h` bounds the sizes of the halting circuits stored
in the DAG (the first field of a tag-`0` node, cf. `haltF`). Hence
`membershipResources P O ≤ N + c + (i + 1) + h`.
-/

set_option autoImplicit false

namespace OPI

open QAlgorithms QAlgorithms.OPI

variable {N c out : ℕ}

/-- Every halting node (tag `0`) of `dag` stores a circuit of size `≤ h` (its first field). -/
def HaltBound (dag : List INode) (h : ℕ) : Prop :=
  ∀ (j : ℕ) (fs cs : List ℕ), dag[j]? = some (0, fs, cs) → fs.headD 0 ≤ h











/-! ### Special case: all halting nodes store size-`0` circuits (e.g. `copyCirc`) -/









end OPI
end

-- ===== OPI.IRFinalRes =====
section

/-!
# The resource bound of the construction, from a polynomial realizer of the generator
-/

namespace OPI

namespace Gen

open QAlgorithms QAlgorithms.OPI TwoFoldOPI OAI.ThreeMachine.StackCompiler W6

/-- The padded input of length `s`. -/
noncomputable def padI (x : Input) (s : ℕ) : List Bool := (x.encode ++ List.replicate s false).take s













end Gen

end OPI
end

-- ===== OPI.IRRrefPR =====
section

/-!
# Realizers of the first-order reduced row echelon form

`IsPR` lemmas for the twins of `IRRref`: the normalized field operations, the insertion step, the
rows of a matrix (`rrefC`, an iteration with an orbit bound along the actual run: at most one row per
step, every coordinate normalized), the nullspace basis, and the basis data `GC`, `pivC`, `kdC`, `bWC`.
-/

namespace OPI

namespace RRefC

open FM

/-! ## Size bounds -/

/-- Well-formed rows: pivots `< m`, rows of `m` entries, each with `e` coordinates `< P`. -/
def WF (m e P : ℕ) (B : RowsC) : Prop :=
  ∀ pu ∈ B, pu.1 < m ∧ pu.2.length = m ∧ ∀ a ∈ pu.2, a.length = e ∧ ∀ y ∈ a, y < P















/-! ## The rows as an iteration -/

/-- The context `(p, e, fl, N, m)`. -/
abbrev RCtx := ℕ × ℕ × List ℕ × ℕ × ℕ

/-- One insertion step on `(context, remaining vectors, rows)`. -/
def rrStep (s : RCtx × List (List (List ℕ)) × RowsC) : RCtx × List (List (List ℕ)) × RowsC :=
  (s.1, s.2.1.tail, insertC s.1.1 s.1.2.1 s.1.2.2.1 s.1.2.2.2.1 s.1.2.2.2.2 s.2.2 (s.2.1.headD []))





/-- The orbit bound. -/
def rrefBound (n : ℕ) : ℕ := 2 * n + n * ((2 * n + 1) + (n * (n * (2 * n + 5) + 1 + 1) + 1) + 1 + 1) + 3



end RRefC

end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI OPI.FM OPI.RRefC

variable {α : Type} [Coding α]

/-! ## Field operations -/

























/-! ## Insertion -/











/-! ## The rows of a matrix -/





/-! ## The basis -/

















end OPI.W6.IsPR
end

-- ===== OPI.IRSegPR =====
section

/-!
# Chains of rigid blocks and their realizers

`iter2 B n` appends the blocks `B 0, …, B (n-1)`; block `j` has continuations the previous entry and
the outer continuation. When every block has a length independent of its continuations and start
(*rigid* blocks), the chain has an explicit closed form, which is realized with `flatMap`.
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI

/-- The chain of blocks. -/
def iter2 (B : ℕ → ISeg2) : ℕ → ISeg
  | 0 => fun _ _ => []
  | n + 1 => then2 (iter2 B n) (B n)

/-- The length of block `j`. -/
def lenB (B : ℕ → ISeg2) (j : ℕ) : ℕ := (B j 0 0 0).length

/-- The offset of block `j`. -/
def offB (B : ℕ → ISeg2) (j : ℕ) : ℕ := ((List.range j).map (lenB B)).sum

/-- The closed form. -/
def iter2C (B : ℕ → ISeg2) (n k s : ℕ) : List INode :=
  (List.range n).flatMap (fun j => B j (if offB B j = 0 then k else s + offB B j - 1) k (s + offB B j))

/-- Rigid blocks. -/
def Rigid (B : ℕ → ISeg2) : Prop := ∀ j k0 k1 s, (B j k0 k1 s).length = lenB B j









/-! ### Rigidity of the building blocks -/

/-- Rigid one-continuation segments. -/
def RigidS (sg : ISeg) : Prop := ∀ k s k' s', (sg k s).length = (sg k' s').length

















/-- A one-continuation segment as a block (the outer continuation is unused). -/
def asB (sg : ISeg) : ISeg2 := fun k0 _ s => sg k0 s



end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI

variable {α : Type} [Coding α]



end OPI.W6.IsPR
end

-- ===== OPI.SegRGrad =====
section

/-!
# Realizers of the gradient-preparation segments

`SegPR`/`Seg2PR` realizers of `testI`, `stageI` (with the grid `gridNodes`), `chainPI` and `gradI`
(`CtrlGrad.lean`), as functions of their natural-number data.
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI

local notation "vl" => List.map Fin.val



/-- The block length of the grid tests. -/
def testLen (c : ℕ) (as wl : List ℕ) (e k : ℕ) : ℕ := (hTestF c as wl e k).length + (rnGates (0, [c])).length + 3

/-- The length of a stage. -/
def gStageLen (c : ℕ) (as wl : List ℕ) (e k Nt : ℕ) (mulF : List (List ℕ)) : ℕ :=
  if Nt = 0 then 0 else mulF.length + (Nt - 1) * ((Nt + 1) * testLen c as wl e k) + testLen c as wl e k



/-- The chain of stages as a chain of rigid blocks (the last stage first). -/
def stageB (c : ℕ) (as wl : List ℕ) (dst Nt b : ℕ) (ks : ℕ → ℕ) (mulFs : ℕ → List (List ℕ)) (j0 n : ℕ) :
    ℕ → ISeg2 := fun i =>
  asB (stageI c as wl (b - (j0 + n - 1 - i) - 1) (ks (j0 + n - 1 - i)) dst Nt (mulFs (j0 + n - 1 - i)))









end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI

variable {α : Type} [Coding α]







end OPI.W6.IsPR

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI

variable {α : Type} [Coding α]















end OPI.W6.IsPR
end

-- ===== OPI.SegRTrial =====
section

/-!
# Realizers of the trial, retry and readout segments

`SegPR` realizers of `measC`, `zeroTestI`, `haltS`, `measAllI`, `retryI` (for rigid trials),
`trialI` (`CtrlTrial.lean`) and of `writeBitsI`, `botDag`, `botRoot` (`IRBot.lean`), with the
closed forms and rigidity lemmas they need.
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI

/-! ### Closed forms -/













/-- The closed form of the retries of a rigid trial: the `fail` node, then the trials. -/
def retryC (T : ISeg) (K _k s : ℕ) : List INode :=
  failI :: (List.range K).flatMap (fun i => T (s + i * (T 0 0).length) (s + 1 + i * (T 0 0).length))





/-! ### Rigidity -/



















end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI

variable {α : Type} [Coding α]





















/-! ### The bottom program -/







end OPI.W6.IsPR
end

-- ===== OPI.GenR =====
section

/-!
# The generator has a polynomial realizer

`gen_pr : IsPR Gen.gen`, proved compositionally by `fun_prop` from the realizers of the building
blocks. The record `Gen.Nums` is coded as the tuple of its fields.
-/

namespace OPI

namespace Gen

/-- The fields of `Nums` as a tuple. -/
abbrev NumsT := ℕ × ℕ × List ℕ × ℕ × Bool × List (List (List ℕ)) × List (List Bool) × ℕ × ℕ × ℕ × ℕ × ℕ

/-- `Nums` to its tuple. -/
def Nums.toT (u : Nums) : NumsT := (u.p, u.e, u.fl, u.m, u.gen, u.Hc, u.βb, u.T, u.w, u.L, u.q, u.Nb)

/-- A tuple to `Nums`. -/
def Nums.ofT (t : NumsT) : Nums :=
  ⟨t.1, t.2.1, t.2.2.1, t.2.2.2.1, t.2.2.2.2.1, t.2.2.2.2.2.1, t.2.2.2.2.2.2.1, t.2.2.2.2.2.2.2.1,
    t.2.2.2.2.2.2.2.2.1, t.2.2.2.2.2.2.2.2.2.1, t.2.2.2.2.2.2.2.2.2.2.1, t.2.2.2.2.2.2.2.2.2.2.2⟩

end Gen

namespace W6

open OAI.ThreeMachine.StackCompiler

/-- `Nums` is coded as the tuple of its fields. -/
instance instCodingGenNums : Coding Gen.Nums := ⟨fun u => enc u.toT⟩

namespace IsPR

open Gen Lay TD RRefC FM SymEnc

variable {α : Type} [Coding α]























/-! ### The derived data -/
























/-! ### The generator -/









end IsPR

end W6

namespace Gen





end Gen

end OPI
end
Source
Formalization of Theorem 7.4 (algorithmic part), repository https://github.com/sragavan99/lean-prove2me-fills/blob/db81d0d4e3fa008609ed37789a2eb2f6f08ee48d/Definitions/Def_TwoFoldOPI_CL_Part05.lean

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