Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Construction for Theorem 7.4, part 3: realizers, segments, field model, gradient preparation

Definition
TwoFoldOPI_CL_Part03

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 3 (imports part 2). It contains the serializer state machine and its bounds, the first-order representation Rep of programs by node lists, program segments with one and two continuations, the field model in coordinates (power-basis coordinate lists and their arithmetic), first-order twins of the reversible-circuit builders and their realizers, the gradient-state preparation (majority tests and multipliers), bit encodings and field tables, and the layout allocation of wires into blocks.

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

Definition code
import Definitions.Def_TwoFoldOPI_CL_Part02
import Mathlib

set_option maxHeartbeats 400000
set_option linter.all false

-- ===== OPI.DFSPR =====
section

/-!
# The DFS machine step as a polynomial realizer
-/

namespace OPI

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

/-- The decoded context of a non-empty machine state. -/
abbrev Ctx := List INode × (Frame × (List Frame × (List (Option ℕ) × (List Str × ℕ))))

def ctxOf (x : List INode × MState) : Ctx := (x.1, (x.2.1.headD (0, 0, []), (x.2.1.tail, x.2.2)))

def hitOf (c : Ctx) : Option ℕ := if c.2.1.2.1 = 0 then mf c.2.2.2.1 c.2.1.1 else none
def ndOf (c : Ctx) : INode := c.1.getD c.2.1.1 failI
def cjOf (c : Ctx) : Option ℕ := (ndOf c).2.2[c.2.1.2.1]?

def brHit (c : Ctx) (k : ℕ) : MState := (deliver k c.2.2.1, c.2.2.2.1, c.2.2.2.2.1, k)
def brPush (c : Ctx) (j : ℕ) : MState :=
  ((j, 0, []) :: (c.2.1.1, c.2.1.2.1 + 1, c.2.1.2.2) :: c.2.2.1, c.2.2.2)
def brFail (c : Ctx) : MState :=
  ((c.2.1.1, c.2.1.2.1 + 1, c.2.1.2.2 ++ [(internProgramNode failCode c.2.2.2.2.1).1]) :: c.2.2.1,
    c.2.2.2.1, (internProgramNode failCode c.2.2.2.2.1).2, c.2.2.2.2.2)
def brDone (c : Ctx) : MState :=
  (deliver (internProgramNode (codeI (ndOf c) c.2.1.2.2) c.2.2.2.2.1).1 c.2.2.1,
    c.2.2.2.1.set c.2.1.1 (some (internProgramNode (codeI (ndOf c) c.2.1.2.2) c.2.2.2.2.1).1),
    (internProgramNode (codeI (ndOf c) c.2.1.2.2) c.2.2.2.2.1).2,
    (internProgramNode (codeI (ndOf c) c.2.1.2.2) c.2.2.2.2.1).1)

def stepC (c : Ctx) : MState :=
  if (hitOf c).isSome then brHit c ((hitOf c).getD 0)
  else if (cjOf c).isSome then
    (if (cjOf c).getD 0 < c.2.1.1 then brPush c ((cjOf c).getD 0) else brFail c)
  else brDone c

lemma stepM_eq (dag : List INode) (s : MState) :
    stepM dag s = if s.1.isEmpty then s else stepC (ctxOf (dag, s)) := by
  rcases s with ⟨stack, memo, T, res⟩
  cases stack with
  | nil => rfl
  | cons fr S =>
    rcases fr with ⟨i, ph, rs⟩
    simp only [List.isEmpty_cons, Bool.false_eq_true, if_false, stepC, ctxOf, List.headD_cons, List.tail_cons,
      hitOf, cjOf, ndOf, brHit, brPush, brFail, brDone]
    simp only [stepM]
    have key : ∀ o : Option ℕ, (match o with
        | some k => (deliver k S, memo, T, k)
        | none =>
          match (dag.getD i failI).2.2[ph]? with
          | some j =>
            if j < i then ((j, 0, []) :: (i, ph + 1, rs) :: S, memo, T, res)
            else ((i, ph + 1, rs ++ [(internProgramNode failCode T).1]) :: S, memo, (internProgramNode failCode T).2, res)
          | none =>
            (deliver (internProgramNode (codeI (dag.getD i failI) rs) T).1 S,
              memo.set i (some (internProgramNode (codeI (dag.getD i failI) rs) T).1),
              (internProgramNode (codeI (dag.getD i failI) rs) T).2,
              (internProgramNode (codeI (dag.getD i failI) rs) T).1)) =
        if o.isSome = true then (deliver (o.getD 0) S, memo, T, o.getD 0)
        else if (dag.getD i failI).2.2[ph]?.isSome = true then
          if (dag.getD i failI).2.2[ph]?.getD 0 < i then
            (((dag.getD i failI).2.2[ph]?.getD 0, 0, []) :: (i, ph + 1, rs) :: S, memo, T, res)
          else ((i, ph + 1, rs ++ [(internProgramNode failCode T).1]) :: S, memo, (internProgramNode failCode T).2, res)
        else
          (deliver (internProgramNode (codeI (dag.getD i failI) rs) T).1 S,
            memo.set i (some (internProgramNode (codeI (dag.getD i failI) rs) T).1),
            (internProgramNode (codeI (dag.getD i failI) rs) T).2,
            (internProgramNode (codeI (dag.getD i failI) rs) T).1) := by
      intro o
      cases o with
      | some k => rfl
      | none =>
        simp only [Option.isSome_none, Bool.false_eq_true, if_false]
        cases (dag.getD i failI).2.2[ph]? <;> rfl
    by_cases hph : ph = 0
    · subst hph; exact key _
    · simp only [hph, if_false]; exact key none

end OPI

namespace OPI.W6.PR

open QAlgorithms QAlgorithms.OPI QAlgorithms.Complexity OAI.ThreeMachine.StackCompiler

def mfP : PR (fun x : List (Option ℕ) × ℕ => mf x.1 x.2) :=
  ((PR.id.pair (const (none : Option ℕ))).comp listGetD).congr (fun _ => rfl)

def deliverP : PR (fun x : ℕ × List Frame => deliver x.1 x.2) :=
  let hd : PR (fun x : ℕ × List Frame => x.2.headD (0, 0, [])) := (snd.pair (const (0, 0, []))).comp headD
  let newF : PR (fun x : ℕ × List Frame =>
      ((x.2.headD (0, 0, [])).1, (x.2.headD (0, 0, [])).2.1, (x.2.headD (0, 0, [])).2.2 ++ [x.1])) :=
    (hd.comp fst).pair ((hd.comp (snd.comp fst)).pair
      (((hd.comp (snd.comp snd)).pair ((fst.pair nil).comp cons)).comp append))
  let consP : PR (fun x : ℕ × List Frame =>
      ((x.2.headD (0, 0, [])).1, (x.2.headD (0, 0, [])).2.1, (x.2.headD (0, 0, [])).2.2 ++ [x.1]) :: x.2.tail) :=
    (newF.pair (snd.comp tail)).comp cons
  (PR.ite (snd.comp isCons) consP nil).congr (fun x => by
    rcases x with ⟨k, S⟩
    cases S with
    | nil => rfl
    | cons fr S => rcases fr with ⟨i, ph, rs⟩; rfl)


def someP {α : Type} [Coding α] : PR (fun a : α => some a) :=
  (PR.id.pair (const ())).comp (reinterpret (fun p : α × Unit => some p.1) (fun _ => rfl))

def ltP : PR (fun x : ℕ × ℕ => decide (x.1 < x.2)) :=
  (((fst.comp succ).pair snd).comp PR.le).congr (fun x => rfl)

def ctxP : PR ctxOf :=
  (fst.pair ((((snd.comp fst).pair (const (0, 0, []))).comp headD).pair
    (((snd.comp fst).comp tail).pair (snd.comp snd)))).congr (fun _ => rfl)

section Ctx
abbrev dagC : PR (fun c : Ctx => c.1) := fst
abbrev iC : PR (fun c : Ctx => c.2.1.1) := (snd.comp fst).comp fst
abbrev phC : PR (fun c : Ctx => c.2.1.2.1) := ((snd.comp fst).comp snd).comp fst
abbrev rsC : PR (fun c : Ctx => c.2.1.2.2) := ((snd.comp fst).comp snd).comp snd
abbrev SC : PR (fun c : Ctx => c.2.2.1) := (snd.comp snd).comp fst
abbrev restC : PR (fun c : Ctx => c.2.2.2) := (snd.comp snd).comp snd
abbrev memoC : PR (fun c : Ctx => c.2.2.2.1) := restC.comp fst
abbrev TC : PR (fun c : Ctx => c.2.2.2.2.1) := (restC.comp snd).comp fst
abbrev resC : PR (fun c : Ctx => c.2.2.2.2.2) := (restC.comp snd).comp snd
end Ctx

def hitP : PR hitOf :=
  (PR.ite (phC.comp isZero) ((memoC.pair iC).comp mfP) (const none)).congr (fun c => by
    simp only [hitOf, decide_eq_true_eq])

def ndP : PR ndOf := ((dagC.pair iC).pair (const failI)).comp listGetD

def cjP : PR cjOf := ((ndP.comp (snd.comp snd)).pair phC).comp getElem?

def brHitP : PR (fun y : Ctx × ℕ => brHit y.1 y.2) :=
  ((snd.pair (fst.comp SC)).comp deliverP).pair ((fst.comp memoC).pair ((fst.comp TC).pair snd))

def brPushP : PR (fun y : Ctx × ℕ => brPush y.1 y.2) :=
  let jF : PR (fun y : Ctx × ℕ => (y.2, 0, ([] : List ℕ))) := snd.pair ((const 0).pair nil)
  let pF : PR (fun y : Ctx × ℕ => (y.1.2.1.1, y.1.2.1.2.1 + 1, y.1.2.1.2.2)) :=
    (fst.comp iC).pair (((fst.comp phC).comp succ).pair (fst.comp rsC))
  ((jF.pair ((pF.pair (fst.comp SC)).comp cons)).comp cons).pair (fst.comp restC)

def brFailP : PR brFail :=
  let uP : PR (fun c : Ctx => internProgramNode failCode c.2.2.2.2.1) := ((const failCode).pair TC).comp intern
  let frameP : PR (fun c : Ctx => (c.2.1.1, c.2.1.2.1 + 1, c.2.1.2.2 ++ [(internProgramNode failCode c.2.2.2.2.1).1])) :=
    iC.pair ((phC.comp succ).pair ((rsC.pair (((uP.comp fst).pair nil).comp cons)).comp append))
  ((frameP.pair SC).comp cons).pair (memoC.pair ((uP.comp snd).pair resC))

def brDoneP : PR brDone :=
  let uP : PR (fun c : Ctx => internProgramNode (codeI (ndOf c) c.2.1.2.2) c.2.2.2.2.1) :=
    (((ndP.pair rsC).comp codeIP).pair TC).comp intern
  (((uP.comp fst).pair SC).comp deliverP).pair
    ((((memoC.pair iC).pair ((uP.comp fst).comp someP)).comp setL).pair ((uP.comp snd).pair (uP.comp fst)))

def stepCP : PR stepC :=
  let hitD : PR (fun c : Ctx => (hitOf c).getD 0) := (hitP.pair (const 0)).comp optGetD
  let cjD : PR (fun c : Ctx => (cjOf c).getD 0) := (cjP.pair (const 0)).comp optGetD
  (PR.ite (hitP.comp isSome) ((PR.id.pair hitD).comp brHitP)
    (PR.ite (cjP.comp isSome) (PR.ite ((cjD.pair iC).comp ltP) ((PR.id.pair cjD).comp brPushP) brFailP) brDoneP)).congr
    (fun c => by simp only [stepC, decide_eq_true_eq])

/-- **The machine step.** -/
def stepP : PR (fun x : List INode × MState => (x.1, stepM x.1 x.2)) :=
  (fst.pair (PR.ite ((snd.comp fst).comp (isCons.comp not)) snd (ctxP.comp stepCP))).congr (fun x => by
    rcases x with ⟨dag, s⟩
    simp only [Bool.not_not, stepM_eq])

end OPI.W6.PR
end

-- ===== OPI.DFSBound =====
section

/-!
# Volume bounds along the DFS machine run, and the serializer realizer
-/

namespace OPI

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

lemma length_encNat (k : ℕ) : (encNat k).length = k + 1 := by simp [encNat]

lemma length_serializeWords (l : List ℕ) : (serializeWords l).length = (l.map (fun x => x + 1)).sum := by
  induction l with
  | nil => rfl
  | cons x l ih => rw [serializeWords_cons, List.length_append, length_encNat, ih]; simp

lemma intern_fst_le (c : Str) (T : List Str) : (internProgramNode c T).1 ≤ T.length := by
  unfold internProgramNode
  split
  · exact (List.idxOf_lt_length_of_mem ‹_›).le
  · exact le_rfl

lemma intern_snd (c : Str) (T : List Str) :
    (internProgramNode c T).2 = T ∨ (internProgramNode c T).2 = T ++ [c] := by
  unfold internProgramNode; split <;> simp

/-- Bounds on a frame. -/
def FrOK (B : ℕ) (fr : Frame) : Prop :=
  fr.1 ≤ B ∧ fr.2.1 ≤ B ∧ fr.2.2.length ≤ B ∧ ∀ x ∈ fr.2.2, x ≤ B

lemma FrOK.mono {B B' : ℕ} (h : B ≤ B') {fr : Frame} (hf : FrOK B fr) : FrOK B' fr :=
  ⟨hf.1.trans h, hf.2.1.trans h, hf.2.2.1.trans h, fun x hx => (hf.2.2.2 x hx).trans h⟩

/-- Bounds on a machine state. -/
def Bnd (L B : ℕ) (s : MState) : Prop :=
  s.1.length ≤ B ∧ (∀ fr ∈ s.1, FrOK B fr) ∧
  s.2.1.length ≤ B ∧ (∀ o ∈ s.2.1, ∀ k ∈ o, k ≤ B) ∧
  s.2.2.1.length ≤ B ∧ (∀ t ∈ s.2.2.1, t.length ≤ L + B * (B + 1)) ∧ s.2.2.2 ≤ B

lemma Bnd.mono {L B B' : ℕ} (h : B ≤ B') {s : MState} (hs : Bnd L B s) : Bnd L B' s := by
  obtain ⟨h1, h2, h3, h4, h5, h6, h7⟩ := hs
  have e : B * (B + 1) ≤ B' * (B' + 1) := Nat.mul_le_mul h (by omega)
  exact ⟨h1.trans h, fun fr hf => (h2 fr hf).mono h, h3.trans h, fun o ho k hk => (h4 o ho k hk).trans h,
    h5.trans h, fun t ht => (h6 t ht).trans (by omega), h7.trans h⟩

lemma deliver_length (k : ℕ) (S : List Frame) : (deliver k S).length = S.length := by
  cases S <;> rfl

lemma deliver_ok {B : ℕ} (k : ℕ) (hk : k ≤ B) (S : List Frame) (hS : ∀ fr ∈ S, FrOK B fr) :
    ∀ fr ∈ deliver k S, FrOK (B + 1) fr := by
  cases S with
  | nil => simp [deliver]
  | cons fr S =>
    rcases fr with ⟨i, ph, rs⟩
    intro fr hfr
    simp only [deliver, List.mem_cons] at hfr
    rcases hfr with rfl | hfr
    · obtain ⟨h1, h2, h3, h4⟩ := hS _ List.mem_cons_self
      refine ⟨by simp only at h1 ⊢; omega, by simp only at h2 ⊢; omega, ?_, ?_⟩
      · simp only [List.length_append, List.length_singleton] at h3 ⊢; omega
      · intro x hx
        simp only [List.mem_append, List.mem_singleton] at hx
        rcases hx with hx | rfl
        · have := h4 x hx; omega
        · omega
    · exact (hS fr (List.mem_cons_of_mem _ hfr)).mono (by omega)

lemma length_codeI_le (nd : INode) (rs : List ℕ) (B : ℕ) (hrs : rs.length ≤ B) (hx : ∀ x ∈ rs, x ≤ B) :
    (codeI nd rs).length ≤ (serializeWords (nd.1 :: nd.2.1)).length + B * (B + 1) := by
  unfold codeI
  rw [show nd.1 :: (nd.2.1 ++ rs) = (nd.1 :: nd.2.1) ++ rs from rfl, serializeWords_append,
    List.length_append, length_serializeWords rs]
  have : (rs.map (fun x => x + 1)).sum ≤ rs.length * (B + 1) := by
    have := List.sum_le_card_nsmul (rs.map (fun x => x + 1)) (B + 1) (fun y hy => by
      obtain ⟨x, hx', rfl⟩ := List.mem_map.mp hy; have := hx x hx'; omega)
    simpa using this
  have : rs.length * (B + 1) ≤ B * (B + 1) := Nat.mul_le_mul_right _ hrs
  omega

/-- **One step preserves the bounds, with `B` increased by one.** -/
theorem Bnd_step (dag : List INode) (L : ℕ) (hL : 2 ≤ L)
    (hdag : ∀ nd ∈ dag, (serializeWords (nd.1 :: nd.2.1)).length ≤ L)
    (B : ℕ) (s : MState) (hs : Bnd L B s) : Bnd L (B + 1) (stepM dag s) := by
  rcases s with ⟨stack, memo, T, res⟩
  obtain ⟨h1, h2, h3, h4, h5, h6, h7⟩ := hs
  simp only at h1 h2 h3 h4 h5 h6 h7
  have hE : L + B * (B + 1) ≤ L + (B + 1) * (B + 1 + 1) := by
    have : B * (B + 1) ≤ (B + 1) * (B + 1 + 1) := Nat.mul_le_mul (by omega) (by omega)
    omega
  cases stack with
  | nil => exact Bnd.mono (by omega) ⟨h1, h2, h3, h4, h5, h6, h7⟩
  | cons fr S =>
    rcases fr with ⟨i, ph, rs⟩
    obtain ⟨fi, fph, frs, frx⟩ := h2 _ List.mem_cons_self
    simp only at fi fph frs frx
    have hS : ∀ fr ∈ S, FrOK B fr := fun fr hf => h2 fr (List.mem_cons_of_mem _ hf)
    simp only [List.length_cons] at h1
    have hT : ∀ (c : Str), c.length ≤ L + (B + 1) * (B + 1 + 1) →
        (internProgramNode c T).2.length ≤ B + 1 ∧
        ∀ t ∈ (internProgramNode c T).2, t.length ≤ L + (B + 1) * (B + 1 + 1) := by
      intro c hc
      rcases intern_snd c T with h | h <;> rw [h]
      · exact ⟨by omega, fun t ht => (h6 t ht).trans hE⟩
      · refine ⟨by simp; omega, fun t ht => ?_⟩
        simp only [List.mem_append, List.mem_singleton] at ht
        rcases ht with ht | rfl
        · exact (h6 t ht).trans hE
        · exact hc
    have hu := fun c => intern_fst_le c T
    simp only [stepM]
    split
    · -- memo hit
      rename_i k hk
      have hkB : k ≤ B := by
        split at hk
        · unfold mf at hk
          rw [List.getD_eq_getElem?_getD] at hk
          cases hm : memo[i]? with
          | none => rw [hm] at hk; simp at hk
          | some o =>
            rw [hm] at hk
            simp only [Option.getD_some] at hk
            exact h4 o (List.mem_of_getElem? hm) k hk
        · simp at hk
      dsimp only [Bnd]
      refine ⟨by rw [deliver_length]; omega, deliver_ok k hkB S hS, by omega,
        fun o ho k' hk' => (h4 o ho k' hk').trans (by omega), by omega,
        fun t ht => (h6 t ht).trans hE, by omega⟩
    · split
      · rename_i j hj
        split
        · -- push
          rename_i hji
          dsimp only [Bnd]
          refine ⟨by simp; omega, ?_, by omega, fun o ho k' hk' => (h4 o ho k' hk').trans (by omega), by omega,
            fun t ht => (h6 t ht).trans hE, by omega⟩
          intro fr hfr
          simp only [List.mem_cons] at hfr
          rcases hfr with rfl | rfl | hfr
          · exact ⟨by simp only; omega, by simp, by simp, by simp⟩
          · exact ⟨by simp only; omega, by simp only; omega, by simp only; omega,
              fun x hx => (frx x hx).trans (by omega)⟩
          · exact (hS fr hfr).mono (by omega)
        · -- failing child
          have hTf := hT failCode (by simp [failCode, serializeWords, encNat]; omega)
          dsimp only [Bnd]
          refine ⟨by simp; omega, ?_, by omega, fun o ho k' hk' => (h4 o ho k' hk').trans (by omega),
            hTf.1, hTf.2, by omega⟩
          intro fr hfr
          simp only [List.mem_cons] at hfr
          rcases hfr with rfl | hfr
          · refine ⟨by simp only; omega, by simp only; omega, by simp; omega, fun x hx => ?_⟩
            simp only [List.mem_append, List.mem_singleton] at hx
            rcases hx with hx | rfl
            · exact (frx x hx).trans (by omega)
            · have := hu failCode; omega
          · exact (hS fr hfr).mono (by omega)
      · -- done
        set nd := dag.getD i failI
        have hnd : (serializeWords (nd.1 :: nd.2.1)).length ≤ L := by
          simp only [nd, List.getD_eq_getElem?_getD]
          cases hdi : dag[i]? with
          | none => simp [failI, serializeWords, encNat]; omega
          | some n => exact hdag n (List.mem_of_getElem? hdi)
        have hc := length_codeI_le nd rs B frs frx
        have hTd := hT (codeI nd rs) (by omega)
        have hk := hu (codeI nd rs)
        dsimp only [Bnd]
        refine ⟨by rw [deliver_length]; omega, deliver_ok _ (by omega) S hS, by simp; omega, ?_,
          hTd.1, hTd.2, by omega⟩
        intro o ho k' hk'
        rcases List.mem_or_eq_of_mem_set ho with ho | rfl
        · exact (h4 o ho k' hk').trans (by omega)
        · simp only [Option.mem_def, Option.some.injEq] at hk'; omega

end OPI

namespace OPI

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

/-- The volume bound of bounded states. -/
def Qv (L B : ℕ) : ℕ :=
  (B * (2 * B * B + 8 * B + 9) + 1) + (B * (2 * B + 4) + 1) + (B * (4 * (L + B * (B + 1)) + 2) + 1) +
    (2 * B + 1) + 3

lemma Qv_mono {L L' B B' : ℕ} (hL : L ≤ L') (hB : B ≤ B') : Qv L B ≤ Qv L' B' := by
  unfold Qv
  have h1 : B * B ≤ B' * B' := Nat.mul_le_mul hB hB
  have h2 : B * (2 * B * B + 8 * B + 9) ≤ B' * (2 * B' * B' + 8 * B' + 9) :=
    Nat.mul_le_mul hB (by nlinarith)
  have h3 : B * (2 * B + 4) ≤ B' * (2 * B' + 4) := Nat.mul_le_mul hB (by omega)
  have h4 : B * (B + 1) ≤ B' * (B' + 1) := Nat.mul_le_mul hB (by omega)
  have h5 : B * (4 * (L + B * (B + 1)) + 2) ≤ B' * (4 * (L' + B' * (B' + 1)) + 2) :=
    Nat.mul_le_mul hB (by omega)
  omega

lemma Qv_poly : Poly (fun n => Qv n n) := by
  refine ⟨fun a b h => Qv_mono h h, 1000, 3, fun n => ?_⟩
  unfold Qv
  have : n ≤ (n + 1) := by omega
  nlinarith [Nat.zero_le n, sq_nonneg (n + 1)]



lemma vol_of_Bnd {L B : ℕ} {s : MState} (hs : Bnd L B s) : volume s ≤ Qv L B := by
  rcases s with ⟨stack, memo, T, res⟩
  obtain ⟨h1, h2, h3, h4, h5, h6, h7⟩ := hs
  simp only at h1 h2 h3 h4 h5 h6 h7
  have hS := volume_list_le stack (2 * B * B + 8 * B + 8) (fun fr hfr => by
    rcases fr with ⟨i, ph, rs⟩
    obtain ⟨fi, fph, frs, frx⟩ := h2 _ hfr
    simp only at fi fph frs frx
    have hrs := volume_list_le rs (2 * B + 1) (fun x hx => by have := frx x hx; simp only [volume_nat]; omega)
    have : rs.length * (2 * B + 1 + 1) ≤ B * (2 * B + 1 + 1) := Nat.mul_le_mul_right _ frs
    simp only [volume_pair, volume_nat]
    nlinarith)
  have hM := volume_list_le memo (2 * B + 3) (fun o ho => by
    cases o with
    | none => simp
    | some k => have := h4 _ ho k rfl; simp only [volume_some, volume_nat]; omega)
  have hT := volume_list_le T (4 * (L + B * (B + 1)) + 1) (fun t ht => by
    have := volume_bools_le t; have := h6 t ht; omega)
  have e1 : stack.length * (2 * B * B + 8 * B + 8 + 1) ≤ B * (2 * B * B + 8 * B + 9) :=
    Nat.mul_le_mul h1 (by omega)
  have e2 : memo.length * (2 * B + 3 + 1) ≤ B * (2 * B + 4) := Nat.mul_le_mul h3 (by omega)
  have e3 : T.length * (4 * (L + B * (B + 1)) + 1 + 1) ≤ B * (4 * (L + B * (B + 1)) + 2) :=
    Nat.mul_le_mul h5 (by omega)
  simp only [volume_pair, volume_nat]
  unfold Qv
  omega

lemma Bnd_init (L root : ℕ) : Bnd L (root + 1) (initM root) := by
  refine ⟨by simp [initM], ?_, by simp [initM], ?_, by simp [initM], by simp [initM], by simp [initM]⟩
  · intro fr hfr
    simp only [initM, List.mem_singleton] at hfr
    subst hfr
    exact ⟨by simp only; omega, by simp, by simp, by simp⟩
  · intro o ho k hk
    simp only [initM, List.mem_replicate] at ho
    rw [ho.2] at hk; simp at hk

lemma Bnd_iter (dag : List INode) (L : ℕ) (hL : 2 ≤ L)
    (hdag : ∀ nd ∈ dag, (serializeWords (nd.1 :: nd.2.1)).length ≤ L) (root j : ℕ) :
    Bnd L (root + 1 + j) ((stepM dag)^[j] (initM root)) := by
  induction j with
  | zero => exact Bnd_init L root
  | succ j ih => rw [Function.iterate_succ_apply']; exact Bnd_step dag L hL hdag _ _ ih

lemma code_le_volume (nd : INode) : (serializeWords (nd.1 :: nd.2.1)).length ≤ volume nd := by
  rcases nd with ⟨tag, fields, ch⟩
  rw [length_serializeWords]
  have : (fields.map (fun x => x + 1)).sum ≤ volume fields := by
    induction fields with
    | nil => simp
    | cons x xs ih => simp only [List.map_cons, List.sum_cons, volume_cons, volume_nat]; omega
  simp only [List.map_cons, List.sum_cons, volume_pair, volume_nat]
  omega

lemma children_le_volume (dag : List INode) : (dag.flatMap (fun nd => nd.2.2)).length ≤ volume dag := by
  induction dag with
  | nil => simp
  | cons nd dag ih =>
    rcases nd with ⟨tag, fields, ch⟩
    simp only [List.flatMap_cons, List.length_append, volume_cons, volume_pair]
    have := PR.length_le_volume ch
    omega

end OPI

namespace OPI.W6.PR

open OAI.ThreeMachine.StackCompiler

variable {α β : Type} [Coding α] [Coding β]

/-- Iteration from a computed start, given bounds on the reachable iterates. -/
def iterFrom {n : α → ℕ} {a : α → β} {f : β → β} (Pn : PR n) (Pa : PR a) (P : PR f)
    (G : ℕ → ℕ) (hG : Poly G) (hacc : ∀ x j, j ≤ n x → volume (f^[j] (a x)) ≤ G (volume x)) :
    PR (fun x => f^[n x] (a x)) :=
  ⟨(Pn.pair Pa).R.comp P.R.iterate,
    fun v => (Pn.pair Pa).T v + 10000 * ((Pn.T v + 1) * (P.T (G v) + G v + Pn.T v + 1)) +
      10 * ((Pn.pair Pa).T v + 1) + G v,
    (((Pn.pair Pa).poly.add (Poly.smul 10000 (Pn.poly.succ.mul
      ((((hG.comp P.poly).add hG).add Pn.poly).succ)))).add (Poly.smul 10 (Pn.pair Pa).poly.succ)).add hG,
    fun x => by
      rw [Realizer.time_comp]
      have h1 := (Pn.pair Pa).time_le x
      have hm : n x ≤ Pn.T (volume x) := by have := Pn.vol_le x; rw [volume_nat] at this; omega
      have h2 := Realizer.time_iterate_le P.R (n x) (a x) (P.T (G (volume x))) (G (volume x))
        (fun j hj => (P.time_le _).trans (P.poly.mono (hacc x j hj.le)))
        (fun j hj => hacc x j hj)
      have e : (n x + 1) * (P.T (G (volume x)) + G (volume x) + n x + 1) ≤
          (Pn.T (volume x) + 1) * (P.T (G (volume x)) + G (volume x) + Pn.T (volume x) + 1) :=
        Nat.mul_le_mul (by omega) (by omega)
      rw [Nat.mul_assoc] at h2
      have h3 := (Pn.pair Pa).vol_le x
      show _ ≤ (Pn.pair Pa).T (volume x) + 10000 * _ + _ + _
      omega,
    fun x => (hacc x (n x) le_rfl).trans (by omega)⟩

end OPI.W6.PR
end

-- ===== OPI.Serial =====
section

/-!
# The serializer realizer

`serOut hdr dag root` is the packed serialization of the DAG program `dag` with root `root` and
header words `hdr`; it has a polynomial realizer (`serOutP`), and equals `packedSerialization`
of `packDag` (`packedSerialization_packDag_eq`).
-/

namespace OPI

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

/-- The serialization computed from first-order nodes. -/
def serOut (hdr : List ℕ) (dag : List INode) (root : ℕ) : Str :=
  serializeWords hdr ++ (encNat (travI dag root (fun _ => none) []).1 ++
    encStr (travI dag root (fun _ => none) []).2.1)



/-- The iterated machine step. -/
lemma iter_step (dag : List INode) (s : MState) (j : ℕ) :
    (fun x : List INode × MState => (x.1, stepM x.1 x.2))^[j] (dag, s) = (dag, (stepM dag)^[j] s) := by
  induction j generalizing s with
  | zero => rfl
  | succ j ih => rw [Function.iterate_succ_apply, Function.iterate_succ_apply]; exact ih _

/-- The bound parameter of the serializer. -/
def Mser (v : ℕ) : ℕ := (v + 2) + (v + 1 + ((2 * v + 2) * (v + 1) + 1))

lemma Mser_poly : Poly Mser := by
  refine ⟨fun a b h => ?_, 100, 2, fun n => ?_⟩
  · unfold Mser; have : (2 * a + 2) * (a + 1) ≤ (2 * b + 2) * (b + 1) := Nat.mul_le_mul (by omega) (by omega)
    omega
  · unfold Mser; nlinarith

/-- The reachable-volume bound of the serializer. -/
def Gser (v : ℕ) : ℕ := v + Qv (Mser v) (Mser v) + 1

lemma Gser_poly : Poly Gser := (Poly.id.add (Mser_poly.comp Qv_poly)).succ

namespace W6.PR

def wMP : PR (fun dag : List INode => wM dag) :=
  ((((id.pair (const ())).comp ((fst.comp (snd.comp snd) : PR (fun y : INode × Unit => y.1.2.2)).flatMap)).comp
    length).comp ((id.pair id).comp add)).congr (fun dag => by simp [wM]; ring)

def fuelP : PR (fun x : List INode × ℕ => fuelM x.1 x.2) :=
  ((((((fst.comp wMP).pair (const 2)).comp add).pair (snd.comp succ)).comp mul).comp succ).congr
    (fun x => rfl)

def initP : PR (fun x : List INode × ℕ => (x.1, initM x.2)) :=
  fst.pair ((((snd.pair ((const 0).pair nil)).pair nil).comp cons).pair
    ((((snd.comp succ).pair (const (none : Option ℕ))).comp replicate).pair
      ((const ([] : List Str)).pair (const 0))))

/-- **The memoized traversal, realized.** -/
def travP : PR (fun x : List INode × ℕ =>
    ((travI x.1 x.2 (fun _ => none) []).1, (travI x.1 x.2 (fun _ => none) []).2.1)) :=
  ((iterFrom fuelP initP stepP Gser Gser_poly (fun x j hj => by
      rcases x with ⟨dag, root⟩
      simp only at hj ⊢
      rw [iter_step]
      have hL : 2 ≤ volume dag + 2 := by omega
      have hdag : ∀ nd ∈ dag, (serializeWords (nd.1 :: nd.2.1)).length ≤ volume dag + 2 := fun nd hnd =>
        (code_le_volume nd).trans ((PR.volume_lt_of_mem hnd).le.trans (by omega))
      have hB := vol_of_Bnd (Bnd_iter dag (volume dag + 2) hL hdag root j)
      have hw : wM dag ≤ 2 * volume (dag, root) := by
        have := children_le_volume dag; unfold wM; simp only [volume_pair]; omega
      have hr : root ≤ volume (dag, root) := by simp only [volume_pair, volume_nat]; omega
      have hj' : j ≤ (2 * volume (dag, root) + 2) * (volume (dag, root) + 1) + 1 := by
        unfold fuelM at hj
        have : (wM dag + 2) * (root + 1) ≤ (2 * volume (dag, root) + 2) * (volume (dag, root) + 1) :=
          Nat.mul_le_mul (by omega) (by omega)
        omega
      have hQ : Qv (volume dag + 2) (root + 1 + j) ≤ Qv (Mser (volume (dag, root))) (Mser (volume (dag, root))) :=
        Qv_mono (by unfold Mser; simp only [volume_pair]; omega) (by unfold Mser; omega)
      unfold Gser
      simp only [volume_pair] at hB hQ ⊢
      omega)).comp ((((snd.comp snd).comp snd).comp snd).pair (((snd.comp snd).comp snd).comp fst))).congr
    (fun x => by
      rcases x with ⟨dag, root⟩
      simp only [iter_step]
      rw [(run_root dag root).1, (run_root dag root).2])

def encStrP : PR (fun T : List Str => encStr T) :=
  (((length.comp encNatP).pair flatten).comp append).congr (fun _ => rfl)

/-- **The serializer, realized.** -/
def serOutP : PR (fun x : List ℕ × (List INode × ℕ) => serOut x.1 x.2.1 x.2.2) :=
  (((fst.comp serWords).pair ((snd.comp travP).comp (((fst.comp encNatP).pair (snd.comp encStrP)).comp
    append))).comp append).congr (fun _ => rfl)

end W6.PR

end OPI
end

-- ===== OPI.RepI =====
section

/-!
# First-order DAGs representing programs

`Rep dag i P`: node `i` of the first-order DAG `dag` represents the program tree `P` (its tag and
fields are those of the head of `P`, and its children, at smaller indices, represent the
sub-programs). Then the uniform traversal `travI` computes `programNodeTable P`, so `serOut`
is the packed serialization (`packedSerialization_of_rep`).
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI QAlgorithms.Complexity

variable {N c out : ℕ}

open Classical in
/-- The fields of a gate: kind (`H`, `T`, other) and wires. -/
noncomputable def gfields (g : GateApp htcxGateSet N) : List ℕ :=
  (if g.gate = Gate.ofMatrix1 hadamard then 0 else if g.gate = Gate.ofMatrix1 gateT then 1 else 2) ::
    List.ofFn (fun i => (g.wires i).val)

/-- The fields of a halting node. -/
def haltF {c out : ℕ} (D : BoolCircuit c out) : List ℕ :=
  [D.gates.length] ++ D.gates.flatMap (fun g => [Learning.boolOpCode g.op, g.a, g.b]) ++ List.ofFn D.outputs

/-- The children of a program node. -/
def kids : Prog N c out → List (Prog N c out)
  | .halt _ _ => []
  | .fail => []
  | .gate _ P => [P]
  | .query _ _ _ _ _ _ _ => []
  | .measure _ _ nx => [nx false, nx true]
  | .prepare _ P => [P]
  | .coin _ nx => [nx false, nx true]
  | .setBit _ _ P => [P]
  | .boolean _ _ _ _ P => [P]
  | .branch _ nx => [nx false, nx true]

/-- The tag and fields of a program node. -/
noncomputable def headI : Prog N c out → ℕ × List ℕ
  | .halt D _ => (0, haltF D)
  | .fail => (1, [])
  | .gate g _ => (2, gfields g)
  | .query _ _ _ _ _ _ _ => (3, [])
  | .measure q d _ => (4, [q.val, d.val])
  | .prepare q _ => (5, [q.val])
  | .coin d _ => (6, [d.val])
  | .setBit d b _ => (7, [d.val, if b then 1 else 0])
  | .boolean op d x y _ => (8, [Learning.boolOpCode op, d.val, x.val, y.val])
  | .branch s _ => (9, [s.val])

/-- No oracle queries at the head. -/
def NoQ : Prog N c out → Prop
  | .query _ _ _ _ _ _ _ => False
  | _ => True

/-- **Representation of a program by a first-order DAG node.** -/
inductive Rep (dag : List INode) : ℕ → Prog N c out → Prop
  | mk (i : ℕ) (P : Prog N c out) (cs : List ℕ)
      (hnode : dag[i]? = some ((headI P).1, (headI P).2, cs))
      (hlen : cs.length = (kids P).length) (hlt : ∀ j ∈ cs, j < i)
      (hkids : ∀ l (h1 : l < cs.length) (h2 : l < (kids P).length), Rep dag cs[l] (kids P)[l])
      (hq : NoQ P) : Rep dag i P

/-- Serializing a list of children. -/
noncomputable def pntKids (ps : List (Prog N c out)) (T : List Str) : List ℕ × List Str :=
  ps.foldl (fun acc P => ((acc.1 ++ [(programNodeTable P acc.2).1]), (programNodeTable P acc.2).2)) ([], T)



/-- Memo entries are stably serialized. -/
def MemoR (dag : List INode) (memo : ℕ → Option ℕ) (T : List Str) : Prop :=
  ∀ j k, memo j = some k → ∀ P : Prog N c out, Rep dag j P → ∀ U,
    programNodeTable P (T ++ U) = (k, T ++ U)









/-- The packed program with no oracles. -/
def packP (P : Prog N c out) : PackedMembershipProgram :=
  ⟨0, fun _ => 0, fun _ => false, N, c, out, P⟩



end OPI
end

-- ===== OPI.ISeg =====
section

/-!
# First-order segments

An `ISeg` produces, from the continuation index `k` and the start position `s`, the list of new
nodes (placed at positions `s, s+1, …`). Its entry is the last new node (or `k` if there is
none). `ISeg.Valid sg F`: appending the nodes to any DAG whose node `k` represents `P` yields a
node representing `F P`.
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI QAlgorithms.Complexity

variable {N c out : ℕ}





/-- First-order segments. -/
abbrev ISeg := ℕ → ℕ → List INode

namespace ISeg

/-- The entry node. -/
def entry (sg : ISeg) (k s : ℕ) : ℕ := if (sg k s).length = 0 then k else s + (sg k s).length - 1

/-- Validity with respect to the tree transformer `F`. -/
def Valid (sg : ISeg) (F : Prog N c out → Prog N c out) : Prop :=
  ∀ (dag : List INode) k (P : Prog N c out), Rep dag k P →
    Rep (dag ++ sg k dag.length) (sg.entry k dag.length) (F P)

/-- Composition: `s₂` first (closest to the continuation), then `s₁`. -/
def comp (s₁ s₂ : ISeg) : ISeg := fun k s =>
  s₂ k s ++ s₁ (s₂.entry k s) (s + (s₂ k s).length)





/-- The empty segment. -/
def idI : ISeg := fun _ _ => []



/-- A single node with head `h` and the continuation repeated `ar` times as children. -/
def node (tag : ℕ) (fields : List ℕ) (ar : ℕ) : ISeg := fun k _ => [(tag, fields, List.replicate ar k)]



/-! ### Primitive segments -/

noncomputable def gateI (g : GateApp htcxGateSet N) : ISeg := node 2 (gfields g) 1



def prepareI (q : ℕ) : ISeg := node 5 [q] 1



def setBitI (dst : ℕ) (b : Bool) : ISeg := node 7 [dst, if b then 1 else 0] 1



def measureI (q dst : ℕ) : ISeg := node 4 [q, dst] 2



/-- A gate chain: gate fields in execution order. -/
def chainI : List (List ℕ) → ISeg
  | [] => idI
  | g :: gs => comp (node 2 g 1) (chainI gs)















end ISeg

end OPI
end

-- ===== OPI.IRGates =====
section

/-!
# First-order gates

`gfields` of the elementary gates; reversible gates over `ℕ` (`RN`) and the gate fields of their
compilation, of inverses and of relocations.
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI

variable {N : ℕ}













/-- Reversible gates on natural-number wires: tag (`0` = X, `1` = CNOT, `2` = Toffoli) and wires. -/
abbrev RN := ℕ × List ℕ

def RGate.toN : RGate N → RN
  | .x q => (0, [q.val])
  | .cx c t => (1, [c.val, t.val])
  | .ccx a b t => (2, [a.val, b.val, t.val])

/-- The Toffoli chain on natural-number wires. -/
def tofI (p q r : ℕ) : List (List ℕ) :=
  [[0, r]] ++ ([[1, p], [1, q], [1, r], [2, p, q]] ++ List.replicate 7 [1, q]) ++
    ([[2, p, q], [2, q, r]] ++ List.replicate 7 [1, r]) ++
    ([[2, q, r], [2, p, r]] ++ List.replicate 7 [1, r]) ++
    [[2, p, r], [2, p, r], [2, q, r], [1, r], [2, q, r], [2, p, r]] ++ [[0, r]]

/-- The gate fields of a compiled reversible gate. -/
def rnGates (g : RN) : List (List ℕ) :=
  let a := g.2.getD 0 0
  let b := g.2.getD 1 0
  let t := g.2.getD 2 0
  if g.1 = 0 then [[0, a]] ++ List.replicate 4 [1, a] ++ [[0, a]]
  else if g.1 = 1 then (if a ≠ b then [[2, a, b]] else [])
  else if a ≠ b ∧ a ≠ t ∧ b ≠ t then tofI a b t else []







/-- The inverse of a gate field: `T` becomes `T⁷`. -/
def invF (g : List ℕ) : List (List ℕ) := if g.headD 0 = 1 then List.replicate 7 g else [g]





end OPI
end

-- ===== OPI.IsPR =====
section

/-!
# `IsPR`: existence of polynomial realizers, proved compositionally by `fun_prop`
-/

namespace OPI.W6

open OAI.ThreeMachine.StackCompiler

/-- A function has a polynomial realizer. -/
@[fun_prop]
def IsPR {α β : Type} [Coding α] [Coding β] (f : α → β) : Prop := Nonempty (PR f)

namespace IsPR

variable {α β γ δ : Type} [Coding α] [Coding β] [Coding γ] [Coding δ]







/-! ### Structure -/












/-! ### Natural numbers -/









/-! ### Booleans and branching -/















/-! ### Options -/





/-! ### Lists -/



























/-! ### Folds with a polynomial growth bound -/



end IsPR

end OPI.W6
end

-- ===== OPI.FModel =====
section

/-!
# A computable model of `F_p[X]/(f)` on coefficient lists

Polynomials are lists of natural numbers (coefficients, lowest degree first) read in `ZMod p`
(`toPoly`). Addition, scaling and multiplication are list operations; reduction modulo a monic
`f` (`reduceL`) subtracts multiples of `f`. The field element of a list is `elemL`.
-/

namespace OPI

namespace FM

open Polynomial

variable (p : ℕ)

/-- The polynomial of a coefficient list. -/
noncomputable def toPoly : List ℕ → (ZMod p)[X]
  | [] => 0
  | a :: l => C (a : ZMod p) + X * toPoly l

@[simp] lemma toPoly_nil : toPoly p [] = 0 := rfl
@[simp] lemma toPoly_cons (a : ℕ) (l : List ℕ) : toPoly p (a :: l) = C (a : ZMod p) + X * toPoly p l := rfl

/-- Coefficientwise sum modulo `p`. -/
def addL : List ℕ → List ℕ → List ℕ
  | [], bs => bs
  | as, [] => as
  | a :: as, b :: bs => (a + b) % p :: addL as bs



/-- Scaling by `c` modulo `p`. -/
def scaleL (c : ℕ) (l : List ℕ) : List ℕ := l.map (fun a => c * a % p)



/-- Product. -/
def mulL (a b : List ℕ) : List ℕ := a.foldr (fun ai acc => addL p (scaleL p ai b) (0 :: acc)) []



/-- Difference `a - b` modulo `p`. -/
def subL (a b : List ℕ) : List ℕ := addL p a (scaleL p (p - 1) b)











/-- One reduction step: cancel the top coefficient with a shifted multiple of `f` (coefficients
`fl`, monic of length `e + 1`), and drop it. -/
def redStep (fl : List ℕ) (g : List ℕ) : List ℕ :=
  (subL p g (List.replicate (g.length - fl.length) 0 ++ scaleL p (g.getLastD 0) fl)).dropLast








/-- Full reduction modulo `fl` (monic, of length `e + 1`). -/
def reduceL (fl g : List ℕ) : List ℕ := (redStep p fl)^[g.length - (fl.length - 1)] g







/-- Padding to length `e`. -/
def padL (e : ℕ) (l : List ℕ) : List ℕ := l ++ List.replicate (e - l.length) 0



/-- Product in the field model. -/
def mulF (fl : List ℕ) (a b : List ℕ) : List ℕ := padL (fl.length - 1) (reduceL p fl (mulL p a b))

end FM

/-! ### The bridge to `F_p[X]/(f)` -/

namespace FM

open Polynomial TwoFoldOPI

variable (F : AvgCaseTI.FieldPres)

/-- The coefficient list of `f`. -/
noncomputable def flOf : List ℕ := List.ofFn (fun j : Fin (F.f.natDegree + 1) => (F.f.coeff j).val)









/-- The field element of a coefficient list. -/
noncomputable def elemL (l : List ℕ) : F.F := AdjoinRoot.mk F.f (toPoly F.p l)





end FM

end OPI
end

-- ===== OPI.FOps =====
section

/-!
# Field operations on coordinate lists

`E x` is the list of power-basis coordinates of `x : F_p[X]/(f)`. Addition, subtraction,
multiplication, inversion (by search), and the trace are computed on these lists.
-/

namespace OPI

namespace FM

open Polynomial TwoFoldOPI

/-- Reduced lists: all entries `< p`. -/
def Red (p : ℕ) (l : List ℕ) : Prop := ∀ x ∈ l, x < p

section Red
variable {p : ℕ} (hp : 0 < p)
include hp















end Red



variable (F : AvgCaseTI.FieldPres)




/-- The coordinates of a field element. -/
noncomputable def E (x : F.F) : List ℕ := List.ofFn (fun j : Fin F.f.natDegree => ((Fq.bas F).repr x j).val)

























/-- The coordinates of `0`. -/
def zeroL (n : ℕ) : List ℕ := List.replicate n 0



/-- The coordinates of `X^i`. -/
def unitL (n i : ℕ) : List ℕ := (List.range n).map (fun k => if k = i then 1 else 0)





/-- **Trace** (`Tr x = Σ_i [x X^i]_i`). -/
def trL (p : ℕ) (fl : List ℕ) (a : List ℕ) : ℕ :=
  ((List.range (fl.length - 1)).map (fun i => (mulF p fl a (unitL (fl.length - 1) i)).getD i 0)).sum % p



end FM

end OPI
end

-- ===== OPI.PRField =====
section

/-!
# Realizers of the field model
-/

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI.FM

variable {α β : Type} [Coding α] [Coding β]

/-! ### Remainder and range -/







/-! ### Sum -/



end OPI.W6.IsPR

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI.FM

variable {α : Type} [Coding α]



























/-- The field product with the modulus clamped (equal to `mulF` for `p ≥ 2`). -/
def mulF2 (p : ℕ) (fl a b : List ℕ) : List ℕ := padL (fl.length - 1) (reduceL (max p 2) fl (mulL (max p 2) a b))







/-- The trace with the modulus clamped. -/
def trL2 (p : ℕ) (fl a : List ℕ) : ℕ :=
  ((List.range (fl.length - 1)).map (fun i => (mulF2 p fl a (unitL (fl.length - 1) i)).getD i 0)).sum % p





end OPI.W6.IsPR
end

-- ===== OPI.IRRev =====
section

/-!
# Reversible circuit builders on natural-number wires
-/

namespace OPI

open QAlgorithms OPI.W6

variable {N : ℕ}

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

/-! ### Definitions -/

def mcxN : List ℕ → List ℕ → ℕ → List RN
  | [], _, t => [(0, [t])]
  | [c], _, t => [(1, [c, t])]
  | [c1, c2], _, t => [(2, [c1, c2, t])]
  | c1 :: c2 :: c3 :: cs, a :: as, t => (2, [c1, c2, a]) :: (mcxN (a :: c3 :: cs) as t ++ [(2, [c1, c2, a])])
  | _ :: _ :: _ :: _, [], _ => []



def incrN (cs as : List ℕ) : List ℕ → List RN
  | [] => []
  | a :: r => mcxN (cs ++ r) as a ++ incrN cs as r



def addIntoN (as gs : List ℕ) : List ℕ → List RN
  | [] => []
  | x :: xs => incrN [x] as (gs.take (gs.length - xs.length)) ++ addIntoN as gs xs



def flipZerosN (xs : List ℕ) (bs : List Bool) : List RN :=
  (xs.zip bs).flatMap (fun xb => if xb.2 then [] else [(0, [xb.1])])



def cxOutN (f : ℕ) (ys : List ℕ) (bs : List Bool) : List RN :=
  (ys.zip bs).flatMap (fun yb => if yb.2 then [(1, [f, yb.1])] else [])



def eqFlipN (xs : List ℕ) (bs : List Bool) (as : List ℕ) (f : ℕ) : List RN :=
  flipZerosN xs bs ++ mcxN xs as f ++ flipZerosN xs bs



def lookupN (xs ys as : List ℕ) (f : ℕ) (T : List (List Bool × List Bool)) : List RN :=
  T.flatMap (fun e => eqFlipN xs e.1 as f ++ cxOutN f ys e.2 ++ eqFlipN xs e.1 as f)



def swapRegsN (bs ws : List ℕ) : List RN :=
  (bs.zip ws).flatMap (fun bw => [(1, [bw.1, bw.2]), (1, [bw.2, bw.1]), (1, [bw.1, bw.2])])



end OPI
end

-- ===== OPI.PRRev =====
section

/-!
# Realizers of the reversible circuit builders
-/

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI

variable {α β γ : Type} [Coding α] [Coding β] [Coding γ]



end OPI.W6.IsPR

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI

variable {α β γ : Type} [Coding α] [Coding β] [Coding γ]



/-- Bounded gate lists. -/
def WiresLe (W : ℕ) (L : List RN) : Prop := ∀ g ∈ L, g.1 ≤ 2 ∧ g.2.length ≤ 3 ∧ ∀ w ∈ g.2, w ≤ W

















end OPI.W6.IsPR

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.IRTable =====
section

/-!
# Tables over all bit patterns, with a size budget
-/

namespace OPI

open QAlgorithms OPI.W6

/-- `allPats k` when `2^k ≤ N`. -/
def allPatsB (k N : ℕ) : List (List Bool) := if 2 ^ k ≤ N then allPats k else [[]]







end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI

variable {α : Type} [Coding α]









end OPI.W6.IsPR
end

-- ===== OPI.GradPrep =====
section

/-!
# M5: gradient preparation — the eigenbasis of `INC`

On a `b`-qubit register, `ê_x = 2^{-b/2} Σ_g e^{-2πi x g/2^b} |g⟩` (`g` read as a number). Then

* `ê_1 = |G_b⟩` (`gradVec`);
* shifting the register by `v` multiplies `ê_x` by `e^{2πi x v/2^b}`;
* precomposing with the multiplication `g ↦ u g (mod 2^b)` turns `ê_x` into `ê_{xu}`.
-/

namespace OPI

open QAlgorithms

variable {b : ℕ}

/-- `e^{2πi n/2^b}` for an integer `n`. -/
noncomputable def ex (b : ℕ) (n : ℤ) : ℂ := Complex.exp (2 * Real.pi * Complex.I * n / (2 ^ b : ℂ))







/-- The eigenvector `ê_x` of the increment. -/
noncomputable def eigv (b x : ℕ) (g : Qubits b) : ℂ :=
  ((Real.sqrt (2 ^ b) : ℂ))⁻¹ * ex b (-((x : ℤ) * bitsToNat g))









/-! ## Kickback on a general eigenvector -/

section Kick

variable {N : ℕ}

/-- A state `ê_x ⊗ ψ(rest)`. -/
noncomputable def withEig (w : Fin b ↪ Fin N) (x : ℕ) (ψ : (Outside w → Bool) → ℂ) : Qubits N → ℂ :=
  fun z => eigv b x (z ∘ w) * ψ (fun o => z o.1)







end Kick

/-! ## The controlled increment by `2^e` as a kickback -/

section Incr

variable {N : ℕ}



end Incr

/-! ## One-qubit gates on the rest, and the Hadamard test -/

section HTest

variable {N : ℕ}







/-- The Hadamard test circuit: `H_c`, controlled `+2^e`, `T_c^k`, `H_c`. -/
noncomputable def hTest (w : Fin b ↪ Fin N) (c : Fin N) (as : List (Fin N)) (e k : ℕ) :
    Circuit htcxGateSet N :=
  [hApp c] ++ revCirc (incr [c] as ((List.ofFn w).take ((List.ofFn w).length - e))) ++
    List.replicate k (tApp c) ++ [hApp c]

/-- The eigenvalue seen by the test. -/
noncomputable def testPhase (b x e k : ℕ) : ℂ :=
  ex b ((x * 2 ^ e : ℕ) : ℤ) * Complex.exp (Complex.I * Real.pi / 4) ^ k



end HTest

/-! ## One measured test -/

section TestLaw

variable {N c' out : ℕ}



/-- One measured Hadamard test with the control restored to `0` and the outcome bit cleared. -/
noncomputable def testProg (w : Fin b ↪ Fin N) (c : Fin N) (as : List (Fin N)) (e k : ℕ)
    (dst : Fin c') (P : Bool → Prog N c' out) : Prog N c' out :=
  (circSeg (hTest w c as e k)).prog (.measure c dst fun r =>
    if r then (circSeg (revCirc [RGate.x c])).prog (.setBit dst false (P true))
    else .setBit dst false (P false))



end TestLaw

end OPI
end

-- ===== OPI.GradLB =====
section

/-!
# M5: gradient preparation — lower bounds over eigen-labels

States `Σ_x c_x ê_x ⊗ ψ` (labels `x ∈ ZMod 2^b`). A lower bound of the law of a continuation by a
diagonal form `Σ_x λ_x |c_x|²` propagates through Hadamard tests and relabelings; at the end a
density split turns it into a bound by the law on `ê_1`.
-/

namespace OPI

open QAlgorithms

variable {N c' out : ℕ}

/-! ## The density split -/





/-! ## Sums over labels -/

variable {b : ℕ} (w : Fin b ↪ Fin N) (ψ : (Outside w → Bool) → ℂ)

/-- `Σ_x c_x ê_x ⊗ ψ`. -/
noncomputable def eSum (c : ZMod (2 ^ b) → ℂ) : Qubits N → ℂ :=
  ∑ x, c x • withEig w x.val ψ

/-- The diagonal lower bound `Σ_x λ_x |c_x|² ≤ law(Σ_x c_x ê_x ⊗ ψ)`. -/
def LB (event : Option (Fin out → Bool) → Prop) (P : Prog N c' out) (lam : ZMod (2 ^ b) → ℝ) : Prop :=
  ∀ (c : ZMod (2 ^ b) → ℂ) (mem : Fin c' → Bool),
    ∑ x, lam x * Complex.normSq (c x) ≤ lawP P event (eSum w ψ c) mem

variable {w ψ}









/-! ## The Hadamard test on label sums -/

section Test

variable (w) in
/-- The two branch maps of a measured test. -/
noncomputable def tK (c : Fin N) (as : List (Fin N)) (e k : ℕ) (r : Bool) (f : Qubits N → ℂ) : Qubits N → ℂ :=
  if r then (Circuit.unitary (revCirc [RGate.x c])).mulVec ((qubitOp1 (measProj true) c).mulVec
      ((Circuit.unitary (hTest w c as e k)).mulVec f))
  else (qubitOp1 (measProj false) c).mulVec ((Circuit.unitary (hTest w c as e k)).mulVec f)





/-- The amplitude of outcome `r`. -/
noncomputable def tAmp (b x e k : ℕ) (r : Bool) : ℂ :=
  if r then (1 - testPhase b x e k) / 2 else (1 + testPhase b x e k) / 2





end Test

end OPI
end

-- ===== OPI.GradMaj =====
section

/-!
# M5: gradient preparation — a majority of Hadamard tests

`majP r s` runs `r` more tests, having counted `s` outcomes `1` so far, and then continues with
`P1` if the majority of the `Nt` outcomes is `1` and with `P0` otherwise. With wrong-outcome
probability `p` per test, the potential `G r w = (1 + 15 p)^r 4^{2w − Nt}` bounds the probability
that the decision is wrong (`w` counts wrong outcomes so far).
-/

namespace OPI

open QAlgorithms

variable {N c' out b : ℕ} {w : Fin b ↪ Fin N} {ψ : (Outside w → Bool) → ℂ}

/-- The majority stage. -/
noncomputable def majP (w : Fin b ↪ Fin N) (c : Fin N) (as : List (Fin N)) (e k : ℕ) (dst : Fin c')
    (Nt : ℕ) (P0 P1 : Prog N c' out) : ℕ → ℕ → Prog N c' out
  | 0, s => if Nt < 2 * s then P1 else P0
  | r + 1, s => testProg w c as e k dst (fun o => majP w c as e k dst Nt P0 P1 r (s + if o then 1 else 0))

/-- The potential. -/
noncomputable def potG (p : ℝ) (Nt r : ℕ) (wr : ℤ) : ℝ := (1 + 15 * p) ^ r * (4 : ℝ) ^ (2 * wr - Nt)

/-- Wrong outcomes so far, for true bit `β`, `r` tests remaining and `s` ones seen. -/
def wrongCnt (β : Bool) (Nt r s : ℕ) : ℤ := if β then (Nt : ℤ) - r - s else s







end OPI
end

-- ===== OPI.GradMul =====
section

/-!
# M5: gradient preparation — in-place multiplication by `1 + 2^j`

For control bits `t = b−1−j, …, 0`, add `2^{t+j}` to the register, controlled by bit `t`; the addition
only touches bits above `t`, so later controls are unchanged. The result is
`z ↦ (1 + 2^j) z mod 2^b`.
-/

namespace OPI

open QAlgorithms

variable {N : ℕ}

/-- One step: controlled by bit `t`, add `2^{j−1}` to the bits above `t`. -/
def mStep (as R : List (Fin N)) (j t : ℕ) : List (RGate N) :=
  match R.drop (R.length - 1 - t) with
  | ctl :: _ => incr [ctl] as ((R.take (R.length - 1 - t)).take ((R.length - 1 - t) - (j - 1)))
  | [] => []

/-- Steps for the controls `t−1, …, 0`. -/
def mulGates (as R : List (Fin N)) (j : ℕ) : ℕ → List (RGate N)
  | 0 => []
  | t + 1 => mStep as R j t ++ mulGates as R j t







/-! ## Permutations on clean states -/



variable {b : ℕ}

/-- Multiplication of a bit string by `u` (mod `2^b`), with inverse `u'`. -/
def mulBitsEquiv (b u u' : ℕ) (h : u * u' % 2 ^ b = 1 % 2 ^ b) : Qubits b ≃ Qubits b where
  toFun g := natToBits b (u * bitsToNat g % 2 ^ b)
  invFun g := natToBits b (u' * bitsToNat g % 2 ^ b)
  left_inv g := by
    simp only [bitsToNat_natToBits, Nat.mod_mod, Nat.mul_mod_mod]
    rw [← mul_assoc, Nat.mul_mod, mul_comm u' u, h, ← Nat.mul_mod, one_mul,
      Nat.mod_eq_of_lt (bitsToNat_lt g), natToBits_bitsToNat]
  right_inv g := by
    simp only [bitsToNat_natToBits, Nat.mod_mod, Nat.mul_mod_mod]
    rw [← mul_assoc, Nat.mul_mod, h, ← Nat.mul_mod, one_mul,
      Nat.mod_eq_of_lt (bitsToNat_lt g), natToBits_bitsToNat]

/-- Multiply the register `w` by `u`. -/
noncomputable def mulEquiv (w : Fin b ↪ Fin N) (u u' : ℕ) (h : u * u' % 2 ^ b = 1 % 2 ^ b) :
    Qubits N ≃ Qubits N :=
  (splitEquiv w).trans ((Equiv.prodCongr (mulBitsEquiv b u u' h) (Equiv.refl _)).trans (splitEquiv w).symm)













end OPI
end

-- ===== OPI.IRRev2 =====
section

/-!
# More reversible builders on natural-number wires (tables as data)
-/

namespace OPI

open QAlgorithms OPI.W6

variable {N : ℕ}

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

/-! ### Function tables and permutation gadgets -/



def permGadN (cs B Z as : List ℕ) (f : ℕ) (T1 T2 : List (List Bool × List Bool)) : List RN :=
  lookupN (cs ++ B) Z as f T1 ++ lookupN (cs ++ Z) B as f T2 ++ swapRegsN B Z

/-- The two tables of a permutation gadget. -/
def pgTab (k : ℕ) (cl : ℕ) (F : List Bool → List Bool → List Bool) : List (List Bool × List Bool) :=
  funTable k (fun pat => F (pat.take cl) (pat.drop cl))



/-! ### Multipliers -/

def mStepN (as R : List ℕ) (j t : ℕ) : List RN :=
  if (R.drop (R.length - 1 - t)).isEmpty then []
  else incrN [(R.drop (R.length - 1 - t)).headD 0] as
    ((R.take (R.length - 1 - t)).take ((R.length - 1 - t) - (j - 1)))



def mulGatesN (as R : List ℕ) (j : ℕ) : ℕ → List RN
  | 0 => []
  | t + 1 => mStepN as R j t ++ mulGatesN as R j t



/-! ### Controlled shifts and readout -/

/-- The tables of one controlled shift by `k`. -/
def csTab (p w k : ℕ) : List (List Bool × List Bool) × List (List Bool × List Bool) :=
  (pgTab (1 + w) 1 (csF p w k), pgTab (1 + w) 1 (csF p w (p - k % p)))

def csListN (Bl Z as : List ℕ) (f : ℕ) (L : List (ℕ × (List (List Bool × List Bool) × List (List Bool × List Bool)))) :
    List RN :=
  L.flatMap (fun ck => permGadN [ck.1] Bl Z as f ck.2.1 ck.2.2)



def rdListN (p : ℕ) (ctrlL top : List ℕ) (lh : ℕ) (lrest as : List ℕ) : List RN :=
  (0, [lh]) :: (List.replicate p (addIntoN as (top ++ lh :: lrest) ctrlL)).flatten



def tauListN (p : ℕ) (ctrlL top : List ℕ) (lh : ℕ) (lrest Al Z as : List ℕ) (f : ℕ)
    (T1 T2 : List (List Bool × List Bool)) : List RN :=
  rdListN p ctrlL top lh lrest as ++ permGadN top Al Z as f T1 T2 ++ (rdListN p ctrlL top lh lrest as).reverse



/-! ### Table phases, lookups of predicates, compiled programs -/

def tablePhaseGatesN (n b : ℕ) (xs scr as : List ℕ) (f : ℕ) (T : List (List Bool × List Bool)) : List RN :=
  lookupN xs scr as f T ++ addIntoN as ((List.range b).map (n + ·)) scr ++ lookupN xs scr as f T











end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI

variable {α : Type} [Coding α]

abbrev Tab := List (List Bool × List Bool)

















end OPI.W6.IsPR
end

-- ===== OPI.BitsPR =====
section

/-!
# Bit lists: values, expansions, long division, with realizers
-/

namespace OPI

open QAlgorithms OPI.W6













end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI

variable {α : Type} [Coding α]









/-- Saturating value of a bit list. -/
def bitsValS (N : ℕ) (l : List Bool) : ℕ := l.foldl (fun v b => min (2 * v + if b then 1 else 0) N) 0





end OPI.W6.IsPR

namespace OPI

/-- The step of long division. -/
def ldStep (p : ℕ) (s : ℕ × List Bool) : ℕ × List Bool :=
  ((2 * s.1) % max p 1, s.2 ++ [decide (max p 1 ≤ 2 * s.1)])

/-- The `b` bits of `2^b t / p` by long division. -/
def ldivBits (b t p : ℕ) : List Bool := ((ldStep p)^[b] (t, [])).2





end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI

variable {α : Type} [Coding α]





end OPI.W6.IsPR
end

-- ===== OPI.FBits =====
section

/-!
# Field elements as bit patterns, in coordinates
-/

namespace OPI

namespace FM

open TwoFoldOPI QAlgorithms

/-- Encoding of a coordinate list. -/
def encL (w : ℕ) (cs : List ℕ) : List Bool := cs.flatMap (natBits w)

/-- The blocks of a bit list. -/
def blocksL (e w : ℕ) (l : List Bool) : List (List Bool) := (List.range e).map (fun j => (l.drop (j * w)).take w)

/-- Decoding to coordinates. -/
def decL (p e w : ℕ) (l : List Bool) : List ℕ := (blocksL e w l).map (fun b => bitsVal b % p)

variable (F : AvgCaseTI.FieldPres)







end FM

end OPI

namespace OPI

namespace FM

open TwoFoldOPI QAlgorithms

variable (F : AvgCaseTI.FieldPres)











/-- Coordinates of the trace-dual encoding. -/
def scoL (p : ℕ) (fl : List ℕ) (a : List ℕ) : List ℕ :=
  (List.range (fl.length - 1)).map (fun j => trL p fl (mulF p fl a (unitL (fl.length - 1) j)))



end FM

end OPI
end

-- ===== OPI.FTables =====
section

/-!
# Field tables in coordinates
-/

namespace OPI

namespace FM

open TwoFoldOPI QAlgorithms
open scoped Classical



/-- Saturating decoding. -/
def decLS (p e w : ℕ) (l : List Bool) : List ℕ := (blocksL e w l).map (fun b => W6.IsPR.bitsValS (2 * p) b % p)

/-- Validity test. -/
def validL (p e w : ℕ) (l : List Bool) : Bool :=
  (blocksL e w l).all (fun b => decide (W6.IsPR.bitsValS (2 * p) b < p))



variable (F : AvgCaseTI.FieldPres)







/-! ### Membership predicates -/

/-- `memT` of a symbol job: valid and different from `β`. -/
def memSL (p e w : ℕ) (βE : List ℕ) (l : List Bool) : Bool :=
  validL p e w l && !decide (decLS p e w l = βE)



/-! ### Shifts by field multiples -/

/-- `B ↦ B + s·c` on valid `B`. -/
def fShiftL (p e w : ℕ) (fl sE : List ℕ) (c B : List Bool) : List Bool :=
  if validL p e w B then encL w (addL p (decLS p e w B) (mulF p fl sE (decLS p e w c))) else B



/-! ### Affine maps of a symbol -/

/-- `x ↦ β - x` on encodings. -/
def pFunL (p e w : ℕ) (βE : List ℕ) (bits : List Bool) : List Bool :=
  if bits.length = e * w ∧ validL p e w bits = true then encL w (subL p βE (decLS p e w bits)) else bits





end FM

end OPI

namespace OPI

namespace FM

open TwoFoldOPI QAlgorithms
open scoped Classical

variable (F : AvgCaseTI.FieldPres)

/-! ### Trace-dual re-encoding -/

/-- `RL` in coordinates. -/
def RLL (p e w : ℕ) (fl : List ℕ) (y : List Bool) : List Bool :=
  if y.length = e * w ∧ validL p e w y = true then encL w (scoL p fl (decLS p e w y)) else y



/-- All coordinate lists of length `e` with entries `< p`. -/
def allL (p : ℕ) : ℕ → List (List ℕ)
  | 0 => [[]]
  | e + 1 => (List.range p).flatMap (fun a => (allL p e).map (a :: ·))







/-- `RLinv` in coordinates: search for the preimage. -/
def RLinvL (p e w : ℕ) (fl : List ℕ) (y : List Bool) : List Bool :=
  if y.length = e * w ∧ validL p e w y = true then
    encL w (((allL p e).find? (fun a => decide (scoL p fl a = decLS p e w y))).getD [])
  else y







end FM

end OPI
end

-- ===== OPI.FTablesPR =====
section

/-!
# Realizers of the field tables
-/

namespace OPI

namespace FM

open TwoFoldOPI QAlgorithms W6

/-- The product with the modulus clamped at `2`. -/
def mulM (p : ℕ) (fl a b : List ℕ) : List ℕ := mulF (max p 2) fl a b
/-- The trace with the modulus clamped at `2`. -/
def trM (p : ℕ) (fl a : List ℕ) : ℕ := trL (max p 2) fl a




/-- Realizable versions of the table twins. -/
def scoM (p : ℕ) (fl a : List ℕ) : List ℕ :=
  (List.range (fl.length - 1)).map (fun j => trM p fl (mulM p fl a (unitL (fl.length - 1) j)))

def fShiftM (p e w : ℕ) (fl sE : List ℕ) (c B : List Bool) : List Bool :=
  if validL p e w B then encL w (addL p (decLS p e w B) (mulM p fl sE (decLS p e w c))) else B

def RLM (p e w : ℕ) (fl : List ℕ) (y : List Bool) : List Bool :=
  if y.length = e * w ∧ validL p e w y = true then encL w (scoM p fl (decLS p e w y)) else y

def RLinvM (p e w : ℕ) (fl : List ℕ) (y : List Bool) : List Bool :=
  if y.length = e * w ∧ validL p e w y = true then
    encL w (((allL p e).find? (fun a => decide (scoM p fl a = decLS p e w y))).getD [])
  else y









/-! ### Phase-table entries and shifts -/

/-- The `zTab` entry of a pattern `r ++ s`. -/
def zEntry (p e w b : ℕ) (fl : List ℕ) (pat : List Bool) : List Bool :=
  ldivBits b (trM p fl (mulM p fl (decLS p e w (pat.take (e * w))) (decLS p e w (pat.drop (e * w))))) p



/-- Shift of a `w`-bit value by `k` modulo `p`. -/
def shiftLN (p w k : ℕ) (y : List Bool) : List Bool :=
  if IsPR.bitsValS (2 * p) y < p then natBits w ((IsPR.bitsValS (2 * p) y + k) % p) else y

/-- `bitsVal c mod p` by Horner modulo `p`. -/
def bitsValMod (p : ℕ) (c : List Bool) : ℕ := c.foldl (fun v b => (2 * v + if b then 1 else 0) % p) 0



variable (F : AvgCaseTI.FieldPres)







end FM

end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI OPI.FM

variable {α β : Type} [Coding α] [Coding β]























end OPI.W6.IsPR

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI OPI.FM

variable {α : Type} [Coding α]























end OPI.W6.IsPR

namespace OPI

namespace FM

/-- `allL p e` when `p^e ≤ N`. -/
def allLB (p e N : ℕ) : List (List ℕ) := if p ^ e ≤ N then allL p e else [[]]



/-- `RLinv` with the search space bounded by `N`. -/
def RLinvB (p e w N : ℕ) (fl : List ℕ) (y : List Bool) : List Bool :=
  if y.length = e * w ∧ validL p e w y = true then
    encL w (((allLB p e N).find? (fun a => decide (scoM p fl a = decLS p e w y))).getD [])
  else y



end FM

end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI OPI.FM

variable {α : Type} [Coding α]









end OPI.W6.IsPR
end

-- ===== OPI.IRPrepCirc =====
section

/-!
# First-order twins of the preparation circuits

* `shGad`, `linGad`: permutation gadgets with the field-dependent tables `shTab` (parameters);
* `linPairs` ↦ `linPairsN kd m pivN`;
* `linCirc` ↦ `linCircN RrW pivN kd m TG Z as f`, with the wire data `RrW = [vl (ofFn (Rr i))]_i`,
  `pivN = [piv j]_j` and the table matrix `TG = [[shTab F L |Z| (G j i)]_i]_j` (field data, a parameter);
* `tpg`, `phCirc` ↦ `tpgN`, `phCircN`, with the table `zTab F b` as a parameter.
-/

namespace OPI

namespace SymEnc

open QAlgorithms TwoFoldOPI OPI.W6

variable {F : AvgCaseTI.FieldPres} {n : ℕ}

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

/-- Tables of bit patterns. -/
abbrev PTab := List (List Bool × List Bool)

/-- The two tables of the shift gadget `R_i += s · dec c` (control length `ol`, scratch length `zl`).
This is field data: it is a parameter of the circuit twins. -/
noncomputable def shTab (F : AvgCaseTI.FieldPres) (ol zl : ℕ) (s : F.F) : PTab × PTab :=
  (pgTab (ol + bitsPerSymbol F) ol (fShift F s), pgTab (ol + zl) ol (fShift F (-s)))



section Lin

variable {m kd : ℕ}

/-- The wire lists of the registers `R_i`. -/
def RrW (Rr : Fin m → (Fin (bitsPerSymbol F) ↪ Fin n)) : List (List ℕ) := List.ofFn fun i => vl (List.ofFn (Rr i))

/-- The pivot columns. -/
def pivW (piv : Fin kd → Fin m) : List ℕ := List.ofFn fun j => (piv j).val

/-- The table matrix of the linear map: entry `(j, i)` holds the tables of the shift by `G j i`. -/
noncomputable def TGW (G : Fin kd → Fin m → F.F) (zl : ℕ) : List (List (PTab × PTab)) :=
  List.ofFn fun j => List.ofFn fun i => shTab F (bitsPerSymbol F) zl (G j i)



end Lin

/-- The shift pairs on natural numbers: rows `j < kd`, non-pivot columns `i < m`. -/
def linPairsN (kd m : ℕ) (pivN : List ℕ) : List (ℕ × ℕ) :=
  (List.range kd).flatMap fun j => ((List.range m).filter fun i => !(pivN.any (· == i))).map fun i => (j, i)



/-- **The linear-map circuit on natural numbers.** -/
def linCircN (RrW : List (List ℕ)) (pivN : List ℕ) (kd m : ℕ) (TG : List (List (PTab × PTab)))
    (Z as : List ℕ) (f : ℕ) : List RN :=
  (linPairsN kd m pivN).flatMap fun p =>
    permGadN (RrW.getD (pivN.getD p.1 0) []) (RrW.getD p.2 []) Z as f ((TG.getD p.1 []).getD p.2 ([], [])).1
      ((TG.getD p.1 []).getD p.2 ([], [])).2





/-! ### The phase circuit -/

/-- The wire lists of the `S` registers. -/
def SW {m : ℕ} (reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n) : List (List ℕ) :=
  List.ofFn fun i => vl (List.ofFn (bReg reg i false))

/-- The table-phase gates of coordinate `i` on natural numbers. -/
def tpgN (n b : ℕ) (RrW SW : List (List ℕ)) (scr as : List ℕ) (f : ℕ) (T : PTab) (i : ℕ) : List RN :=
  tablePhaseGatesN n b (RrW.getD i [] ++ SW.getD i []) scr as f T



/-- **The phase circuit on natural numbers** (coordinates in reverse order). -/
def phCircN (n b : ℕ) (RrW SW : List (List ℕ)) (scr as : List ℕ) (f : ℕ) (T : PTab) (is : List ℕ) :
    List (List ℕ) :=
  is.reverse.flatMap fun i => (tpgN n b RrW SW scr as f T i).flatMap rnGates





end SymEnc

end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI OPI.SymEnc

variable {α : Type} [Coding α]















end OPI.W6.IsPR
end

-- ===== OPI.ISeg2 =====
section

/-!
# Segments with two continuations
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI

variable {N c out : ℕ}

/-- Two-continuation segments: continuations `k₀, k₁`, start position. -/
abbrev ISeg2 := ℕ → ℕ → ℕ → List INode

namespace ISeg2

def entry (sg : ISeg2) (k0 k1 s : ℕ) : ℕ := s + (sg k0 k1 s).length - 1

/-- Validity: nonempty, and the entry represents `F P₀ P₁`. -/
def Valid (sg : ISeg2) (F : Prog N c out → Prog N c out → Prog N c out) : Prop :=
  ∀ (dag : List INode) k0 k1 (P0 P1 : Prog N c out), Rep dag k0 P0 → Rep dag k1 P1 →
    (sg k0 k1 dag.length) ≠ [] ∧ Rep (dag ++ sg k0 k1 dag.length) (sg.entry k0 k1 dag.length) (F P0 P1)

/-- A node whose two children are segments on the two continuations. -/
def twoK (tag : ℕ) (fields : List ℕ) (s₀ s₁ : ISeg) : ISeg2 := fun k0 k1 s =>
  s₀ k0 s ++ s₁ k1 (s + (s₀ k0 s).length) ++
    [(tag, fields, [s₀.entry k0 s, s₁.entry k1 (s + (s₀ k0 s).length)])]



/-- Measurement with outcome-dependent continuations. -/
def measK (q dst : ℕ) (s₀ s₁ : ISeg) : ISeg2 := twoK 4 [q, dst] s₀ s₁



/-- Precompose a one-continuation segment. -/
def pre (s : ISeg) (sg : ISeg2) : ISeg2 := fun k0 k1 st =>
  sg k0 k1 st ++ s (sg.entry k0 k1 st) (st + (sg k0 k1 st).length)



end ISeg2

end OPI
end

-- ===== OPI.CtrlRus =====
section

/-!
# Resets and repeat-until-success loops as first-order segments
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI

variable {N c out : ℕ}

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

/-- Reset a register. -/
def resetsI : List ℕ → ISeg
  | [] => ISeg.idI
  | q :: xs => (ISeg.prepareI q).comp (resetsI xs)



/-- The `fail` node. -/
def failS : ISeg := ISeg.node 1 [] 0



/-- Append a two-continuation block whose continuations are the segment's entry and the outer
continuation. -/
def then2 (sg : ISeg) (B : ISeg2) : ISeg := fun k st =>
  sg k st ++ B (sg.entry k st) k (st + (sg k st).length)





/-- One attempt: the attempt circuit `A`, measurement of `fl`; on success the uncomputation `U`,
on failure a reset of `xs`. -/
def rusBlk (A U : List (List ℕ)) (xs : List ℕ) (fl dst : ℕ) : ISeg2 :=
  ISeg2.pre (ISeg.chainI A) (ISeg2.measK fl dst (resetsI xs) (ISeg.chainI U))

/-- `R` attempts, then `fail`. -/
def rusI (A U : List (List ℕ)) (xs : List ℕ) (fl dst : ℕ) : ℕ → ISeg
  | 0 => failS
  | R + 1 => then2 (rusI A U xs fl dst R) (rusBlk A U xs fl dst)



end OPI
end

-- ===== OPI.CtrlTrial =====
section

/-!
# Trials, retries and readout as first-order segments
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI

variable {N c out : ℕ}

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

/-- A two-continuation block used with both continuations equal. -/
def diag (B : ISeg2) : ISeg := fun k st => B k k st



/-- A measurement whose `false` child is a segment and whose `true` child is the continuation. -/
def measC (q d : ℕ) (s : ISeg) : ISeg := diag (ISeg2.measK q d s ISeg.idI)



/-- `zeroTest`: test the wires `qs`, accepting into `A` (a constant segment) when all are zero. -/
def zeroTestI (dz : ℕ) (Acc : ISeg) : List ℕ → ISeg
  | [] => Acc
  | q :: qs => measC q dz (zeroTestI dz Acc qs)



/-- The halting node (fields of the readout circuit). -/
def haltS (fs : List ℕ) : ISeg := ISeg.node 0 fs 0



/-- Measure all of a list. -/
def measAllI : List (ℕ × ℕ) → ISeg
  | [] => ISeg.idI
  | (q, d) :: L => (ISeg.measureI q d).comp (measAllI L)



/-- Retries: `T` applied `K` times to `fail`. -/
def retryI (T : ISeg) : ℕ → ISeg
  | 0 => failS
  | K + 1 => T.comp (retryI T K)



/-- One trial. -/
def trialI (preS : ISeg) (C : List (List ℕ)) (dz : ℕ) (Rw : List ℕ) (Acc : ISeg) (sys : List ℕ) : ISeg :=
  preS.comp ((ISeg.chainI C).comp ((zeroTestI dz Acc Rw).comp (resetsI sys)))



/-! ### Chains of repeat-until-success stages -/

/-- A stage of the chain: attempt gates, uncomputation gates, reset wires. -/
abbrev RusData := List (List ℕ) × List (List ℕ) × List ℕ

/-- Chain of stages (first stage outermost). -/
def rusChainI (fl dst R : ℕ) : List RusData → ISeg
  | [] => ISeg.idI
  | j :: js => (rusI j.1 j.2.1 j.2.2 fl dst R).comp (rusChainI fl dst R js)

/-- The data of a job. -/
noncomputable def rjData {n b : ℕ} (fl f0 : Fin n) (as : List (Fin n)) (j : RJob n) : RusData :=
  let xs := List.ofFn (j.w.trans (sysEmb (b := b)))
  (((hLayer xs ++ revCirc (rusLook xs (Fin.castAdd b fl) (Fin.castAdd b f0) (as.map (Fin.castAdd b)) j.memT)).map
      gfields),
    ((revCirc (rusLook xs (Fin.castAdd b fl) (Fin.castAdd b f0) (as.map (Fin.castAdd b)) j.memT)).map gfields),
    vl xs)



end OPI
end

-- ===== OPI.IRPrepSeg =====
section

/-!
# Realizers of the generic segment builders

`SegPR S`: the node list `S a k s` of a segment family is realizable as a function of
`(a, k, s)`. Realizers for `ISeg.comp`, `ISeg.entry`, `ISeg.node`, gate chains (`ISeg.chainI`),
resets (`resetsI`), the two-continuation blocks (`ISeg2.twoK`, `ISeg2.measK`, `ISeg2.pre`, `then2`),
repeat-until-success loops (`rusBlk`, `rusI`) and chains of them (`rusChainI`).
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI

/-! ### Chains of single-child nodes and closed-form lengths -/

/-- A chain of single-child nodes with a common tag (first entry outermost). -/
def chainT (tag : ℕ) : List (List ℕ) → ISeg
  | [] => ISeg.idI
  | g :: gs => ISeg.comp (ISeg.node tag g 1) (chainT tag gs)















/-- The length of a repeat-until-success block. -/
def blkLen (A U : List (List ℕ)) (xs : List ℕ) : ℕ := xs.length + U.length + 1 + A.length







/-- The length of a chain stage. -/
def stageLen (R : ℕ) (j : RusData) : ℕ := 1 + R * blkLen j.1 j.2.1 j.2.2





end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI

variable {α β : Type} [Coding α] [Coding β]

/-- A realizable segment family: its nodes as a function of `(a, k, s)`. -/
def SegPR (S : α → ISeg) : Prop := IsPR (fun p : α × ℕ × ℕ => S p.1 p.2.1 p.2.2)

/-- A realizable family of two-continuation segments. -/
def Seg2PR (S : α → ISeg2) : Prop := IsPR (fun p : α × ℕ × ℕ × ℕ => S p.1 p.2.1 p.2.2.1 p.2.2.2)





















/-! ### Chains -/







/-! ### Two-continuation blocks -/









/-! ### Repeat-until-success -/

/-- The data of a repeat-until-success loop. -/
abbrev RusArgs := List (List ℕ) × List (List ℕ) × List ℕ × ℕ × ℕ











end OPI.W6.IsPR
end

-- ===== OPI.IRPrepJobs =====
section

/-!
# The repeat-until-success jobs of the preparation as natural-number data

A job `j` enters the chain through its wire list `vl (ofFn (j.w.trans sysEmb))` and its lookup table
`funTable j.k (fun v => [j.memT v])` (`jobW`). For the jobs of the preparation (`allJobs`):

* pivot jobs `pJob`: wires `RrW[piv j]`, table `TpF F` (valid symbols);
* resource jobs `rJob` over `resAll D`: wires of the resource registers (`resAllN`), table `TrF F`
  (values `< p` on `Fq.w F` bits);
* `S` jobs `sJob`: wires `SW[i]`, tables `TsF F β` (valid symbols `≠ β i`).

The tables are field data and stay parameters. `rjDataN` is the twin of `rjData` (CtrlTrial).
-/

namespace OPI

namespace SymEnc

open QAlgorithms TwoFoldOPI OPI.W6

variable {F : AvgCaseTI.FieldPres} {n : ℕ}

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

/-! ### Resource wires -/

/-- The wires of a factor. -/
def resW (r : Res n) : List ℕ := vl (List.ofFn r.w)

/-- The resource wires of a `QFT_q` gadget. -/
def gsW {b t : ℕ} (Q : QQ n b F t) : List (List ℕ) := Q.Gs.map fun G => vl (List.ofFn G.bE)



/-- The resources of a coordinate on natural numbers. -/
def resCN (wf wt : List (List ℕ)) : List (List ℕ) := wf ++ wt

/-- The resource wires of all gadgets, per coordinate `(c = false, c = true)`. -/
def QWof {m b t : ℕ} {reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n} (D : RealDec F reg b t) :
    List (List (List ℕ) × List (List ℕ)) :=
  List.ofFn fun i => (gsW (D.Q i false), gsW (D.Q i true))



/-- All resources on natural numbers. -/
def resAllN (QW : List (List (List ℕ) × List (List ℕ))) : List (List ℕ) := QW.flatMap fun q => resCN q.1 q.2





/-! ### Jobs -/

/-- The natural-number data of a job: wires (after `sysEmb`) and lookup table. -/
def jobW {b : ℕ} (j : RJob n) : List ℕ × PTab :=
  (vl (List.ofFn (j.w.trans (sysEmb (n := n) (b := b)))), funTable j.k (fun v => [j.memT v]))



open Classical in
/-- The table of the pivot jobs. -/
noncomputable def TpF (F : AvgCaseTI.FieldPres) : PTab :=
  funTable (bitsPerSymbol F) (fun v => [decide (Fq.Valid F (toQ F v))])

open Classical in
/-- The table of the resource jobs. -/
noncomputable def TrF (F : AvgCaseTI.FieldPres) : PTab :=
  funTable (Fq.w F) (fun v => [decide (bitsVal v < F.p)])

open Classical in
/-- The tables of the `S` jobs. -/
noncomputable def TsF {m : ℕ} (F : AvgCaseTI.FieldPres) (β : Fin m → F.F) : List PTab :=
  List.ofFn fun i => funTable (bitsPerSymbol F)
    (fun v => [decide (Fq.Valid F (toQ F v) ∧ decodeElem F (toQ F v) ≠ β i)])

/-- **All jobs on natural numbers**: pivots, resources, `S`. -/
def allJobsN (RrW : List (List ℕ)) (pivN : List ℕ) (resW SW : List (List ℕ)) (Tp Tr : PTab) (Ts : List PTab) :
    List (List ℕ × PTab) :=
  pivN.map (fun j => (RrW.getD j [], Tp)) ++ resW.map (fun w => (w, Tr)) ++ SW.zip Ts









/-! ### The data of a repeat-until-success stage -/

/-- **Twin of `rjData`**: attempt gates, uncomputation gates, reset wires. -/
def rjDataN (xs : List ℕ) (T : PTab) (fl f0 : ℕ) (as : List ℕ) : RusData :=
  (xs.map (fun q => [0, q]) ++ (lookupN xs [fl] as f0 T).flatMap rnGates,
    (lookupN xs [fl] as f0 T).flatMap rnGates, xs)







end SymEnc

end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI OPI.SymEnc

variable {α : Type} [Coding α]







end OPI.W6.IsPR
end

-- ===== OPI.IRPrepLaw =====
section

/-!
# The preparation `PrepLay.pre` as a first-order segment

`prepI fl dst R js linF phF`: the repeat-until-success chain `js`, then the gate chain `linF` (the
linear map), then the gate chain `phF` (the table phase). `PrepLay.prepI_valid`: it represents
`X.pre β dst R`. `prepIN`: the same segment from natural-number data (`PrepLay.prepI_eq`), with an
`IsPR` realizer of its node list as a function of the data, the continuation and the start position.
-/

namespace OPI

open QAlgorithms QAlgorithms.OPI TwoFoldOPI OPI.W6

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

/-- The preparation segment. -/
def prepI (fl dst R : ℕ) (js : List RusData) (linF phF : List (List ℕ)) : ISeg :=
  (rusChainI fl dst R js).comp ((ISeg.chainI linF).comp (ISeg.chainI phF))

namespace SymEnc

variable {F : AvgCaseTI.FieldPres} {n b m t kd : ℕ} {reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n}
  {D : RealDec F reg b t}



end SymEnc

open SymEnc in
/-- **The preparation segment from natural-number data.**
* `fl f0 asR`: flag, lookup flag and ancillas of the repeat-until-success stages; `dst`, `R`;
* `jobs`: the jobs (wires, lookup table), e.g. `allJobsN …`;
* `n b kd m RrW pivN TG Z asL fL`: the linear map (`TG` the shift tables);
* `SW scr asP fP zT`: the table phase (`zT` the phase table). -/
def prepIN (fl f0 dst R : ℕ) (asR : List ℕ) (jobs : List (List ℕ × PTab)) (n b kd m : ℕ) (RrW : List (List ℕ))
    (pivN : List ℕ) (TG : List (List (PTab × PTab))) (Z asL : List ℕ) (fL : ℕ) (SW : List (List ℕ))
    (scr asP : List ℕ) (fP : ℕ) (zT : PTab) : ISeg :=
  prepI fl dst R (jobs.map fun d => rjDataN d.1 d.2 fl f0 asR)
    ((linCircN RrW pivN kd m TG Z asL fL).flatMap rnGates) (phCircN n b RrW SW scr asP fP zT (List.range m))

namespace SymEnc

variable {F : AvgCaseTI.FieldPres} {n b m t kd : ℕ} {reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n}
  {D : RealDec F reg b t}





end SymEnc

end OPI

namespace OPI.W6.IsPR

open OAI.ThreeMachine.StackCompiler OPI OPI.SymEnc

variable {α : Type} [Coding α]









end OPI.W6.IsPR
end

-- ===== OPI.LayAlloc =====
section

/-!
# Wire allocation by blocks

Blocks `k < NB` of sizes `sz k`; wire `(k, l)` is `Σ_{k' < k} sz k' + l` (`finSigmaFinEquiv`).
Different blocks never share wires.
-/

namespace OPI

namespace Lay

/-- Layout parameters: number of coordinates, bits per symbol, field degree, bits per prime-field
element, QPE bits, gradient bits, classical-decoder ids. -/
structure Par where
  m : ℕ
  L : ℕ
  d : ℕ
  w : ℕ
  t : ℕ
  b : ℕ
  nI : ℕ

/-- Number of blocks. -/
abbrev NB : ℕ := 40

/-- Block sizes. -/
def sz (P : Par) (k : Fin NB) : ℕ :=
  match k.val with
  | 0 => P.m * (2 * P.L)        -- symbol registers `(i, c, j)`
  | 1 => P.m * P.L              -- `R`
  | 2 => (P.m * 2 * P.d) * P.w  -- resources `(i, c, g, j)`
  | 3 => P.t                    -- shared QPE control register
  | 4 => P.w + 1                -- accumulator top
  | 5 => 1                      -- accumulator `lh`
  | 6 => P.t - 1                -- accumulator rest
  | 7 => P.w                    -- lookup scratch `Z`
  | 8 => P.t + 2 * P.w + 2      -- lookup ancillas
  | 9 => P.L                    -- `QQ` scratch `ZR`
  | 10 => P.L                   -- `QQ` ancillas
  | 11 => 1                     -- `QQ` flag
  | 12 => P.L                   -- subtraction scratch
  | 13 => 2 * P.L               -- subtraction ancillas
  | 14 => 1                     -- subtraction flag
  | 15 => 1                     -- lookup flag
  | 16 => P.b                   -- gradient-workspace scratch
  | 17 => P.b + 2 * P.w         -- gradient-workspace ancillas
  | 18 => 1                     -- gradient-workspace flag
  | 19 => 2 * P.L               -- `E` scratch
  | 20 => 2 * P.L               -- `E` ancillas
  | 21 => 1                     -- `E` bit `a`
  | 22 => 1                     -- `E` flag
  | 23 => P.L                   -- `P_β` scratch
  | 24 => P.L                   -- `P_β` ancillas
  | 25 => 1                     -- `P_β` flag
  | 26 => P.nI * P.L            -- classical-decoder registers
  | 27 => 4 * P.L               -- classical-decoder ancillas
  | 28 => 1                     -- classical-decoder flag
  | 29 => 1                     -- RUS flag
  | 30 => 1                     -- RUS outcome
  | 31 => P.L + P.w             -- RUS ancillas
  | 32 => P.L                   -- linear-map scratch
  | 33 => 2 * P.L               -- linear-map ancillas
  | 34 => 1                     -- linear-map flag
  | 35 => P.b                   -- phase scratch
  | 36 => P.b + 2 * P.L         -- phase ancillas
  | 37 => 1                     -- phase flag
  | 38 => 1                     -- gradient-preparation control
  | 39 => P.b                   -- gradient-preparation ancillas
  | _ => 0

@[simp] lemma sz_0 (P : Par) : sz P 0 = P.m * (2 * P.L) := rfl
@[simp] lemma sz_1 (P : Par) : sz P 1 = P.m * P.L := rfl
@[simp] lemma sz_2 (P : Par) : sz P 2 = (P.m * 2 * P.d) * P.w := rfl
@[simp] lemma sz_3 (P : Par) : sz P 3 = P.t := rfl
@[simp] lemma sz_4 (P : Par) : sz P 4 = P.w + 1 := rfl
@[simp] lemma sz_5 (P : Par) : sz P 5 = 1 := rfl
@[simp] lemma sz_6 (P : Par) : sz P 6 = P.t - 1 := rfl
@[simp] lemma sz_7 (P : Par) : sz P 7 = P.w := rfl
@[simp] lemma sz_8 (P : Par) : sz P 8 = P.t + 2 * P.w + 2 := rfl
@[simp] lemma sz_9 (P : Par) : sz P 9 = P.L := rfl
@[simp] lemma sz_10 (P : Par) : sz P 10 = P.L := rfl
@[simp] lemma sz_11 (P : Par) : sz P 11 = 1 := rfl
@[simp] lemma sz_12 (P : Par) : sz P 12 = P.L := rfl
@[simp] lemma sz_13 (P : Par) : sz P 13 = 2 * P.L := rfl
@[simp] lemma sz_14 (P : Par) : sz P 14 = 1 := rfl
@[simp] lemma sz_15 (P : Par) : sz P 15 = 1 := rfl
@[simp] lemma sz_16 (P : Par) : sz P 16 = P.b := rfl
@[simp] lemma sz_17 (P : Par) : sz P 17 = P.b + 2 * P.w := rfl
@[simp] lemma sz_18 (P : Par) : sz P 18 = 1 := rfl
@[simp] lemma sz_19 (P : Par) : sz P 19 = 2 * P.L := rfl
@[simp] lemma sz_20 (P : Par) : sz P 20 = 2 * P.L := rfl
@[simp] lemma sz_21 (P : Par) : sz P 21 = 1 := rfl
@[simp] lemma sz_22 (P : Par) : sz P 22 = 1 := rfl
@[simp] lemma sz_23 (P : Par) : sz P 23 = P.L := rfl
@[simp] lemma sz_24 (P : Par) : sz P 24 = P.L := rfl
@[simp] lemma sz_25 (P : Par) : sz P 25 = 1 := rfl
@[simp] lemma sz_26 (P : Par) : sz P 26 = P.nI * P.L := rfl
@[simp] lemma sz_27 (P : Par) : sz P 27 = 4 * P.L := rfl
@[simp] lemma sz_28 (P : Par) : sz P 28 = 1 := rfl
@[simp] lemma sz_29 (P : Par) : sz P 29 = 1 := rfl
@[simp] lemma sz_30 (P : Par) : sz P 30 = 1 := rfl
@[simp] lemma sz_31 (P : Par) : sz P 31 = P.L + P.w := rfl
@[simp] lemma sz_32 (P : Par) : sz P 32 = P.L := rfl
@[simp] lemma sz_33 (P : Par) : sz P 33 = 2 * P.L := rfl
@[simp] lemma sz_34 (P : Par) : sz P 34 = 1 := rfl
@[simp] lemma sz_35 (P : Par) : sz P 35 = P.b := rfl
@[simp] lemma sz_36 (P : Par) : sz P 36 = P.b + 2 * P.L := rfl
@[simp] lemma sz_37 (P : Par) : sz P 37 = 1 := rfl
@[simp] lemma sz_38 (P : Par) : sz P 38 = 1 := rfl
@[simp] lemma sz_39 (P : Par) : sz P 39 = P.b := rfl

/-- Total number of system wires. -/
def total (P : Par) : ℕ := ∑ k, sz P k

variable (P : Par)

/-- Wire `l` of block `k`. -/
def W (k : Fin NB) (l : Fin (sz P k)) : Fin (total P) := finSigmaFinEquiv ⟨k, l⟩

variable {P}







lemma W_inj {k : Fin NB} {l l' : Fin (sz P k)} (h : W P k l = W P k l') : l = l' := by
  have := finSigmaFinEquiv.injective h
  exact eq_of_heq (Sigma.mk.inj_iff.mp this).2

/-- The wire lies in block `k`. -/
def InB (k : Fin NB) (q : Fin (total P)) : Prop := ∃ l, q = W P k l





/-- The list of a block. -/
def blk (k : Fin NB) : List (Fin (total P)) := List.ofFn (W P k)

lemma blk_nodup (k : Fin NB) : (blk (P := P) k).Nodup :=
  List.nodup_ofFn.mpr (fun _ _ h => W_inj h)

lemma mem_blk {k : Fin NB} {q : Fin (total P)} : q ∈ blk (P := P) k ↔ InB k q := by
  simp only [blk, List.mem_ofFn, InB]; exact ⟨fun ⟨l, h⟩ => ⟨l, h.symm⟩, fun ⟨l, h⟩ => ⟨l, h.symm⟩⟩

@[simp] lemma blk_length (k : Fin NB) : (blk (P := P) k).length = sz P k := List.length_ofFn

/-- The single wire of a block of size `1`. -/
def one (k : Fin NB) (h : sz P k = 1) : Fin (total P) := W P k ⟨0, by omega⟩

@[simp] lemma bkOf_one' (k : Fin NB) (h : sz P k = 1) : (finSigmaFinEquiv.symm (W P k ⟨0, by omega⟩)).1 = k := by
  unfold W; rw [Equiv.symm_apply_apply]



end Lay

end OPI

namespace OPI

namespace Lay

variable {P : Par}

/-- The block of a wire. -/
def bkOf (q : Fin (total P)) : Fin NB := (finSigmaFinEquiv.symm q).1

@[simp] lemma bkOf_W (k : Fin NB) (l : Fin (sz P k)) : bkOf (W P k l) = k := by
  unfold bkOf W; rw [Equiv.symm_apply_apply]

lemma bkOf_of_mem_blk {k : Fin NB} {q : Fin (total P)} (h : q ∈ blk (P := P) k) : bkOf q = k := by
  obtain ⟨l, rfl⟩ := mem_blk.mp h; simp

@[simp] lemma bkOf_one (k : Fin NB) (h : sz P k = 1) : bkOf (one (P := P) k h) = k := bkOf_W _ _

lemma ne_of_bkOf {q q' : Fin (total P)} (h : bkOf q ≠ bkOf q') : q ≠ q' := fun e => h (by rw [e])

/-- **Nodup of concatenations across blocks.** -/
lemma nodup_app {l₁ l₂ : List (Fin (total P))} (h₁ : l₁.Nodup) (h₂ : l₂.Nodup)
    (hd : ∀ q ∈ l₁, ∀ q' ∈ l₂, bkOf q ≠ bkOf q') : (l₁ ++ l₂).Nodup :=
  List.nodup_append.mpr ⟨h₁, h₂, fun a ha b hb e => hd a ha b hb (by rw [e])⟩

/-- All wires of a list lie in the blocks of `S`. -/
def InS (S : Finset (Fin NB)) (l : List (Fin (total P))) : Prop := ∀ q ∈ l, bkOf q ∈ S

lemma InS_blk (k : Fin NB) : InS {k} (blk (P := P) k) := fun q hq => by
  rw [bkOf_of_mem_blk hq]; simp

lemma InS_app {S : Finset (Fin NB)} {l₁ l₂ : List (Fin (total P))} (h₁ : InS S l₁) (h₂ : InS S l₂) :
    InS S (l₁ ++ l₂) := fun q hq => by
  rcases List.mem_append.mp hq with h | h
  · exact h₁ q h
  · exact h₂ q h





lemma notMem_of_InS {S : Finset (Fin NB)} {l : List (Fin (total P))} (hl : InS S l) {q : Fin (total P)}
    (hq : bkOf q ∉ S) : q ∉ l := fun h => hq (hl q h)

end Lay

end OPI
end

-- ===== OPI.LayFam =====
section

/-!
# The wire families of the concrete layout
-/

namespace OPI

namespace Lay

open TwoFoldOPI

/-- The parameters of an instance. -/
def parOf (F : AvgCaseTI.FieldPres) (m t b nI : ℕ) : Par :=
  ⟨m, bitsPerSymbol F, F.f.natDegree, Fq.w F, t, b, nI⟩

variable (F : AvgCaseTI.FieldPres) (m t b nI : ℕ)

local notation "PP" => parOf F m t b nI
local notation "NN" => total (parOf F m t b nI)

lemma fpf_inj {a c : ℕ} {x y : Fin a × Fin c} (h : finProdFinEquiv x = finProdFinEquiv y) :
    x.1 = y.1 ∧ x.2 = y.2 := Prod.ext_iff.mp (finProdFinEquiv.injective h)

/-- The symbol registers `(i, c, j)`. -/
def regE : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin NN :=
  ⟨fun x => W PP 0 (finProdFinEquiv (x.1, finProdFinEquiv ((if x.2.1 then 1 else 0 : Fin 2), x.2.2))), by
    rintro ⟨i, c, j⟩ ⟨i', c', j'⟩ h
    obtain ⟨h1, h2⟩ := fpf_inj (W_inj h)
    obtain ⟨h3, h4⟩ := fpf_inj h2
    simp only at h1 h3 h4
    subst h1; subst h4
    cases c <;> cases c' <;> simp_all⟩

/-- The registers `R_i`. -/
def RrE (i : Fin m) : Fin (bitsPerSymbol F) ↪ Fin NN :=
  ⟨fun j => W PP 1 (finProdFinEquiv (i, j)), fun j j' h => (fpf_inj (W_inj h)).2⟩

lemma RrE_inj (i i' : Fin m) (j j' : Fin (bitsPerSymbol F)) (h : RrE F m t b nI i j = RrE F m t b nI i' j') :
    i = i' ∧ j = j' := fpf_inj (W_inj h)

/-- The resource of gadget `g` of coordinate `(i, c)`. -/
def resE (i : Fin m) (c : Bool) (g : Fin F.f.natDegree) : Fin (Fq.w F) ↪ Fin NN :=
  ⟨fun j => W PP 2 (finProdFinEquiv (finProdFinEquiv (finProdFinEquiv (i, (if c then 1 else 0 : Fin 2)), g), j)),
    fun j j' h => (fpf_inj (W_inj h)).2⟩

lemma resE_inj (i i' : Fin m) (c c' : Bool) (g g' : Fin F.f.natDegree) (j j' : Fin (Fq.w F))
    (h : resE F m t b nI i c g j = resE F m t b nI i' c' g' j') : i = i' ∧ c = c' ∧ g = g' ∧ j = j' := by
  obtain ⟨h1, h2⟩ := fpf_inj (W_inj h)
  obtain ⟨h3, h4⟩ := fpf_inj h1
  obtain ⟨h5, h6⟩ := fpf_inj h3
  simp only at h2 h4 h5 h6
  refine ⟨h5, ?_, h4, h2⟩
  cases c <;> cases c' <;> simp_all

/-- The shared QPE control register. -/
def cEE : Fin t ↪ Fin NN := ⟨fun j => W PP 3 j, fun _ _ h => W_inj h⟩

@[simp] lemma bkOf_regE (x) : bkOf (regE F m t b nI x) = 0 := bkOf_W _ _
@[simp] lemma bkOf_RrE (i j) : bkOf (RrE F m t b nI i j) = 1 := bkOf_W _ _
@[simp] lemma bkOf_resE (i c g j) : bkOf (resE F m t b nI i c g j) = 2 := bkOf_W _ _
@[simp] lemma bkOf_cEE (j) : bkOf (cEE F m t b nI j) = 3 := bkOf_W _ _

lemma InS_ofFn {k : ℕ} (f : Fin k → Fin NN) (S : Finset (Fin NB)) (h : ∀ j, bkOf (f j) ∈ S) :
    InS S (List.ofFn f) := fun q hq => by
  obtain ⟨j, rfl⟩ := List.mem_ofFn.mp hq; exact h j

end Lay

end OPI
end

-- ===== OPI.LayQG =====
section

/-!
# The concrete `QFT_p` gadgets
-/

namespace OPI

namespace Lay

open TwoFoldOPI

variable {P : Par}

/-- **Nodup of a concatenation of lists from pairwise disjoint block sets.** -/
lemma nodup_flatten_S (ls : List (List (Fin (total P)) × Finset (Fin NB)))
    (h1 : ∀ x ∈ ls, x.1.Nodup ∧ InS x.2 x.1) (h2 : ls.Pairwise (fun x y => Disjoint x.2 y.2)) :
    (ls.map Prod.fst).flatten.Nodup := by
  induction ls with
  | nil => simp
  | cons x ls ih =>
    simp only [List.map_cons, List.flatten_cons]
    have hp := List.pairwise_cons.mp h2
    refine nodup_app (h1 x (by simp)).1 (ih (fun y hy => h1 y (by simp [hy])) hp.2) ?_
    intro q hq q' hq' e
    obtain ⟨ys, hys, hq'⟩ := List.mem_flatten.mp hq'
    obtain ⟨y, hy, rfl⟩ := List.mem_map.mp hys
    have a := (h1 x (by simp)).2 q hq
    have b := (h1 y (by simp [hy])).2 q' hq'
    rw [e] at a
    exact Finset.disjoint_left.mp (hp.1 y hy) a b

lemma nodup_flatten_S' (ls : List (List (Fin (total P)))) (Ss : List (Finset (Fin NB)))
    (hl : ls.length = Ss.length) (h1 : ∀ x ∈ ls.zip Ss, x.1.Nodup ∧ InS x.2 x.1)
    (h2 : Ss.Pairwise Disjoint) : ls.flatten.Nodup := by
  have := nodup_flatten_S (ls.zip Ss) h1 (by
    have e : (ls.zip Ss).map Prod.snd = Ss := List.map_snd_zip (by omega)
    rw [← List.pairwise_map (f := Prod.snd), e]; exact h2)
  rwa [List.map_fst_zip (by omega)] at this

lemma nodup_ofFn_emb {k : ℕ} (f : Fin k ↪ Fin (total P)) : (List.ofFn f).Nodup :=
  List.nodup_ofFn.mpr f.injective

variable (F : AvgCaseTI.FieldPres) (m t b nI : ℕ)

local notation "PP" => parOf F m t b nI
local notation "NN" => total (parOf F m t b nI)

/-- The shared lookup ancillas (also holding the `QQ` and subtraction scratch). -/
def asQ : List (Fin NN) :=
  blk 8 ++ blk 9 ++ blk 10 ++ [one 11 (sz_11 _)] ++ blk 12 ++ blk 13 ++ [one 14 (sz_14 _)]

lemma InS_asQ : InS {8, 9, 10, 11, 12, 13, 14} (asQ F m t b nI) := by
  intro q hq
  simp only [asQ, List.mem_append, List.mem_singleton] at hq
  rcases hq with (((((h | h) | h) | h) | h) | h) | h
  all_goals first
    | (rw [bkOf_of_mem_blk h]; decide)
    | (subst h; simp only [bkOf_one]; decide)

lemma asQ_length : (asQ F m t b nI).length =
    t + 2 * Fq.w F + 2 + bitsPerSymbol F + bitsPerSymbol F + 1 + bitsPerSymbol F + 2 * bitsPerSymbol F + 1 := by
  unfold asQ
  rw [List.length_append, List.length_append, List.length_append, List.length_append, List.length_append,
    List.length_append, blk_length, blk_length, blk_length, blk_length, blk_length, List.length_singleton,
    List.length_singleton, sz_8, sz_9, sz_10, sz_12, sz_13]
  rfl

lemma asQ_nodup : (asQ F m t b nI).Nodup := by
  have : asQ F m t b nI = [blk (P := PP) 8, blk 9, blk 10, [one 11 (sz_11 _)], blk 12, blk 13, [one 14 (sz_14 _)]].flatten := by
    simp [asQ, List.append_assoc]
  rw [this]
  apply nodup_flatten_S' _ [{8}, {9}, {10}, {11}, {12}, {13}, {14}] rfl
  · intro x hx
    simp only [List.zip_cons_cons, List.zip_nil_right, List.mem_cons, List.mem_nil_iff, or_false] at hx
    rcases hx with rfl | rfl | rfl | rfl | rfl | rfl | rfl
    all_goals first
      | exact ⟨blk_nodup _, InS_blk _⟩
      | exact ⟨List.nodup_singleton _, fun q hq => by
          rw [List.mem_singleton] at hq; subst hq; simp only [bkOf_one]; exact Finset.mem_singleton_self _⟩
  · decide

@[simp] lemma bkOf_bReg (i : Fin m) (c : Bool) (j : Fin (bitsPerSymbol F)) :
    bkOf (SymEnc.bReg (regE F m t b nI) i c j) = 0 := bkOf_W _ _

lemma InS_single (k : Fin NB) (h : sz PP k = 1) : InS {k} [one (P := PP) k h] := fun q hq => by
  rw [List.mem_singleton] at hq; subst hq; simp only [bkOf_one]; exact Finset.mem_singleton_self _

lemma InS_aE (i : Fin m) (c : Bool) (g : Fin F.f.natDegree) :
    InS {0} (List.ofFn ((Fq.blk F g).trans (SymEnc.bReg (regE F m t b nI) i c))) :=
  InS_ofFn F m t b nI _ _ (fun j => by simp [Function.Embedding.trans_apply])

/-- The concrete lookup layout of gadget `(i, c, g)`. -/
def qlay (ht : 1 ≤ t) (i : Fin m) (c : Bool) (g : Fin F.f.natDegree) : QLay NN F.p (Fq.w F) t where
  aE := (Fq.blk F g).trans (SymEnc.bReg (regE F m t b nI) i c)
  bE := resE F m t b nI i c g
  cE := cEE F m t b nI
  top := blk 4
  lh := one 5 (sz_5 _)
  lrest := blk 6
  Z := blk 7
  as := asQ F m t b nI
  f := one 15 (sz_15 _)
  htop := by simp [parOf]
  hlrest := by simp [parOf]; omega
  hZ := by simp [parOf]
  has := by rw [asQ_length]; omega
  hnd := by
    have e : (List.ofFn (cEE F m t b nI) ++ (blk 4 ++ one 5 (sz_5 _) :: blk 6) ++
        List.ofFn ((Fq.blk F g).trans (SymEnc.bReg (regE F m t b nI) i c)) ++ List.ofFn (resE F m t b nI i c g) ++
        blk 7 ++ asQ F m t b nI ++ [one 15 (sz_15 _)]) =
        [List.ofFn (cEE F m t b nI), blk 4, [one 5 (sz_5 _)], blk 6,
          List.ofFn ((Fq.blk F g).trans (SymEnc.bReg (regE F m t b nI) i c)), List.ofFn (resE F m t b nI i c g),
          blk 7, asQ F m t b nI, [one 15 (sz_15 _)]].flatten := by
      simp [List.append_assoc]
    rw [e]
    apply nodup_flatten_S' _ [{3}, {4}, {5}, {6}, {0}, {2}, {7}, {8, 9, 10, 11, 12, 13, 14}, {15}] rfl
    · intro x hx
      simp only [List.zip_cons_cons, List.zip_nil_right, List.mem_cons, List.mem_nil_iff, or_false] at hx
      rcases hx with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl
      · exact ⟨nodup_ofFn_emb _, InS_ofFn F m t b nI _ _ (fun j => by simp)⟩
      · exact ⟨blk_nodup _, InS_blk _⟩
      · exact ⟨List.nodup_singleton _, InS_single F m t b nI _ _⟩
      · exact ⟨blk_nodup _, InS_blk _⟩
      · exact ⟨nodup_ofFn_emb _, InS_aE F m t b nI i c g⟩
      · exact ⟨nodup_ofFn_emb _, InS_ofFn F m t b nI _ _ (fun j => by simp)⟩
      · exact ⟨blk_nodup _, InS_blk _⟩
      · exact ⟨asQ_nodup F m t b nI, InS_asQ F m t b nI⟩
      · exact ⟨List.nodup_singleton _, InS_single F m t b nI _ _⟩
    · decide

/-- The concrete gradient workspace. -/
def wsC : WS NN b where
  scr := blk 16
  as := blk 17
  f := one 18 (sz_18 _)
  hscr := by simp [parOf]
  has := by simp [parOf]; omega
  hnd := by
    have e : blk (P := PP) 16 ++ blk 17 ++ [one 18 (sz_18 _)] = [blk (P := PP) 16, blk 17, [one 18 (sz_18 _)]].flatten := by
      simp [List.append_assoc]
    rw [e]
    apply nodup_flatten_S' _ [{16}, {17}, {18}] rfl
    · intro x hx
      simp only [List.zip_cons_cons, List.zip_nil_right, List.mem_cons, List.mem_nil_iff, or_false] at hx
      rcases hx with rfl | rfl | rfl
      · exact ⟨blk_nodup _, InS_blk _⟩
      · exact ⟨blk_nodup _, InS_blk _⟩
      · exact ⟨List.nodup_singleton _, InS_single F m t b nI _ _⟩
    · decide

lemma InS_wsC : InS {16, 17, 18} (wsC F m t b nI).cl := by
  intro q hq
  simp only [WS.cl, wsC, List.mem_append, List.mem_singleton] at hq
  rcases hq with (h | h) | h
  · rw [bkOf_of_mem_blk h]; decide
  · rw [bkOf_of_mem_blk h]; decide
  · subst h; simp only [bkOf_one]; decide

lemma notMem_wsC {q : Fin NN} (hq : bkOf q ∉ ({16, 17, 18} : Finset (Fin NB))) : q ∉ (wsC F m t b nI).cl :=
  notMem_of_InS (InS_wsC F m t b nI) hq

/-- **The concrete `QFT_p` gadget of `(i, c, g)`.** -/
def qg (ht : 1 ≤ t) (htb : t ≤ b) (i : Fin m) (c : Bool) (g : Fin F.f.natDegree) : QG NN b F.p (Fq.w F) t :=
  { qlay F m t b nI ht i c g with
    W := wsC F m t b nI
    hWa := fun j => notMem_wsC F m t b nI (by simp [qlay, Function.Embedding.trans_apply])
    hWb := fun j => notMem_wsC F m t b nI (by simp [qlay])
    hWc := fun j => notMem_wsC F m t b nI (by simp [qlay])
    hWacc := fun a ha => by
      refine notMem_wsC F m t b nI ?_
      simp only [qlay, List.mem_append, List.mem_cons] at ha
      rcases ha with h | h | h
      · rw [bkOf_of_mem_blk h]; decide
      · subst h; simp only [bkOf_one]; decide
      · rw [bkOf_of_mem_blk h]; decide
    htb := htb
    hwas := by
      show Fq.w F + Fq.w F ≤ (blk (P := PP) 17).length + 2
      rw [blk_length, sz_17]
      show Fq.w F + Fq.w F ≤ b + 2 * Fq.w F + 2
      omega }

/-! ## The `QFT_q` gadgets -/

/-- The shared clean wires of all `QFT_p` gadgets. -/
def clQ : List (Fin NN) :=
  (wsC F m t b nI).cl ++ (blk 4 ++ one 5 (sz_5 _) :: blk 6) ++ (blk 7 ++ asQ F m t b nI ++ [one 15 (sz_15 _)])

lemma InS_clQ : InS {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18} (clQ F m t b nI) := by
  intro q hq
  simp only [clQ, List.mem_append, List.mem_cons] at hq
  rcases hq with (h | (h | h | h)) | ((h | h) | h)
  · exact Finset.mem_of_subset (by decide) (InS_wsC F m t b nI q h)
  · rw [bkOf_of_mem_blk h]; decide
  · subst h; simp only [bkOf_one]; decide
  · rw [bkOf_of_mem_blk h]; decide
  · rw [bkOf_of_mem_blk h]; decide
  · exact Finset.mem_of_subset (by decide) (InS_asQ F m t b nI q h)
  · rcases h with h | h
    · subst h; simp only [bkOf_one]; decide
    · simp at h

lemma notMem_clQ {q : Fin NN} (hq : bkOf q ∉ ({4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18} : Finset (Fin NB))) :
    q ∉ clQ F m t b nI := notMem_of_InS (InS_clQ F m t b nI) hq

lemma clG_qg (ht : 1 ≤ t) (htb : t ≤ b) (i : Fin m) (c : Bool) (g : Fin F.f.natDegree) :
    (qg F m t b nI ht htb i c g).clG = clQ F m t b nI := rfl

/-- The block set of the accumulator and lookup scratch. -/
lemma wiresOf_qg (ht : 1 ≤ t) (htb : t ≤ b) (i : Fin m) (c : Bool) (g : Fin F.f.natDegree) (a : Fin NN)
    (h : (qg F m t b nI ht htb i c g).wiresOf a) :
    a ∈ Set.range ((Fq.blk F g).trans (SymEnc.bReg (regE F m t b nI) i c)) ∨
      a ∈ Set.range (resE F m t b nI i c g) ∨
      bkOf a ∈ ({3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15} : Finset (Fin NB)) := by
  rcases h with h | h | h | h | h
  · exact Or.inl h
  · exact Or.inr (Or.inl h)
  · obtain ⟨j, rfl⟩ := h; right; right; simp [qg, qlay]
  · right; right
    simp only [qg, qlay, QLay.acc, List.mem_append, List.mem_cons] at h
    rcases h with h | h | h
    · rw [bkOf_of_mem_blk h]; decide
    · subst h; simp only [bkOf_one]; decide
    · rw [bkOf_of_mem_blk h]; decide
  · right; right
    simp only [qg, qlay, QLay.cl, List.mem_append, List.mem_singleton] at h
    rcases h with (h | h) | h
    · rw [bkOf_of_mem_blk h]; decide
    · exact Finset.mem_of_subset (by decide) (InS_asQ F m t b nI a h)
    · subst h; simp only [bkOf_one]; decide

lemma cross_qg (ht : 1 ≤ t) (htb : t ≤ b) (i : Fin m) (c : Bool) (g g' : Fin F.f.natDegree) (hgg : g ≠ g') :
    QG.Cross (qg F m t b nI ht htb i c g) (qg F m t b nI ht htb i c g') := by
  have hA : ∀ g g' : Fin F.f.natDegree, g ≠ g' → QG.Avoids (qg F m t b nI ht htb i c g).aE (qg F m t b nI ht htb i c g') := by
    intro g g' hgg j hw
    rcases wiresOf_qg F m t b nI ht htb i c g' _ hw with ⟨j', hj'⟩ | ⟨j', hj'⟩ | h
    · simp only [qg, qlay, Function.Embedding.trans_apply] at hj'
      have := (regE F m t b nI).injective hj'
      simp only [SymEnc.bReg, Function.Embedding.coeFn_mk, Prod.mk.injEq] at this
      exact hgg (fpf_inj this.2.2).1.symm
    · have := congrArg bkOf hj'
      simp [qg, qlay, Function.Embedding.trans_apply] at this
    · simp [qg, qlay, Function.Embedding.trans_apply] at h
  have hB : ∀ g g' : Fin F.f.natDegree, g ≠ g' → QG.Avoids (qg F m t b nI ht htb i c g).bE (qg F m t b nI ht htb i c g') := by
    intro g g' hgg j hw
    rcases wiresOf_qg F m t b nI ht htb i c g' _ hw with ⟨j', hj'⟩ | ⟨j', hj'⟩ | h
    · have := congrArg bkOf hj'
      simp [qg, qlay, Function.Embedding.trans_apply] at this
    · simp only [qg, qlay] at hj'
      exact hgg (resE_inj F m t b nI _ _ _ _ _ _ _ _ hj').2.2.1.symm
    · simp [qg, qlay] at h
  exact ⟨hA g g' hgg, hB g g' hgg, hA g' g hgg.symm, hB g' g hgg.symm⟩

/-- **The concrete `QFT_q` gadget of coordinate `(i, c)`.** -/
def qq (ht : 1 ≤ t) (htb : t ≤ b) (i : Fin m) (c : Bool) : QQ NN b F t where
  X := SymEnc.bReg (regE F m t b nI) i c
  Gs := List.ofFn fun g => qg F m t b nI ht htb i c g
  hlen := List.length_ofFn
  haE := fun j => by rw [List.get_ofFn]; rfl
  hpair := List.pairwise_ofFn.mpr (fun g g' hlt => cross_qg F m t b nI ht htb i c g g' (ne_of_lt hlt))
  cl := clQ F m t b nI
  hcl := fun G hG => by
    obtain ⟨g, rfl⟩ := List.mem_ofFn.mp hG
    exact clG_qg F m t b nI ht htb i c g
  ZR := blk 9
  asR := blk 10
  fR := one 11 (sz_11 _)
  hZR := by rw [blk_length, sz_9]; rfl
  hasR := by rw [blk_length, sz_10]; show bitsPerSymbol F ≤ bitsPerSymbol F + 2; omega
  hndR := by
    have e : List.ofFn (SymEnc.bReg (regE F m t b nI) i c) ++ blk 9 ++ blk 10 ++ [one 11 (sz_11 _)] =
        [List.ofFn (SymEnc.bReg (regE F m t b nI) i c), blk 9, blk 10, [one 11 (sz_11 _)]].flatten := by
      simp [List.append_assoc]
    rw [e]
    apply nodup_flatten_S' _ [{0}, {9}, {10}, {11}] rfl
    · intro x hx
      simp only [List.zip_cons_cons, List.zip_nil_right, List.mem_cons, List.mem_nil_iff, or_false] at hx
      rcases hx with rfl | rfl | rfl | rfl
      · exact ⟨nodup_ofFn_emb _, InS_ofFn F m t b nI _ _ (fun j => by simp)⟩
      · exact ⟨blk_nodup _, InS_blk _⟩
      · exact ⟨blk_nodup _, InS_blk _⟩
      · exact ⟨List.nodup_singleton _, InS_single F m t b nI _ _⟩
    · decide
  hRcl := fun a ha => by
    have h1 : a ∈ asQ F m t b nI := by
      unfold asQ
      rcases List.mem_append.mp ha with h | h
      · rcases List.mem_append.mp h with h | h
        · exact List.mem_append_left _ (List.mem_append_left _ (List.mem_append_left _
            (List.mem_append_left _ (List.mem_append_left _ (List.mem_append_right _ h)))))
        · exact List.mem_append_left _ (List.mem_append_left _ (List.mem_append_left _
            (List.mem_append_left _ (List.mem_append_right _ h))))
      · exact List.mem_append_left _ (List.mem_append_left _ (List.mem_append_left _
          (List.mem_append_right _ h)))
    unfold clQ
    exact List.mem_append_right _ (List.mem_append_left _ (List.mem_append_right _ h1))
  hXcl := fun j => notMem_clQ F m t b nI (by simp)
  hXb := fun G hG j j' e => by
    obtain ⟨g, rfl⟩ := List.mem_ofFn.mp hG
    have := congrArg bkOf e
    simp [qg, qlay] at this
  hXc := fun G hG j j' e => by
    obtain ⟨g, rfl⟩ := List.mem_ofFn.mp hG
    have := congrArg bkOf e
    simp [qg, qlay] at this

end Lay

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_Part03.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