Construction for Theorem 7.4, part 5: input parser, generator and the construction `constructQ`
DefinitionTwoFoldOPI_CL_Part05lean-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 (the bottom-case program when , the quantum program otherwise), and the generator 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