Construction for Theorem 7.4, part 4: concrete layout, RREF basis, final program and its first-order form
DefinitionTwoFoldOPI_CL_Part04lean-formalizationquantum-algorithmstwo-fold-opi-construction
Definitions underlying the formal construction behind the algorithmic part of Theorem 7.4, part 4 (imports part 3). It contains the concrete wire layout (decoder, classical decoder, preparation, trial loop), the reduced row echelon basis of the dual code, the gradient stages and the full quantum program with its numerical parameters, the bottom-case program for , and the first-order (natural-number) twins of all circuits, layouts and lookup tables from which the generator builds the program DAG.
The bundle contains only definitions together with the structural lemmas these definitions require.
Definition code
import Definitions.Def_TwoFoldOPI_CL_Part03
import Mathlib
import Definitions.Def_TwoFoldOPI_codeOf
import Definitions.Def_TwoFoldOPI_schurSquare
import Definitions.Def_TwoFoldOPI_solves
set_option maxHeartbeats 400000
set_option linter.all false
-- ===== OPI.LayDec =====
section
/-!
# The concrete real-decoder layout
-/
namespace OPI
namespace Lay
open TwoFoldOPI
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 bReg_nodup2 (i : Fin m) :
(List.ofFn (SymEnc.bReg (regE F m t b nI) i false) ++ List.ofFn (SymEnc.bReg (regE F m t b nI) i true)).Nodup := by
refine List.nodup_append.mpr ⟨nodup_ofFn_emb _, nodup_ofFn_emb _, ?_⟩
intro a ha a' ha' e
obtain ⟨j, rfl⟩ := List.mem_ofFn.mp ha
obtain ⟨j', rfl⟩ := List.mem_ofFn.mp ha'
have := (regE F m t b nI).injective e
simp [SymEnc.bReg] at this
lemma InS_bReg (i : Fin m) (c : Bool) : InS {0} (List.ofFn (SymEnc.bReg (regE F m t b nI) i c)) :=
InS_ofFn F m t b nI _ _ (fun j => by simp)
/-- **The concrete wires of the `E` and `P_β` gadgets of coordinate `i`.** -/
def coordW (i : Fin m) : SymEnc.CoordWires F (regE F m t b nI) i where
ZE := blk 19
asE := blk 20
aE := one 21 (sz_21 _)
fE := one 22 (sz_22 _)
hndE := by
have e : [one (P := PP) 21 (sz_21 _)] ++ (List.ofFn (SymEnc.bReg (regE F m t b nI) i false) ++
List.ofFn (SymEnc.bReg (regE F m t b nI) i true)) ++ blk 19 ++ blk 20 ++ [one 22 (sz_22 _)] =
[[one (P := PP) 21 (sz_21 _)], List.ofFn (SymEnc.bReg (regE F m t b nI) i false) ++
List.ofFn (SymEnc.bReg (regE F m t b nI) i true), blk 19, blk 20, [one 22 (sz_22 _)]].flatten := by
simp [List.append_assoc]
rw [e]
apply nodup_flatten_S' _ [{21}, {0}, {19}, {20}, {22}] 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
· exact ⟨List.nodup_singleton _, InS_single F m t b nI _ _⟩
· exact ⟨bReg_nodup2 F m t b nI i, InS_app (InS_bReg F m t b nI i false) (InS_bReg F m t b nI i true)⟩
· exact ⟨blk_nodup _, InS_blk _⟩
· exact ⟨blk_nodup _, InS_blk _⟩
· exact ⟨List.nodup_singleton _, InS_single F m t b nI _ _⟩
· decide
hZE := by rw [blk_length, sz_19]; rfl
hlenE := by rw [blk_length, sz_20]; show 1 + 2 * bitsPerSymbol F ≤ 2 * bitsPerSymbol F + 2; omega
houtE := fun p => by
refine ⟨ne_of_bkOf (by simp), ne_of_bkOf (by simp), fun x hx => ne_of_bkOf ?_, fun x hx => ne_of_bkOf ?_⟩
· rw [bkOf_of_mem_blk hx]; simp
· rw [bkOf_of_mem_blk hx]; simp
ZP := blk 23
asP := blk 24
fP := one 25 (sz_25 _)
hndP := by
have e : [] ++ List.ofFn (SymEnc.bReg (regE F m t b nI) i false) ++ blk 23 ++ blk 24 ++ [one 25 (sz_25 _)] =
[List.ofFn (SymEnc.bReg (regE F m t b nI) i false), blk 23, blk 24, [one 25 (sz_25 _)]].flatten := by
simp [List.append_assoc]
rw [e]
apply nodup_flatten_S' _ [{0}, {23}, {24}, {25}] 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_bReg F m t b nI i false⟩
· exact ⟨blk_nodup _, InS_blk _⟩
· exact ⟨blk_nodup _, InS_blk _⟩
· exact ⟨List.nodup_singleton _, InS_single F m t b nI _ _⟩
· decide
hZP := by rw [blk_length, sz_23]; rfl
hlenP := by rw [blk_length, sz_24]; show bitsPerSymbol F ≤ bitsPerSymbol F + 2; omega
houtP := fun p => by
refine ⟨ne_of_bkOf (by simp), fun x hx => ne_of_bkOf ?_, fun x hx => ne_of_bkOf ?_⟩
· rw [bkOf_of_mem_blk hx]; simp
· rw [bkOf_of_mem_blk hx]; simp
lemma mem_resQ (ht : 1 ≤ t) (htb : t ≤ b) (i : Fin m) (c : Bool) (r : Res NN)
(hr : r ∈ SymEnc.resQ F (qq F m t b nI ht htb i c)) :
∃ g, r = ⟨Fq.w F, resE F m t b nI i c g, fvec F.p (Fq.w F) 0⟩ := by
simp only [SymEnc.resQ, qq, List.mem_map, List.mem_ofFn] at hr
obtain ⟨G, ⟨g, rfl⟩, rfl⟩ := hr
exact ⟨g, rfl⟩
lemma bkOf_res (ht : 1 ≤ t) (htb : t ≤ b) (i : Fin m) (c : Bool) (r : Res NN)
(hr : r ∈ SymEnc.resQ F (qq F m t b nI ht htb i c)) (j : Fin r.k) : bkOf (r.w j) = 2 := by
obtain ⟨g, rfl⟩ := mem_resQ F m t b nI ht htb i c r hr
simp
lemma cWire_cases (ht : 1 ≤ t) (htb : t ≤ b) (i : Fin m) (c : Bool) (q : Fin NN)
(h : SymEnc.cWire F (qq F m t b nI ht htb i c) q) :
(∃ g j, q = resE F m t b nI i c g j) ∨
bkOf q ∈ ({3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15} : Finset (Fin NB)) := by
rcases h with h | ⟨G, hG, h⟩
· right
simp only [qq, List.mem_append, List.mem_singleton] at h
rcases h 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
· obtain ⟨g, rfl⟩ := List.mem_ofFn.mp hG
rcases h with ⟨j, rfl⟩ | ⟨j, rfl⟩ | h | h
· exact Or.inl ⟨g, j, rfl⟩
· right; simp [qg, qlay]
· 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
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 q h)
· subst h; simp only [bkOf_one]; decide
/-- **The concrete real-decoder layout.** -/
def realDec (ht : 1 ≤ t) (htb : t ≤ b) : SymEnc.RealDec F (regE F m t b nI) b t where
W := coordW F m t b nI
Q := qq F m t b nI ht htb
hQX := fun _ _ => rfl
hres := fun i c i' c' hne r hr r' hr' j j' e => by
obtain ⟨g, rfl⟩ := mem_resQ F m t b nI ht htb i c r hr
obtain ⟨g', rfl⟩ := mem_resQ F m t b nI ht htb i' c' r' hr'
obtain ⟨h1, h2, -, -⟩ := resE_inj F m t b nI _ _ _ _ _ _ _ _ e
exact hne (by rw [h1, h2])
hcw := fun i c q hq => by
rcases cWire_cases F m t b nI ht htb i c q hq with ⟨g, j, rfl⟩ | h
· refine ⟨fun p => ne_of_bkOf (by simp), fun i' c' hne r hr ⟨j', e⟩ => ?_⟩
obtain ⟨g', rfl⟩ := mem_resQ F m t b nI ht htb i' c' r hr
obtain ⟨h1, h2, -, -⟩ := resE_inj F m t b nI _ _ _ _ _ _ _ _ e
exact hne (by rw [h1, h2])
· refine ⟨fun p e => ?_, fun i' c' _ r hr ⟨j', e⟩ => ?_⟩
· rw [← e] at h; simp at h
· rw [← e, bkOf_res F m t b nI ht htb i' c' r hr] at h; simp at h
hep := fun i i' c' r hr q hq ⟨j, e⟩ => by
have h2 := bkOf_res F m t b nI ht htb i' c' r hr j
rw [e] at h2
rcases hq with h | h | h | h | h | h | h
· subst h; simp [coordW] at h2
· subst h; simp [coordW] at h2
· rw [bkOf_of_mem_blk h] at h2; simp at h2
· rw [bkOf_of_mem_blk h] at h2; simp at h2
· subst h; simp [coordW] at h2
· rw [bkOf_of_mem_blk h] at h2; simp at h2
· rw [bkOf_of_mem_blk h] at h2; simp at h2
end Lay
end OPI
end
-- ===== OPI.LayCls =====
section
/-!
# The concrete classical-decoder layout
-/
namespace OPI
namespace Lay
open TwoFoldOPI RelinProg
variable (F : AvgCaseTI.FieldPres) (m t b : ℕ) (k k2 : ℕ)
local notation "nI" => SymEnc.nIds m k k2
local notation "PP" => parOf F m t b (SymEnc.nIds m k k2)
local notation "NN" => total (parOf F m t b (SymEnc.nIds m k k2))
/-- The decoder register of a non-input id. -/
def clsReg (x : Fin nI) : List (Fin NN) :=
List.ofFn fun j : Fin (bitsPerSymbol F) => W PP 26 (finProdFinEquiv (x, j))
lemma bkOf_cls (x : ℕ) (hx : x < nI) (j : Fin (bitsPerSymbol F)) :
bkOf (W PP 26 (finProdFinEquiv (⟨x, hx⟩, j))) = 26 := bkOf_W _ _
open Classical in
/-- **The registers of the straight-line ids.** -/
noncomputable def rsOf (x : ℕ) : List (Fin NN) :=
if h : ∃ i : Fin m, in1 m k k2 i = x then List.ofFn (SymEnc.bReg (regE F m t b nI) (Classical.choose h) false)
else if h : ∃ i : Fin m, in2 m k k2 i = x then List.ofFn (SymEnc.bReg (regE F m t b nI) (Classical.choose h) true)
else if hx : x < nI then clsReg F m t b k k2 ⟨x, hx⟩ else []
lemma rsOf_in1 (i : Fin m) : rsOf F m t b k k2 (in1 m k k2 i) = List.ofFn (SymEnc.bReg (regE F m t b nI) i false) := by
have h : ∃ i' : Fin m, in1 m k k2 i' = in1 m k k2 i := ⟨i, rfl⟩
unfold rsOf
rw [dif_pos h, SymEnc.in1_inj (Classical.choose_spec h)]
lemma rsOf_in2 (i : Fin m) : rsOf F m t b k k2 (in2 m k k2 i) = List.ofFn (SymEnc.bReg (regE F m t b nI) i true) := by
have h : ∃ i' : Fin m, in2 m k k2 i' = in2 m k k2 i := ⟨i, rfl⟩
have h1 : ¬ ∃ i' : Fin m, in1 m k k2 i' = in2 m k k2 i := fun ⟨i', e⟩ => SymEnc.in1_ne_in2 i' i e
unfold rsOf
rw [dif_neg h1, dif_pos h, SymEnc.in2_inj (Classical.choose_spec h)]
lemma rsOf_other (x : ℕ) (h1 : ∀ i : Fin m, in1 m k k2 i ≠ x) (h2 : ∀ i : Fin m, in2 m k k2 i ≠ x) (hx : x < nI) :
rsOf F m t b k k2 x = clsReg F m t b k k2 ⟨x, hx⟩ := by
unfold rsOf
rw [dif_neg (fun ⟨i, e⟩ => h1 i e), dif_neg (fun ⟨i, e⟩ => h2 i e), dif_pos hx]
/-- Cases of an id. -/
lemma rsOf_cases (x : ℕ) (hx : x < nI) :
(∃ i : Fin m, x = in1 m k k2 i ∧ rsOf F m t b k k2 x = List.ofFn (SymEnc.bReg (regE F m t b nI) i false)) ∨
(∃ i : Fin m, x = in2 m k k2 i ∧ rsOf F m t b k k2 x = List.ofFn (SymEnc.bReg (regE F m t b nI) i true)) ∨
((∀ i : Fin m, in1 m k k2 i ≠ x) ∧ (∀ i : Fin m, in2 m k k2 i ≠ x) ∧
rsOf F m t b k k2 x = clsReg F m t b k k2 ⟨x, hx⟩) := by
by_cases h1 : ∃ i : Fin m, in1 m k k2 i = x
· obtain ⟨i, rfl⟩ := h1; exact Or.inl ⟨i, rfl, rsOf_in1 F m t b k k2 i⟩
· by_cases h2 : ∃ i : Fin m, in2 m k k2 i = x
· obtain ⟨i, rfl⟩ := h2; exact Or.inr (Or.inl ⟨i, rfl, rsOf_in2 F m t b k k2 i⟩)
· push Not at h1 h2
exact Or.inr (Or.inr ⟨h1, h2, rsOf_other F m t b k k2 x h1 h2 hx⟩)
lemma mem_rsOf (x : ℕ) (hx : x < nI) (a : Fin NN) (ha : a ∈ rsOf F m t b k k2 x) :
(∃ i : Fin m, ∃ j, x = in1 m k k2 i ∧ a = regE F m t b nI (i, false, j)) ∨
(∃ i : Fin m, ∃ j, x = in2 m k k2 i ∧ a = regE F m t b nI (i, true, j)) ∨
(∃ j, a = W PP 26 (finProdFinEquiv (⟨x, hx⟩, j))) := by
rcases rsOf_cases F m t b k k2 x hx with ⟨i, rfl, e⟩ | ⟨i, rfl, e⟩ | ⟨-, -, e⟩
· rw [e] at ha
obtain ⟨j, rfl⟩ := List.mem_ofFn.mp ha
exact Or.inl ⟨i, j, rfl, rfl⟩
· rw [e] at ha
obtain ⟨j, rfl⟩ := List.mem_ofFn.mp ha
exact Or.inr (Or.inl ⟨i, j, rfl, rfl⟩)
· rw [e] at ha
obtain ⟨j, rfl⟩ := List.mem_ofFn.mp ha
exact Or.inr (Or.inr ⟨j, rfl⟩)
lemma rsOf_length (x : ℕ) (hx : x < nI) : (rsOf F m t b k k2 x).length = bitsPerSymbol F := by
rcases rsOf_cases F m t b k k2 x hx with ⟨i, -, e⟩ | ⟨i, -, e⟩ | ⟨-, -, e⟩ <;> rw [e] <;>
first | exact List.length_ofFn | simp [clsReg]
lemma rsOf_nodup (x : ℕ) (hx : x < nI) : (rsOf F m t b k k2 x).Nodup := by
rcases rsOf_cases F m t b k k2 x hx with ⟨i, -, e⟩ | ⟨i, -, e⟩ | ⟨-, -, e⟩ <;> rw [e]
· exact nodup_ofFn_emb _
· exact nodup_ofFn_emb _
· exact List.nodup_ofFn.mpr (fun j j' h => (fpf_inj (W_inj h)).2)
lemma bkOf_rsOf (x : ℕ) (hx : x < nI) (a : Fin NN) (ha : a ∈ rsOf F m t b k k2 x) :
bkOf a = 0 ∨ bkOf a = 26 := by
rcases mem_rsOf F m t b k k2 x hx a ha with ⟨i, j, -, rfl⟩ | ⟨i, j, -, rfl⟩ | ⟨j, rfl⟩
· exact Or.inl (bkOf_regE F m t b nI _)
· exact Or.inl (bkOf_regE F m t b nI _)
· exact Or.inr (bkOf_cls F m t b k k2 x hx j)
lemma rsOf_disj (x : ℕ) (hx : x < nI) (y : ℕ) (hy : y < nI) (hxy : x ≠ y) (a : Fin NN)
(hax : a ∈ rsOf F m t b k k2 x) (hay : a ∈ rsOf F m t b k k2 y) : False := by
have rc : ∀ (c : Bool) (i : Fin m) (j : Fin (bitsPerSymbol F)) (z : ℕ) (hz : z < nI) (j' : Fin (bitsPerSymbol F)),
a = regE F m t b nI (i, c, j) → a = W PP 26 (finProdFinEquiv (⟨z, hz⟩, j')) → False := by
intro c i j z hz j' e1 e2
have h1 : bkOf a = 0 := by rw [e1]; exact bkOf_regE F m t b nI _
have h2 : bkOf a = 26 := by rw [e2]; exact bkOf_cls F m t b k k2 _ _ _
rw [h1] at h2; exact absurd h2 (by decide)
rcases mem_rsOf F m t b k k2 x hx a hax with ⟨i, j, ex, ea⟩ | ⟨i, j, ex, ea⟩ | ⟨j, ea⟩ <;>
rcases mem_rsOf F m t b k k2 y hy a hay with ⟨i', j', ey, eb⟩ | ⟨i', j', ey, eb⟩ | ⟨j', eb⟩
· have := (regE F m t b nI).injective (ea.symm.trans eb)
simp only [Prod.mk.injEq] at this
exact hxy (by rw [ex, ey, this.1])
· have := (regE F m t b nI).injective (ea.symm.trans eb)
simp at this
· exact rc _ _ _ _ _ _ ea eb
· have := (regE F m t b nI).injective (ea.symm.trans eb)
simp at this
· have := (regE F m t b nI).injective (ea.symm.trans eb)
simp only [Prod.mk.injEq] at this
exact hxy (by rw [ex, ey, this.1])
· exact rc _ _ _ _ _ _ ea eb
· exact rc _ _ _ _ _ _ eb ea
· exact rc _ _ _ _ _ _ eb ea
· have := fpf_inj (W_inj (ea.symm.trans eb))
exact hxy (congrArg Fin.val this.1)
/-- The decoder ancillas and flag. -/
def asC : List (Fin NN) := blk 27
lemma asC_f0_nodup : (asC F m t b k k2 ++ [one 28 (sz_28 _)]).Nodup := by
refine nodup_app (blk_nodup _) (List.nodup_singleton _) ?_
intro q hq q' hq'
rw [List.mem_singleton] at hq'
subst hq'
have h1 : bkOf q = 27 := bkOf_of_mem_blk (P := PP) hq
rw [h1, bkOf_one]
decide
lemma bkOf_asC_f0 (a : Fin NN) (ha : a ∈ asC F m t b k k2 ++ [one 28 (sz_28 _)]) : bkOf a = 27 ∨ bkOf a = 28 := by
rcases List.mem_append.mp ha with h | h
· exact Or.inl (bkOf_of_mem_blk h)
· rw [List.mem_singleton] at h; subst h; exact Or.inr (bkOf_one _ _)
/-- **The concrete classical-decoder layout.** -/
noncomputable def clsLay : SymEnc.ClsLay (regE F m t b nI) (elemBits F) (decodeElem F) (Fq.decode_elemBits F) k k2 where
rs := rsOf F m t b k k2
as := asC F m t b k k2
f0 := one 28 (sz_28 _)
hlay := {
len := fun x hx => rsOf_length F m t b k k2 x hx
nd := fun x hx => rsOf_nodup F m t b k k2 x hx
disj := fun x hx y hy hxy a hax hay => rsOf_disj F m t b k k2 x hx y hy hxy a hax hay
scr := fun x hx a ha hs => by
rcases bkOf_rsOf F m t b k k2 x hx a ha with h | h <;>
rcases bkOf_asC_f0 F m t b k k2 a hs with h' | h' <;> rw [h] at h' <;> simp at h'
scrnd := asC_f0_nodup F m t b k k2 }
hin1 := fun i => rsOf_in1 F m t b k k2 i
hin2 := fun i => rsOf_in2 F m t b k k2 i
hfree := fun x hx hne q hq p e => by
rw [rsOf_other F m t b k k2 x (fun i => (hne i).1.symm) (fun i => (hne i).2.symm) hx] at hq
obtain ⟨j, rfl⟩ := List.mem_ofFn.mp hq
have e1 : bkOf (regE F m t b nI p) = 0 := bkOf_regE F m t b nI _
have e2 : bkOf (regE F m t b nI p) = 26 := by rw [e]; exact bkOf_cls F m t b k k2 _ _ _
rw [e1] at e2; exact absurd e2 (by decide)
hscr := fun q hq p e => by
rcases bkOf_asC_f0 F m t b k k2 q hq with h | h <;> rw [← e] at h <;> simp at h
hsz := by
show 4 * bitsPerSymbol F ≤ (blk (P := PP) 27).length + 2
rw [blk_length, sz_27]; show 4 * bitsPerSymbol F ≤ 4 * bitsPerSymbol F + 2; omega
end Lay
end OPI
end
-- ===== OPI.LayFull =====
section
/-!
# The concrete full decoder layout
-/
namespace OPI
namespace Lay
open TwoFoldOPI RelinProg
variable (F : AvgCaseTI.FieldPres) (m t b : ℕ) (k k2 : ℕ)
local notation "nI" => SymEnc.nIds m k k2
local notation "PP" => parOf F m t b (SymEnc.nIds m k k2)
local notation "NN" => total (parOf F m t b (SymEnc.nIds m k k2))
lemma RrE_hRd : ∀ i i' j j', RrE F m t b nI i j = RrE F m t b nI i' j' → i = i' ∧ j = j' :=
fun i i' j j' h => RrE_inj F m t b nI i i' j j' h
/-- The `R` register as a word. -/
def wRC : Fin (m * bitsPerSymbol F) ↪ Fin NN :=
SymEnc.wRof (F := F) (RrE F m t b nI) (RrE_hRd F m t b k k2)
lemma bkOf_wRC (x : Fin (m * bitsPerSymbol F)) : bkOf (wRC F m t b k k2 x) = 1 := bkOf_W _ _
lemma notMem_wRC {q : Fin NN} (hq : bkOf q ≠ 1) : q ∉ Set.range (wRC F m t b k k2) := by
rintro ⟨x, rfl⟩; exact hq (bkOf_wRC F m t b k k2 x)
lemma bkOf_epAll (ht : 1 ≤ t) (htb : t ≤ b) (i : Fin m) (q : Fin NN)
(hq : SymEnc.epAll ((realDec F m t b nI ht htb).W i) q) :
bkOf q ∈ ({0, 19, 20, 21, 22, 23, 24, 25} : Finset (Fin NB)) := by
rcases hq with h | h | h
· rcases h with h | h | h | h | h | h | h
· subst h; simp [realDec, coordW]
· subst h; simp [realDec, coordW]
· rw [bkOf_of_mem_blk h]; decide
· rw [bkOf_of_mem_blk h]; decide
· subst h; simp [realDec, coordW]
· rw [bkOf_of_mem_blk h]; decide
· rw [bkOf_of_mem_blk h]; decide
· obtain ⟨j, rfl⟩ := List.mem_ofFn.mp h; simp
· obtain ⟨j, rfl⟩ := List.mem_ofFn.mp h; simp
lemma bkOf_sysWire (ht : 1 ≤ t) (htb : t ≤ b) (i : Fin m) (c : Bool) (q : Fin NN)
(hq : ((realDec F m t b nI ht htb).Q i c).sysWire q) : bkOf q ≠ 1 := by
rcases hq with ⟨j, rfl⟩ | h | h | h | ⟨G, hG, h⟩
· simp [realDec, qq]
· simp only [realDec, qq] at h; rw [bkOf_of_mem_blk h]; decide
· simp only [realDec, qq] at h; rw [bkOf_of_mem_blk h]; decide
· simp only [realDec, qq] at h; subst h; simp only [bkOf_one]; decide
· simp only [realDec, qq] at hG
obtain ⟨g, rfl⟩ := List.mem_ofFn.mp hG
rcases h with ⟨j, rfl⟩ | ⟨j, rfl⟩ | ⟨j, rfl⟩ | h | h | h | h | h | h
· simp [qg, qlay, Function.Embedding.trans_apply]
· simp [qg, qlay]
· simp [qg, qlay]
· simp only [qg, qlay] at h; rw [bkOf_of_mem_blk h]; decide
· simp only [qg, qlay] at h; subst h; simp only [bkOf_one]; decide
· simp only [qg, qlay] at h; rw [bkOf_of_mem_blk h]; decide
· simp only [qg, qlay] at h; rw [bkOf_of_mem_blk h]; decide
· simp only [qg, qlay] at h
have := InS_asQ F m t b nI q h
intro e; rw [e] at this; revert this; decide
· simp only [qg, qlay] at h; subst h; simp only [bkOf_one]; decide
/-- **The concrete full decoder layout.** -/
noncomputable def decFull (ht : 1 ≤ t) (htb : t ≤ b) :
SymEnc.DecFull F (regE F m t b nI) b t k k2 (m * bitsPerSymbol F) where
D := realDec F m t b nI ht htb
C := clsLay F m t b k k2
clQ := clQ F m t b nI
hclQ := fun _ _ => rfl
wR := wRC F m t b k k2
hep := fun i q hq => by
have h := bkOf_epAll F m t b k k2 ht htb i q hq
refine ⟨notMem_clQ F m t b nI ?_, notMem_wRC F m t b k k2 ?_⟩
· intro h'; revert h h'; generalize bkOf q = z; decide +revert
· intro h'; rw [h'] at h; revert h; decide
hqR := fun i c q hq => notMem_wRC F m t b k k2 (bkOf_sysWire F m t b k k2 ht htb i c q hq)
hcls := fun q hq => by
have h : bkOf q = 0 ∨ bkOf q = 26 ∨ bkOf q = 27 ∨ bkOf q = 28 := by
rcases hq with ⟨x, hx, h⟩ | h | h
· rcases bkOf_rsOf F m t b k k2 x hx q h with h | h
· exact Or.inl h
· exact Or.inr (Or.inl h)
· exact Or.inr (Or.inr (Or.inl (bkOf_of_mem_blk h)))
· subst h; exact Or.inr (Or.inr (Or.inr (bkOf_one _ (sz_28 _))))
refine ⟨notMem_clQ F m t b nI ?_, notMem_wRC F m t b k k2 ?_⟩
· rcases h with h | h | h | h <;> rw [h] <;> decide
· rcases h with h | h | h | h <;> rw [h] <;> decide
end Lay
end OPI
end
-- ===== OPI.LayPrep =====
section
/-!
# The concrete preparation layout
-/
namespace OPI
namespace Lay
open TwoFoldOPI RelinProg SymEnc
variable (F : AvgCaseTI.FieldPres) (m t b : ℕ) (k k2 : ℕ)
local notation "nI" => SymEnc.nIds m k k2
local notation "PP" => parOf F m t b (SymEnc.nIds m k k2)
local notation "NN" => total (parOf F m t b (SymEnc.nIds m k k2))
variable (ht : 1 ≤ t) (htb : t ≤ b)
lemma bkOf_resAll (r : Res NN) (hr : r ∈ resAll (realDec F m t b nI ht htb)) (x : Fin r.k) : bkOf (r.w x) = 2 := by
simp only [resAll, resC, List.mem_flatMap, List.mem_append] at hr
obtain ⟨i, -, h | h⟩ := hr
· exact bkOf_res F m t b nI ht htb i false r h x
· exact bkOf_res F m t b nI ht htb i true r h x
lemma notMem_res_of_bkOf (q : Fin NN) (hq : bkOf q ≠ 2) (r : Res NN) (hr : r ∈ resAll (realDec F m t b nI ht htb)) :
q ∉ Set.range r.w := by
rintro ⟨x, rfl⟩; exact hq (bkOf_resAll F m t b k k2 ht htb r hr x)
variable {kd : ℕ} (piv : Fin kd → Fin m) (β : Fin m → F.F)
lemma job_cases (j : RJob NN) (hj : j ∈ allJobs (realDec F m t b nI ht htb) (RrE F m t b nI) piv β) :
(j.k = bitsPerSymbol F ∧ ∀ x, bkOf (j.w x) = 1) ∨ (j.k = Fq.w F ∧ ∀ x, bkOf (j.w x) = 2) ∨
(j.k = bitsPerSymbol F ∧ ∀ x, bkOf (j.w x) = 0) := by
simp only [allJobs, List.mem_append, List.mem_map, List.mem_finRange, true_and] at hj
rcases hj with (⟨jj, rfl⟩ | ⟨r, hr, rfl⟩) | ⟨i, rfl⟩
· exact Or.inl ⟨rfl, fun x => bkOf_W _ _⟩
· right; left
refine ⟨?_, fun x => bkOf_resAll F m t b k k2 ht htb r hr x⟩
simp only [resAll, resC, List.mem_flatMap, List.mem_append] at hr
obtain ⟨i, -, h | h⟩ := hr <;> obtain ⟨g, rfl⟩ := mem_resQ F m t b nI ht htb _ _ r h <;> rfl
· exact Or.inr (Or.inr ⟨rfl, fun x => bkOf_W _ _⟩)
lemma job_nodup (j : RJob NN) (hj : j ∈ allJobs (realDec F m t b nI ht htb) (RrE F m t b nI) piv β) :
(List.ofFn j.w ++ [one (P := PP) 29 (sz_29 _)] ++ blk 31 ++ [one 30 (sz_30 _)]).Nodup ∧
j.k ≤ (blk (P := PP) 31).length + 2 := by
have hk : j.k ≤ bitsPerSymbol F + Fq.w F := by
rcases job_cases F m t b k k2 ht htb piv β j hj with ⟨h, -⟩ | ⟨h, -⟩ | ⟨h, -⟩ <;> rw [h] <;> omega
refine ⟨?_, by rw [blk_length, sz_31]; show j.k ≤ bitsPerSymbol F + Fq.w F + 2; omega⟩
have hS : ∃ z : Fin NB, (z = 0 ∨ z = 1 ∨ z = 2) ∧ ∀ x, bkOf (j.w x) = z := by
rcases job_cases F m t b k k2 ht htb piv β j hj with ⟨-, h⟩ | ⟨-, h⟩ | ⟨-, h⟩
· exact ⟨1, by decide, h⟩
· exact ⟨2, by decide, h⟩
· exact ⟨0, by decide, h⟩
obtain ⟨z, hz, hw⟩ := hS
have e : List.ofFn j.w ++ [one (P := PP) 29 (sz_29 _)] ++ blk 31 ++ [one 30 (sz_30 _)] =
[List.ofFn j.w, [one (P := PP) 29 (sz_29 _)], blk 31, [one 30 (sz_30 _)]].flatten := by
simp [List.append_assoc]
rw [e]
apply nodup_flatten_S' _ [{0, 1, 2}, {29}, {31}, {30}] 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
· refine ⟨List.nodup_ofFn.mpr j.w.injective, fun q hq => ?_⟩
obtain ⟨x, rfl⟩ := List.mem_ofFn.mp hq
rw [hw x]
rcases hz with h | h | h <;> rw [h] <;> simp
· exact ⟨List.nodup_singleton _, InS_single F m t b nI _ _⟩
· exact ⟨blk_nodup _, InS_blk _⟩
· exact ⟨List.nodup_singleton _, InS_single F m t b nI _ _⟩
· decide
lemma bk_pJobs (j : RJob NN) (hj : j ∈ (List.finRange kd).map (pJob (RrE F m t b nI) piv)) (x : Fin j.k) :
bkOf (j.res.w x) = 1 := by
obtain ⟨jj, -, rfl⟩ := List.mem_map.mp hj; exact bkOf_W _ _
lemma bk_rJobs (j : RJob NN) (hj : j ∈ (resAll (realDec F m t b nI ht htb)).map (rJob F)) (x : Fin j.k) :
bkOf (j.res.w x) = 2 := by
obtain ⟨r, hr, rfl⟩ := List.mem_map.mp hj; exact bkOf_resAll F m t b k k2 ht htb r hr x
lemma bk_sJobs (j : RJob NN) (hj : j ∈ (List.finRange m).map (sJob (regE F m t b nI) β)) (x : Fin j.k) :
bkOf (j.res.w x) = 0 := by
obtain ⟨i, -, rfl⟩ := List.mem_map.mp hj; exact bkOf_W _ _
lemma disj_of_bk (j j' : RJob NN) (z z' : Fin NB) (hz : z ≠ z') (h : ∀ x, bkOf (j.res.w x) = z)
(h' : ∀ x, bkOf (j'.res.w x) = z') : Res.Disj j.res j'.res := by
intro x x' e
have := h x
rw [e, h' x'] at this
exact hz this.symm
lemma jobs_pairwise (hpivi : Function.Injective piv) :
((allJobs (realDec F m t b nI ht htb) (RrE F m t b nI) piv β).map RJob.res).Pairwise Res.Disj := by
unfold allJobs
simp only [List.map_append]
rw [List.pairwise_append, List.pairwise_append]
refine ⟨⟨?_, ?_, ?_⟩, ?_, ?_⟩
· -- pivot jobs
rw [List.pairwise_map]
rw [List.pairwise_map]
refine (List.nodup_finRange kd).pairwise_of_forall_ne (fun jj _ jj' _ hne => ?_)
intro x x' e
exact hne (hpivi (RrE_inj F m t b nI _ _ _ _ e).1)
· -- resource jobs
rw [List.pairwise_map, List.pairwise_map]
exact (resAll_pairwise (realDec F m t b nI ht htb)).imp (fun h => h)
· intro a ha a' ha'
obtain ⟨j, hj, rfl⟩ := List.mem_map.mp ha
obtain ⟨j', hj', rfl⟩ := List.mem_map.mp ha'
exact disj_of_bk F m t b k k2 j j' 1 2 (by decide) (bk_pJobs F m t b k k2 piv j hj)
(bk_rJobs F m t b k k2 ht htb j' hj')
· -- `S` jobs
rw [List.pairwise_map, List.pairwise_map]
refine (List.nodup_finRange m).pairwise_of_forall_ne (fun i _ i' _ hne => ?_)
intro x x' e
have := (regE F m t b nI).injective e
simp only [Prod.mk.injEq] at this
exact hne this.1
· intro a ha a' ha'
obtain ⟨j', hj', rfl⟩ := List.mem_map.mp ha'
rcases List.mem_append.mp ha with h | h
· obtain ⟨j, hj, rfl⟩ := List.mem_map.mp h
exact disj_of_bk F m t b k k2 j j' 1 0 (by decide) (bk_pJobs F m t b k k2 piv j hj)
(bk_sJobs F m t b k k2 β j' hj')
· obtain ⟨j, hj, rfl⟩ := List.mem_map.mp h
exact disj_of_bk F m t b k k2 j j' 2 0 (by decide) (bk_rJobs F m t b k k2 ht htb j hj)
(bk_sJobs F m t b k k2 β j' hj')
lemma bk_mem_cons_app (q : Fin NN) (k0 : Fin NB) (k1 k2' : Fin NB) (h0 : sz PP k0 = 1)
(hq : q ∈ one (P := PP) k0 h0 :: blk k1 ++ blk k2') : bkOf q = k0 ∨ bkOf q = k1 ∨ bkOf q = k2' := by
simp only [List.cons_append, List.mem_cons, List.mem_append] at hq
rcases hq with h | h | h
· subst h; exact Or.inl (bkOf_one _ _)
· exact Or.inr (Or.inl (bkOf_of_mem_blk h))
· exact Or.inr (Or.inr (bkOf_of_mem_blk h))
lemma bk_mem_app_one (q : Fin NN) (k1 k2' k0 : Fin NB) (h0 : sz PP k0 = 1)
(hq : q ∈ blk (P := PP) k1 ++ blk k2' ++ [one k0 h0]) : bkOf q = k1 ∨ bkOf q = k2' ∨ bkOf q = k0 := by
simp only [List.mem_append, List.mem_singleton] at hq
rcases hq with (h | h) | h
· exact Or.inl (bkOf_of_mem_blk h)
· exact Or.inr (Or.inl (bkOf_of_mem_blk h))
· subst h; exact Or.inr (Or.inr (bkOf_one _ _))
lemma reg_ne_of_bk (p : Fin m × Bool × Fin (bitsPerSymbol F)) (q : Fin NN) (hq : bkOf q ≠ 0) :
regE F m t b nI p ≠ q := fun e => hq (by rw [← e]; exact bkOf_W _ _)
lemma RrE_ne_of_bk (i : Fin m) (j : Fin (bitsPerSymbol F)) (q : Fin NN) (hq : bkOf q ≠ 1) :
RrE F m t b nI i j ≠ q := fun e => hq (by rw [← e]; exact bkOf_W _ _)
/-- **The concrete preparation layout.** -/
noncomputable def prepLay (G : Fin kd → Fin m → F.F) (hpivi : Function.Injective piv)
(hpiv : ∀ j j', G j (piv j') = if j = j' then 1 else 0) :
PrepLay (realDec F m t b nI ht htb) kd where
Rr := RrE F m t b nI
hRd := RrE_hRd F m t b k k2
piv := piv
hpivi := hpivi
G := G
hpiv := hpiv
fl := one 29 (sz_29 _)
f0 := one 30 (sz_30 _)
asR := blk 31
Z := blk 32
asL := blk 33
fL := one 34 (sz_34 _)
scr := blk 35
asP := blk 36
fP := one 37 (sz_37 _)
hRreg := fun i j p => reg_ne_of_bk F m t b k k2 p _ (by rw [bkOf_RrE]; decide)
hRres := fun r hr i j => notMem_res_of_bkOf F m t b k k2 ht htb _ (by rw [bkOf_RrE]; decide) r hr
hjob := fun β j hj => job_nodup F m t b k k2 ht htb piv β j hj
hjpair := fun β => jobs_pairwise F m t b k k2 ht htb piv β hpivi
hndL := fun p hp => by
have h12 : (List.ofFn (RrE F m t b nI (piv p.1)) ++ List.ofFn (RrE F m t b nI p.2)).Nodup := by
refine List.nodup_append.mpr ⟨nodup_ofFn_emb _, nodup_ofFn_emb _, ?_⟩
intro a ha a' ha' e
obtain ⟨x, rfl⟩ := List.mem_ofFn.mp ha
obtain ⟨x', rfl⟩ := List.mem_ofFn.mp ha'
exact hp p.1 (RrE_inj F m t b nI _ _ _ _ e).1
have e : List.ofFn (RrE F m t b nI (piv p.1)) ++ List.ofFn (RrE F m t b nI p.2) ++ blk 32 ++ blk 33 ++
[one 34 (sz_34 _)] = [List.ofFn (RrE F m t b nI (piv p.1)) ++ List.ofFn (RrE F m t b nI p.2), blk 32,
blk 33, [one 34 (sz_34 _)]].flatten := by simp [List.append_assoc]
rw [e]
apply nodup_flatten_S' _ [{1}, {32}, {33}, {34}] 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 ⟨h12, InS_app (InS_ofFn F m t b nI _ _ (fun j => by simp)) (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
hZ := by rw [blk_length, sz_32]; rfl
hlenL := by rw [blk_length, sz_33]; show bitsPerSymbol F + bitsPerSymbol F ≤ 2 * bitsPerSymbol F + 2; omega
hscL := fun i j => ⟨RrE_ne_of_bk F m t b k k2 i j _ (by rw [bkOf_one]; decide),
fun q hq => RrE_ne_of_bk F m t b k k2 i j q (by rw [bkOf_of_mem_blk hq]; decide),
fun q hq => RrE_ne_of_bk F m t b k k2 i j q (by rw [bkOf_of_mem_blk hq]; decide)⟩
hLoff := fun q hq => by
have h := bk_mem_cons_app F m t b k k2 q 34 33 32 (sz_34 _) hq
refine ⟨fun p => reg_ne_of_bk F m t b k k2 p q ?_, fun r hr => notMem_res_of_bkOf F m t b k k2 ht htb q ?_ r hr⟩
· rcases h with h | h | h <;> rw [h] <;> decide
· rcases h with h | h | h <;> rw [h] <;> decide
hsl := by rw [blk_length, sz_35]; rfl
hscr := blk_nodup _
hbl := by rw [blk_length, sz_36]; show 1 + b ≤ b + 2 * bitsPerSymbol F + 2; omega
hxl := by rw [blk_length, sz_36]; show bitsPerSymbol F + bitsPerSymbol F ≤ b + 2 * bitsPerSymbol F + 2; omega
hndP := fun i => by
have e : List.ofFn (RrE F m t b nI i) ++ List.ofFn (SymEnc.bReg (regE F m t b nI) i false) ++ blk 35 ++
blk 36 ++ [one 37 (sz_37 _)] = [List.ofFn (RrE F m t b nI i), List.ofFn (SymEnc.bReg (regE F m t b nI) i false),
blk 35, blk 36, [one 37 (sz_37 _)]].flatten := by simp [List.append_assoc]
rw [e]
apply nodup_flatten_S' _ [{1}, {0}, {35}, {36}, {37}] 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
· exact ⟨nodup_ofFn_emb _, InS_ofFn F m t b nI _ _ (fun j => by simp)⟩
· exact ⟨nodup_ofFn_emb _, InS_bReg F m t b nI i false⟩
· exact ⟨blk_nodup _, InS_blk _⟩
· exact ⟨blk_nodup _, InS_blk _⟩
· exact ⟨List.nodup_singleton _, InS_single F m t b nI _ _⟩
· decide
hPoff := fun q hq => by
have h := bk_mem_app_one F m t b k k2 q 35 36 37 (sz_37 _) hq
refine ⟨fun p => reg_ne_of_bk F m t b k k2 p q ?_,
fun r hr => notMem_res_of_bkOf F m t b k k2 ht htb q ?_ r hr, fun i j => RrE_ne_of_bk F m t b k k2 i j q ?_⟩
· rcases h with h | h | h <;> rw [h] <;> decide
· rcases h with h | h | h <;> rw [h] <;> decide
· rcases h with h | h | h <;> rw [h] <;> decide
end Lay
end OPI
end
-- ===== OPI.TrialInst =====
section
/-!
# The trial loop with the concrete decoder and subtraction
`le_lawP_trials` instantiated with `U = DecFull.U`, the register `R` holding words (`encW`), the
subtraction `R ⊖= O` (`subAll`), and the middle circuit `Cd ++ Cs ++ Cd⁻¹`.
-/
namespace OPI
namespace SymEnc
open QAlgorithms TwoFoldOPI
variable {F : AvgCaseTI.FieldPres} {n b t m k k2 : ℕ}
{reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
lemma outOf_setE {kR : ℕ} (wR : Fin kR ↪ Fin n) (Os : Fin m → List (Fin n))
(hOsR : ∀ i, ∀ q ∈ Os i, q ∉ Set.range wR) (z : Qubits n) (y : Qubits kR) :
outOf (F := F) Os (setE wR z y) = outOf Os z := by
unfold outOf; congr 1; funext i; congr 2
exact List.map_congr_left (fun q hq => setE_out _ _ _ _ (hOsR i q hq))
end SymEnc
end OPI
end
-- ===== OPI.Assemble =====
section
/-!
# Assembly: preparation, decoder, subtraction and trial loop
For the concrete decoder and preparation layouts, the trial loop started from `|0⟩ ⊗ grad` fails
with probability at most `(1 − w + w |D| (1 − P) + e)/(w P) + (1 − w P)^K`, where `P` is the
decoding probability bound of `real_accept`, `w` the preparation weight and `e` its phase error.
-/
namespace OPI
namespace SymEnc
open QAlgorithms TwoFoldOPI CoordSym
variable {F : AvgCaseTI.FieldPres} {n b t m k k2 : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
variable {reg : Fin m × Bool × Fin L ↪ Fin n}
/-- The decoding probability bound. -/
noncomputable def decP (F : AvgCaseTI.FieldPres) (b t m : ℕ) (E : ℝ) : ℝ :=
(max (Real.sqrt (1 - E) - m * (epsQ F b t * (2 + epsQ F b t))) 0) ^ 2
end SymEnc
end OPI
end
-- ===== OPI.RREF =====
section
/-!
# Reduced row echelon form by incremental insertion
A list of `(pivot, row)` pairs is kept in reduced form: distinct pivots, each row is `1` at its
own pivot and `0` at the other pivots. Inserting a vector reduces it by all rows at once, and if
something remains, normalizes it at its first nonzero column and clears that column from the
other rows. The span is preserved.
-/
namespace OPI
namespace RREF
variable {K : Type*} [Field K] [DecidableEq K] {m : ℕ}
/-- Reduced rows. -/
abbrev Rows (K : Type*) (m : ℕ) := List (Fin m × (Fin m → K))
/-- The reduction `v − Σ v(p) u`. -/
def reduce (B : Rows K m) (v : Fin m → K) : Fin m → K := v - (B.map fun pu => v pu.1 • pu.2).sum
/-- The first nonzero column. -/
def firstNZ (v : Fin m → K) : Option (Fin m) := (List.finRange m).find? fun c => v c ≠ 0
/-- Insert a vector. -/
def insert (B : Rows K m) (v : Fin m → K) : Rows K m :=
match firstNZ (reduce B v) with
| none => B
| some p =>
B.map (fun qu => (qu.1, qu.2 - qu.2 p • ((reduce B v p)⁻¹ • reduce B v))) ++
[(p, (reduce B v p)⁻¹ • reduce B v)]
/-- The rows of a family of vectors. -/
def rrefOf {r : ℕ} (H : Fin r → Fin m → K) : Rows K m :=
(List.finRange r).foldl (fun B i => insert B (H i)) []
/-- The invariant. -/
structure Inv (B : Rows K m) : Prop where
nodup : (B.map Prod.fst).Nodup
one : ∀ pu ∈ B, pu.2 pu.1 = 1
zero : ∀ pu ∈ B, ∀ qu ∈ B, pu.1 ≠ qu.1 → qu.2 pu.1 = 0
lemma inv_nil : Inv ([] : Rows K m) := ⟨by simp, by simp, by simp⟩
lemma sum_at (B : Rows K m) (f : Fin m × (Fin m → K) → K) (c : Fin m) :
(B.map fun pu => f pu • pu.2).sum c = (B.map fun pu => f pu * pu.2 c).sum := by
induction B with
| nil => simp
| cons pu B ih => simp [ih]
lemma reduce_piv (B : Rows K m) (hB : Inv B) (v : Fin m → K) (pu : Fin m × (Fin m → K)) (hpu : pu ∈ B) :
reduce B v pu.1 = 0 := by
unfold reduce
rw [Pi.sub_apply, sum_at]
have : (B.map fun qu => v qu.1 * qu.2 pu.1).sum = v pu.1 := by
obtain ⟨l1, l2, rfl⟩ := List.append_of_mem hpu
have hnd := hB.nodup
simp only [List.map_append, List.map_cons, List.sum_append, List.sum_cons]
rw [hB.one pu hpu, mul_one]
have h1 : (l1.map fun qu => v qu.1 * qu.2 pu.1).sum = 0 := by
refine List.sum_eq_zero (fun x hx => ?_)
obtain ⟨qu, hqu, rfl⟩ := List.mem_map.mp hx
rw [hB.zero pu hpu qu (by simp [hqu]) ?_, mul_zero]
intro e
simp only [List.map_append, List.map_cons] at hnd
have := List.nodup_append.mp hnd
exact this.2.2 qu.1 (List.mem_map.mpr ⟨qu, hqu, rfl⟩) pu.1 (by simp) e.symm
have h2 : (l2.map fun qu => v qu.1 * qu.2 pu.1).sum = 0 := by
refine List.sum_eq_zero (fun x hx => ?_)
obtain ⟨qu, hqu, rfl⟩ := List.mem_map.mp hx
rw [hB.zero pu hpu qu (by simp [hqu]) ?_, mul_zero]
intro e
simp only [List.map_append, List.map_cons] at hnd
have := List.nodup_cons.mp (List.nodup_append.mp hnd).2.1
exact this.1 (by rw [e]; exact List.mem_map.mpr ⟨qu, hqu, rfl⟩)
rw [h1, h2]; ring
rw [this, sub_self]
lemma firstNZ_spec {v : Fin m → K} {p : Fin m} (h : firstNZ v = some p) : v p ≠ 0 := by
unfold firstNZ at h
have := List.find?_some h
simpa using this
theorem inv_insert (B : Rows K m) (hB : Inv B) (v : Fin m → K) : Inv (insert B v) := by
unfold insert
split
· exact hB
· rename_i p hp
set v' := reduce B v
have hvp := firstNZ_spec hp
set row := (v' p)⁻¹ • v'
have hrowp : row p = 1 := by simp [row, inv_mul_cancel₀ hvp]
have hrowq : ∀ qu ∈ B, row qu.1 = 0 := fun qu hqu => by
simp [row, reduce_piv B hB v qu hqu, v']
have hpB : ∀ qu ∈ B, qu.1 ≠ p := fun qu hqu e => by
have := reduce_piv B hB v qu hqu; rw [e] at this; exact hvp this
refine ⟨?_, ?_, ?_⟩
· simp only [List.map_append, List.map_map, List.map_cons, List.map_nil]
rw [List.nodup_append]
refine ⟨by simpa [Function.comp_def] using hB.nodup, List.nodup_singleton _, ?_⟩
intro a ha b hb
simp only [List.mem_singleton] at hb
subst hb
obtain ⟨qu, hqu, rfl⟩ := List.mem_map.mp ha
exact hpB qu hqu
· intro pu hpu
simp only [List.mem_append, List.mem_map, List.mem_singleton] at hpu
rcases hpu with ⟨qu, hqu, rfl⟩ | rfl
· simp only [Pi.sub_apply, Pi.smul_apply, smul_eq_mul]
rw [hB.one qu hqu, hrowq qu hqu, mul_zero, sub_zero]
· exact hrowp
· intro pu hpu qu hqu hne
simp only [List.mem_append, List.mem_map, List.mem_singleton] at hpu hqu
rcases hpu with ⟨pu', hpu', rfl⟩ | rfl <;> rcases hqu with ⟨qu', hqu', rfl⟩ | rfl
· simp only [Pi.sub_apply, Pi.smul_apply, smul_eq_mul] at hne ⊢
rw [hB.zero pu' hpu' qu' hqu' hne, hrowq pu' hpu', mul_zero, sub_zero]
· exact hrowq pu' hpu'
· simp only [Pi.sub_apply, Pi.smul_apply, smul_eq_mul]
rw [hrowp, mul_one, sub_self]
· exact absurd rfl hne
theorem inv_rrefOf {r : ℕ} (H : Fin r → Fin m → K) : Inv (rrefOf H) := by
unfold rrefOf
suffices ∀ (l : List (Fin r)) (B : Rows K m), Inv B → Inv (l.foldl (fun B i => insert B (H i)) B) from
this _ _ inv_nil
intro l
induction l with
| nil => intro B hB; exact hB
| cons i l ih => intro B hB; exact ih _ (inv_insert B hB (H i))
/-! ## Spans -/
/-- The span of the rows. -/
def rowSpan (B : Rows K m) : Submodule K (Fin m → K) := Submodule.span K {x | x ∈ B.map Prod.snd}
/-! ## The basis -/
variable (B : Rows K m)
/-- The rows as a family. -/
def G : Fin B.length → Fin m → K := fun j => (B.get j).2
/-- The pivots. -/
def piv : Fin B.length → Fin m := fun j => (B.get j).1
variable {B}
lemma piv_injective (hB : Inv B) : Function.Injective (piv B) := by
intro j j' h
have hl := hB.nodup
have := (hl.getElem_inj_iff (i := j.val) (j := j'.val) (hi := by simp) (hj := by simp)).mp
(by simpa [piv] using h)
exact Fin.ext this
lemma G_piv (hB : Inv B) (j j' : Fin B.length) : G B j (piv B j') = if j = j' then 1 else 0 := by
split_ifs with h
· subst h; exact hB.one _ (List.get_mem _ _)
· exact hB.zero _ (List.get_mem _ _) _ (List.get_mem _ _) (fun e => h (piv_injective hB e).symm)
/-! ## The nullspace basis -/
variable (B)
/-- The free columns. -/
def free : List (Fin m) := (List.finRange m).filter fun c => c ∉ B.map Prod.fst
/-- The row with pivot `c`, if any. -/
def pivRow (c : Fin m) : Option (Fin m → K) := (B.find? fun pu => pu.1 = c).map Prod.snd
/-- The nullspace basis vector of a free column. -/
def NV (f : Fin (free B).length) : Fin m → K := fun c =>
if c = (free B).get f then 1 else
match pivRow B c with
| some u => -u ((free B).get f)
| none => 0
/-- Its pivot (the free column). -/
def pivN (f : Fin (free B).length) : Fin m := (free B).get f
variable {B}
lemma free_nodup : (free B).Nodup := (List.nodup_finRange m).filter _
lemma mem_free {c : Fin m} : c ∈ free B ↔ c ∉ B.map Prod.fst := by simp [free]
lemma pivN_injective : Function.Injective (pivN B) := by
intro f f' h
exact Fin.ext ((free_nodup.getElem_inj_iff).mp h)
lemma pivRow_none {c : Fin m} (hc : c ∉ B.map Prod.fst) : pivRow B c = none := by
unfold pivRow
rw [Option.map_eq_none_iff, List.find?_eq_none]
intro pu hpu h
exact hc (List.mem_map.mpr ⟨pu, hpu, by simpa using h⟩)
lemma NV_free (f f' : Fin (free B).length) : NV B f (pivN B f') = if f = f' then 1 else 0 := by
unfold NV pivN
have hf' : (free B).get f' ∉ B.map Prod.fst := mem_free.mp (List.get_mem _ _)
by_cases h : f = f'
· subst h; simp
· rw [if_neg (fun e => h (pivN_injective e.symm)), pivRow_none hf', if_neg h]
/-- The orthogonality conditions of the rows. -/
def Orth (B : Rows K m) (x : Fin m → K) : Prop := ∀ pu ∈ B, pu.2 ⬝ᵥ x = 0
end RREF
end OPI
end
-- ===== OPI.RREFCode =====
section
/-!
# A basis of `D = (codeOf gen H)^⊥` with an identity on pivot columns
Parity-check case (`gen = false`): `D` is the row space of `H`; the basis is the RREF rows.
Generator case (`gen = true`): `D = {x : Hx = 0}`; the basis is the standard nullspace basis.
-/
namespace OPI
open RREF
variable {K : Type*} [Field K] [DecidableEq K] {m r : ℕ}
/-- A basis with pivots. -/
structure BasisP (K : Type*) (m : ℕ) where
kd : ℕ
G : Fin kd → Fin m → K
piv : Fin kd → Fin m
/-- **The basis of `D`.** -/
def basisOf (gen : Bool) (H : Matrix (Fin r) (Fin m) K) : BasisP K m :=
if gen then ⟨_, NV (rrefOf fun i => H i), pivN (rrefOf fun i => H i)⟩
else ⟨_, RREF.G (rrefOf fun i => H i), RREF.piv (rrefOf fun i => H i)⟩
theorem basisOf_piv_injective (gen : Bool) (H : Matrix (Fin r) (Fin m) K) :
Function.Injective (basisOf gen H).piv := by
cases gen
· exact piv_injective (inv_rrefOf _)
· exact pivN_injective
theorem basisOf_hpiv (gen : Bool) (H : Matrix (Fin r) (Fin m) K) (j j' : Fin (basisOf gen H).kd) :
(basisOf gen H).G j ((basisOf gen H).piv j') = if j = j' then 1 else 0 := by
cases gen
· exact G_piv (inv_rrefOf _) j j'
· exact NV_free j j'
/-! ## The span, its size, and the Schur square -/
variable [Fintype K]
open Classical in
/-- `D` as a finset. -/
noncomputable def Dfin (gen : Bool) (H : Matrix (Fin r) (Fin m) K) : Finset (Fin m → K) :=
Finset.univ.filter fun d => d ∈ CodingTheory.dualCode K (Fin m) (TwoFoldOPI.codeOf gen H)
/-- The pairwise products of the basis rows. -/
def bWof (gen : Bool) (H : Matrix (Fin r) (Fin m) K) :
Fin ((basisOf gen H).kd * (basisOf gen H).kd) → Fin m → K :=
fun x => (basisOf gen H).G (finProdFinEquiv.symm x).1 * (basisOf gen H).G (finProdFinEquiv.symm x).2
end OPI
end
-- ===== OPI.LayTrial =====
section
/-!
# The trial loop on the concrete layout
-/
namespace OPI
namespace Lay
open QAlgorithms TwoFoldOPI RelinProg SymEnc GEP
/-! ## Output ids -/
variable (F : AvgCaseTI.FieldPres) (m t b : ℕ) (k k2 : ℕ)
local notation "nI" => SymEnc.nIds m k k2
local notation "PP" => parOf F m t b (SymEnc.nIds m k k2)
local notation "NN" => total (parOf F m t b (SymEnc.nIds m k k2))
/-! ## The readout -/
/-- The readout wires: the `S` registers, word bit `(i, j) ↦ i L + j`. -/
def qS : Fin (m * bitsPerSymbol F) → Fin NN :=
fun x => regE F m t b nI ((finProdFinEquiv.symm x).1, false, (finProdFinEquiv.symm x).2)
variable (ht : 1 ≤ t) (htb : t ≤ b)
end Lay
/-! ## The concrete trial loop -/
namespace Lay
open QAlgorithms TwoFoldOPI RelinProg SymEnc GEP
variable (F : AvgCaseTI.FieldPres) (m t b : ℕ) {r : ℕ} (gen : Bool) (H : Matrix (Fin r) (Fin m) F.F)
/-- The basis size. -/
noncomputable def kdOf : ℕ := (basisOf gen H).kd
local notation "KD" => kdOf F m gen H
local notation "nI" => SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)
local notation "PP" => parOf F m t b (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H))
local notation "NN" => total (parOf F m t b (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)))
variable (ht : 1 ≤ t) (htb : t ≤ b)
/-- The concrete decoder. -/
noncomputable def decC := decFull F m t b KD (KD * KD) ht htb
/-- The concrete preparation layout. -/
noncomputable def prepC : PrepLay (decC F m t b gen H ht htb).D KD :=
prepLay F m t b KD (KD * KD) ht htb (basisOf gen H).piv (basisOf gen H).G (basisOf_piv_injective gen H)
(basisOf_hpiv gen H)
/-- The output registers. -/
noncomputable def OsC (i : Fin m) : List (Fin NN) :=
(decC F m t b gen H ht htb).C.rs (RelinProg.outId (m := m) (k := KD) (k2 := KD * KD) i)
/-- The concrete subtraction circuit. -/
noncomputable def CsC : Circuit htcxGateSet NN :=
revCirc (subAll (F := F) (RrE F m t b nI) (OsC F m t b gen H ht htb) (blk 12) (blk 13) (one 14 (sz_14 _))
(List.finRange m))
/-- **The concrete trial loop.** -/
noncomputable def trialsC {c : ℕ} (β : Fin m → F.F) (dz dst : Fin c) (slot : Fin (m * bitsPerSymbol F) → Fin c)
(hslot : Function.Injective slot) (R K : ℕ) : Prog (NN + b) c (m * bitsPerSymbol F) :=
retry (trialStep ((prepC F m t b gen H ht htb).pre β dst R)
((decC F m t b gen H ht htb).circ β (basisOf gen H).G (bWof gen H) ++ relocCirc sysEmb (CsC F m t b gen H ht htb) ++
invCirc ((decC F m t b gen H ht htb).circ β (basisOf gen H).G (bWof gen H))) dz
(List.ofFn (decC F m t b gen H ht htb).wR)
(measAll (readList (fun j => Fin.castAdd b (qS F m t b KD (KD * KD) j)) slot)
(.halt (copyCirc slot) (copyCirc_wf slot)))) K
end Lay
end OPI
end
-- ===== OPI.GradStage =====
section
/-!
# M5: gradient preparation — one stage
Stage `j` decides bit `j` of the label (invariant: label `≡ 1 mod 2^j`) by a majority of `Nt`
Hadamard tests on `INC^{2^{b−j−1}}` (with `T^k` correction), then multiplies by `1 + 2^j` if the
decision is `1`.
-/
namespace OPI
open QAlgorithms
variable {b : ℕ}
/-- The residual phase of stage `j` with correction `T^k`. -/
noncomputable def rho (b j k : ℕ) : ℂ :=
ex b ((2 ^ (b - j - 1) : ℕ) : ℤ) * Complex.exp (Complex.I * Real.pi / 4) ^ k
/-! ## Labels and the inverse of `1 + 2^j` -/
/-- Labels `≡ 1 mod 2^j`. -/
def Ej (b j : ℕ) (x : ZMod (2 ^ b)) : Prop := x.val % 2 ^ j = 1
instance (b j : ℕ) : DecidablePred (Ej b j) := fun x => by unfold Ej; infer_instance
/-- Bit `j` of a label. -/
def bitj (b j : ℕ) (x : ZMod (2 ^ b)) : Bool := decide (x.val / 2 ^ j % 2 = 1)
/-- The inverse of `1 + 2^j` modulo `2^b`. -/
noncomputable def uInv (b j : ℕ) : ℕ := (((1 + 2 ^ j : ℕ) : ZMod (2 ^ b))⁻¹).val
lemma coprime_uJ (b j : ℕ) (hj : 1 ≤ j) : Nat.Coprime (1 + 2 ^ j) (2 ^ b) := by
apply Nat.Coprime.pow_right
rw [Nat.coprime_two_right]
exact Even.one_add (by rw [Nat.even_pow]; exact ⟨even_two, by omega⟩)
lemma uInv_mul (b j : ℕ) (hj : 1 ≤ j) :
((1 + 2 ^ j : ℕ) : ZMod (2 ^ b)) * ((uInv b j : ℕ) : ZMod (2 ^ b)) = 1 := by
rw [uInv, ZMod.natCast_zmod_val]
exact ZMod.coe_mul_inv_eq_one _ (coprime_uJ b j hj)
/-- Multiplication by `(1 + 2^j)^{-1}` on labels. -/
noncomputable def sigmaJ (b j : ℕ) (hj : 1 ≤ j) : ZMod (2 ^ b) ≃ ZMod (2 ^ b) where
toFun x := x * (uInv b j : ZMod (2 ^ b))
invFun y := y * ((1 + 2 ^ j : ℕ) : ZMod (2 ^ b))
left_inv x := by
simp only; rw [mul_assoc, mul_comm ((uInv b j : ℕ) : ZMod (2 ^ b)), uInv_mul b j hj, mul_one]
right_inv y := by
simp only; rw [mul_assoc, uInv_mul b j hj, mul_one]
/-! ## One stage -/
variable {N c' out : ℕ}
/-- Stage `j`. -/
noncomputable def stageP (w : Fin b ↪ Fin N) (c : Fin N) (as : List (Fin N)) (dst : Fin c')
(j k Nt : ℕ) (P : Prog N c' out) : Prog N c' out :=
majP w c as (b - j - 1) k dst Nt P ((circSeg (revCirc (mulGates as (List.ofFn w) j (b - j)))).prog P) Nt 0
/-! ## The chain of stages -/
/-- The error of stage `j`. -/
noncomputable def errJ (b j k Nt : ℕ) : ℝ := potG (Complex.normSq ((1 - rho b j k) / 2)) Nt Nt 0
/-- Stages `j0, …, j0 + n − 1`. -/
noncomputable def chainP (w : Fin b ↪ Fin N) (c : Fin N) (as : List (Fin N)) (dst : Fin c')
(ks : ℕ → ℕ) (Nt : ℕ) : ℕ → ℕ → Prog N c' out → Prog N c' out
| _, 0, P => P
| j0, n + 1, P => stageP w c as dst j0 (ks j0) Nt (chainP w c as dst ks Nt (j0 + 1) n P)
end OPI
end
-- ===== OPI.GradEnds =====
section
/-!
# M5: gradient preparation — the two ends
Character sums over `ZMod 2^b`, orthonormality of `ê_x` and the norm of label sums; the start state
`(|0⟩ − |2^{b−1}⟩)/√2` as a sum over odd labels; the final density split onto `ê_1`.
-/
namespace OPI
open QAlgorithms
variable {b : ℕ}
variable {N : ℕ}
/-- Norm of a function on the outside of `w`. -/
noncomputable def nsqO {w : Fin b ↪ Fin N} (ψ : (Outside w → Bool) → ℂ) : ℝ := ∑ o, Complex.normSq (ψ o)
/-! ## The start state -/
/-- The start coefficients: `√(2/2^b)` on odd labels, `0` on even ones. -/
noncomputable def c0 (b : ℕ) (x : ZMod (2 ^ b)) : ℂ :=
((Real.sqrt 2 : ℂ) * ((Real.sqrt (2 ^ b) : ℝ) : ℂ)⁻¹) * (1 - ex b ((x.val * 2 ^ (b - 1) : ℕ) : ℤ)) / 2
/-- The gradient register cleared, with `ψ` on the rest. -/
noncomputable def zeroG (w : Fin b ↪ Fin N) (ψ : (Outside w → Bool) → ℂ) : Qubits N → ℂ :=
fun z => (if z ∘ w = fun _ => false then 1 else 0) * ψ (fun o => z o.1)
/-- The start circuit: `X` then `H` on the most significant gradient qubit. -/
noncomputable def startC (w : Fin b ↪ Fin N) (hb : 0 < b) : Circuit htcxGateSet N :=
revCirc [RGate.x (w ⟨0, hb⟩)] ++ [hApp (w ⟨0, hb⟩)]
/-! ## The final density split -/
/-! ## The gradient preparation -/
/-- The gradient preparation followed by `P`. -/
noncomputable def gradProg (w : Fin b ↪ Fin N) (hb : 0 < b) (c : Fin N) (as : List (Fin N)) {c' out : ℕ}
(dst : Fin c') (ks : ℕ → ℕ) (Nt : ℕ) (P : Prog N c' out) : Prog N c' out :=
(circSeg (startC w hb)).prog (chainP w c as dst ks Nt 1 (b - 1) P)
end OPI
end
-- ===== OPI.GradNum =====
section
/-!
# M5: gradient preparation — numerics of the stage errors
With corrections `T^6` (stage 1), `T^7` (stage 2) and none from stage 3 on, every stage errs with
probability at most `(2/5)^Nt`.
-/
namespace OPI
open QAlgorithms
/-- The corrections. -/
def ksT (j : ℕ) : ℕ := if j = 1 then 6 else if j = 2 then 7 else 0
end OPI
end
-- ===== OPI.GradLayout =====
section
/-!
# M5: gradient preparation on the layout `n + b`
The gradient register is the last `b` qubits; the rest is the cleared system register.
-/
namespace OPI
open QAlgorithms
variable {n b : ℕ}
/-- The cleared system register, as a function on the outside of the gradient register. -/
def sysPsi : (Outside (gradEmb (n := n) (b := b)) → Bool) → ℂ :=
fun o => if ∀ a, o a = false then 1 else 0
end OPI
end
-- ===== OPI.Final =====
section
/-!
# The full quantum program: gradient preparation, then the trial loop
-/
namespace OPI
open QAlgorithms QAlgorithms.OPI TwoFoldOPI
namespace Lay
open SymEnc
variable (F : AvgCaseTI.FieldPres) (m t : ℕ) (b' : ℕ) {r : ℕ} (gen : Bool) (H : Matrix (Fin r) (Fin m) F.F)
local notation "KD" => kdOf F m gen H
local notation "nI" => SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)
local notation "PP" => parOf F m t (b' + 1) (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H))
local notation "NN" => total (parOf F m t (b' + 1) (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)))
/-- The gradient-preparation control. -/
noncomputable def gCtl : Fin (NN + (b' + 1)) := Fin.castAdd (b' + 1) (one (P := PP) 38 (sz_38 _))
/-- The gradient-preparation ancillas. -/
noncomputable def gAs : List (Fin (NN + (b' + 1))) := (blk (P := PP) 39).map (Fin.castAdd (b' + 1))
variable (ht : 1 ≤ t) (htb : t ≤ b' + 1)
/-- **The full quantum program.** -/
noncomputable def progQ {c : ℕ} (β : Fin m → F.F) (dG dz dst : Fin c) (slot : Fin (m * bitsPerSymbol F) → Fin c)
(hslot : Function.Injective slot) (R K Nt : ℕ) : Prog (NN + (b' + 1)) c (m * bitsPerSymbol F) :=
gradProg (gradEmb (n := NN) (b := b' + 1)) (Nat.succ_pos b') (gCtl F m t b' gen H) (gAs F m t b' gen H) dG ksT Nt
(trialsC F m t (b' + 1) gen H ht htb β dz dst slot hslot R K)
end Lay
end OPI
end
-- ===== OPI.FinalNum =====
section
/-!
# Numerics of the final bound
-/
namespace OPI
open QAlgorithms TwoFoldOPI
namespace SymEnc
variable {F : AvgCaseTI.FieldPres} {n m kd b t : ℕ}
end SymEnc
/-! ## The abstract numerics -/
/-! ## The weight of the repeat-until-success stages -/
namespace SymEnc
variable {F : AvgCaseTI.FieldPres} {n m kd b t : ℕ}
end SymEnc
/-! ## The precision parameters -/
/-- Half the number of gradient bits. -/
def Bpar (T m L : ℕ) : ℕ := T + m * L + m + 2 * L + 12
/-! ## The final arithmetic -/
end OPI
end
-- ===== OPI.FinalBound =====
section
/-!
# The final bound of the quantum program (`D ≠ ⊥`)
-/
namespace OPI
open QAlgorithms TwoFoldOPI
/-! ## Small numeric facts -/
namespace Lay
open SymEnc
variable (F : AvgCaseTI.FieldPres) (m : ℕ) {r : ℕ} (gen : Bool) (H : Matrix (Fin r) (Fin m) F.F) (T : ℕ)
local notation "LL" => bitsPerSymbol F
local notation "BB" => Bpar T m (bitsPerSymbol F)
local notation "KD" => kdOf F m gen H
lemma tB_pos : 1 ≤ 2 * Bpar T m (bitsPerSymbol F) := by unfold Bpar; omega
lemma tB_le : 2 * Bpar T m (bitsPerSymbol F) ≤ 2 * Bpar T m (bitsPerSymbol F) - 1 + 1 := by omega
local notation "NNf" => total (parOf F m (2 * Bpar T m (bitsPerSymbol F)) (2 * Bpar T m (bitsPerSymbol F) - 1 + 1)
(SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)))
/-- The number of repeat-until-success jobs. -/
noncomputable def numJobs (β : Fin m → F.F) : ℕ :=
(allJobs (decC F m (2 * BB) (2 * BB - 1 + 1) gen H (tB_pos F m T) (tB_le F m T)).D
(prepC F m (2 * BB) (2 * BB - 1 + 1) gen H (tB_pos F m T) (tB_le F m T)).Rr
(prepC F m (2 * BB) (2 * BB - 1 + 1) gen H (tB_pos F m T) (tB_le F m T)).piv β).length
/-- The repeat-until-success cap. -/
noncomputable def Rpar (β : Fin m → F.F) : ℕ := 2 * Fintype.card F.F * (T + 10 + numJobs F m gen H T β)
/-- **The quantum program with the chosen parameters.** -/
noncomputable def progFinal {c : ℕ} (β : Fin m → F.F) (dG dz dst : Fin c) (slot : Fin (m * LL) → Fin c)
(hslot : Function.Injective slot) : Prog (NNf + (2 * BB - 1 + 1)) c (m * LL) :=
progQ F m (2 * BB) (2 * BB - 1) gen H (tB_pos F m T) (tB_le F m T) β dG dz dst slot hslot
(Rpar F m gen H T β) (T + 3) (2 * T + 6 + (2 * BB - 1))
end Lay
end OPI
end
-- ===== OPI.Bot =====
section
/-!
# The case `D = ⊥`
Then `C = ⊤`, and the word `β + 1` lies in `C ∩ A`. A classical program writes its bits and halts.
-/
namespace OPI
open QAlgorithms QAlgorithms.OPI TwoFoldOPI
variable {N c out : ℕ}
/-- Write a list of bits. -/
def writeBits (bits : List (Fin c × Bool)) (P : Prog N c out) : Prog N c out :=
bits.foldr (fun dv P => .setBit dv.1 dv.2 P) P
namespace Bot
variable (F : AvgCaseTI.FieldPres) (m : ℕ) (β : Fin m → F.F)
/-- The bits of the word `β + 1`. -/
noncomputable def bitsB : Fin (m * bitsPerSymbol F) → Bool :=
fun x => elemBits F (β (finProdFinEquiv.symm x).1 + 1) (finProdFinEquiv.symm x).2
/-- **The program for `D = ⊥`.** -/
noncomputable def progBot : Prog 0 (m * bitsPerSymbol F) (m * bitsPerSymbol F) :=
writeBits ((List.finRange _).map fun i => (i, bitsB F m β i)) (.halt (copyCirc id) (copyCirc_wf id))
end Bot
end OPI
end
-- ===== OPI.GEPI =====
section
/-!
# The elimination program in first-order form
Opcodes `(tag, c)` with a constant `c` (coordinates); their semantics on coordinate lists mirrors
the field operations of `GEP`/`RelinProg`.
-/
namespace OPI
namespace FM
open TwoFoldOPI QAlgorithms
/-- Opcodes: `0` zero, `1` S, `2` F, `3` P, `4` N1, `5` N2, `6` A1, `7` A2, `8` U, `9` O c,
`10` `-(xy)`, `11` `-((x+y)c)`, `12` constant `c`. -/
abbrev OpC := ℕ × List ℕ
/-- The field context: modulus, degree, coefficients of `f`, budget for searches. -/
structure FCtx where
p : ℕ
e : ℕ
fl : List ℕ
N : ℕ
def oneL (e : ℕ) : List ℕ := (List.range e).map (fun j => if j = 0 then 1 else 0)
def isZ (a : List ℕ) : Bool := a.all (fun x => decide (x = 0))
/-- Inverse by search. -/
def invM (C : FCtx) (a : List ℕ) : List ℕ :=
((allLB C.p C.e C.N).find? (fun c => decide (mulM C.p C.fl c a = oneL C.e))).getD (zeroL C.e)
def addM (C : FCtx) (a b : List ℕ) : List ℕ := addL C.p a b
def subM (C : FCtx) (a b : List ℕ) : List ℕ := subL C.p a b
def mM (C : FCtx) (a b : List ℕ) : List ℕ := mulM C.p C.fl a b
/-- Semantics of an opcode on decoded arguments. -/
def opSem (C : FCtx) (o : OpC) (xs : List (List ℕ)) : List ℕ :=
let z := zeroL C.e
let one := oneL C.e
let a0 := xs.getD 0 z
let a1 := xs.getD 1 z
let a2 := xs.getD 2 z
let a3 := xs.getD 3 z
if o.1 = 1 then (if xs.length = 3 then (if !isZ a0 && isZ a1 && isZ a2 then one else z) else z)
else if o.1 = 2 then (if xs.length = 3 then (if !isZ a2 || (!isZ a0 && isZ a1) then one else z) else z)
else if o.1 = 3 then (if xs.length = 3 then addM C a2 (if !isZ a0 then a1 else z) else z)
else if o.1 = 4 then (if xs.length = 1 then mM C (invM C a0) a0 else z)
else if o.1 = 5 then (if xs.length = 2 then mM C (invM C a0) a1 else z)
else if o.1 = 6 then (if xs.length = 3 then (if !isZ a0 then a2 else subM C a1 (mM C a1 a2)) else z)
else if o.1 = 7 then (if xs.length = 4 then (if !isZ a0 then a3 else subM C a1 (mM C a2 a3)) else z)
else if o.1 = 8 then (if xs.length = 2 then (if !isZ a0 || !isZ a1 then one else z) else z)
else if o.1 = 9 then (if xs.length = 2 then addM C a0 (mM C a1 o.2) else z)
else if o.1 = 10 then (if xs.length = 2 then subM C z (mM C a0 a1) else z)
else if o.1 = 11 then (if xs.length = 2 then subM C z (mM C (addM C a0 a1) o.2) else z)
else if o.1 = 12 then o.2
else z
variable (F : AvgCaseTI.FieldPres)
/-- The field context of `F` with budget `N`. -/
noncomputable def ctxOf (N : ℕ) : FCtx := ⟨F.p, F.f.natDegree, flOf F, N⟩
end FM
end OPI
namespace OPI
namespace FM
open TwoFoldOPI QAlgorithms GEP
variable (F : AvgCaseTI.FieldPres) (N : ℕ) (hN : F.p ^ F.f.natDegree ≤ N)
end FM
end OPI
end
-- ===== OPI.IRBot =====
section
/-!
# The program for `D = ⊥` as a first-order DAG
-/
namespace OPI
open QAlgorithms QAlgorithms.OPI TwoFoldOPI FM
variable {N c out : ℕ}
/-! ### DAGs rooted at a fail node -/
/-- Write bits into memory. -/
def writeBitsI : List (ℕ × Bool) → ISeg
| [] => ISeg.idI
| (d, v) :: L => (ISeg.setBitI d v).comp (writeBitsI L)
/-! ### The bits of `β + 1` -/
/-- Coordinate words of `β + 1` from the bit encodings of `β`. -/
def botBits (p e w : ℕ) (βb : List (List Bool)) : List (List Bool) :=
βb.map (fun bs => encL w (addL p (decLS p e w bs) (oneL e)))
/-- The bit-writes of the bottom program. -/
def botWrites (L : ℕ) (bb : List (List Bool)) : List (ℕ × Bool) :=
(List.range (bb.length * L)).map (fun x => (x, (bb.getD (x / L) []).getD (x % L) false))
/-- The DAG of the bottom program. -/
def botDag (L : ℕ) (bb : List (List Bool)) : List INode :=
[failI] ++ ((writeBitsI (botWrites L bb)).comp (haltS (0 :: List.range (bb.length * L)))) 0 1
def botRoot (L : ℕ) (bb : List (List Bool)) : ℕ :=
((writeBitsI (botWrites L bb)).comp (haltS (0 :: List.range (bb.length * L)))).entry 0 1
section
variable (F : AvgCaseTI.FieldPres) (m : ℕ) (β : Fin m → F.F)
end
end OPI
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI OPI.FM
variable {α : Type} [Coding α]
end OPI.W6.IsPR
end
-- ===== OPI.Grid =====
section
/-!
# Grids of two-continuation segments (majority votes)
Level `r + 1`, column `s` is a copy of the segment `T` whose continuations are the nodes of level
`r`, columns `s` and `s + 1`. Every block has the same length `S`, so positions are explicit.
-/
namespace OPI
open QAlgorithms QAlgorithms.OPI
variable {N c out : ℕ}
/-- Indices of the grid nodes. -/
def gidx (Nt S B : ℕ) (lev0 : ℕ → ℕ) : ℕ → ℕ → ℕ
| 0, s => lev0 s
| r + 1, s => B + (r * (Nt + 1) + s) * S + S - 1
/-- One level of the grid. -/
def gridLevel (T : ISeg2) (Nt S B : ℕ) (lev0 : ℕ → ℕ) (r : ℕ) : List INode :=
(List.range (Nt + 1)).flatMap (fun s => T (gidx Nt S B lev0 r s) (gidx Nt S B lev0 r (s + 1)) (B + (r * (Nt + 1) + s) * S))
/-- The grid nodes. -/
def gridNodes (T : ISeg2) (Nt S B : ℕ) (lev0 : ℕ → ℕ) (R : ℕ) : List INode :=
(List.range R).flatMap (gridLevel T Nt S B lev0)
section
variable (T : ISeg2) (Nt S B : ℕ) (lev0 : ℕ → ℕ) (hS : ∀ k0 k1 st, (T k0 k1 st).length = S)
include hS
end
end OPI
end
-- ===== OPI.CtrlGrad =====
section
/-!
# The gradient preparation as first-order segments
-/
namespace OPI
open QAlgorithms QAlgorithms.OPI
variable {N c' out b : ℕ}
local notation "vl" => List.map Fin.val
/-- Gate fields of the Hadamard test. -/
def hTestF (c : ℕ) (as wl : List ℕ) (e k : ℕ) : List (List ℕ) :=
[[0, c]] ++ (incrN [c] as (wl.take (wl.length - e))).flatMap rnGates ++ List.replicate k [1, c] ++ [[0, c]]
/-- The test as a two-continuation segment. -/
def testI (c : ℕ) (as wl : List ℕ) (e k dst : ℕ) : ISeg2 :=
ISeg2.pre (ISeg.chainI (hTestF c as wl e k))
(ISeg2.measK c dst (ISeg.setBitI dst false) ((ISeg.chainI (rnGates (0, [c]))).comp (ISeg.setBitI dst false)))
end OPI
namespace OPI
open QAlgorithms QAlgorithms.OPI
variable {N c' out b : ℕ}
local notation "vl" => List.map Fin.val
/-- One stage: the multiplication chain, the grid of tests below the top level, the top test. -/
def stageI (c : ℕ) (as wl : List ℕ) (e k dst Nt : ℕ) (mulF : List (List ℕ)) : ISeg := fun k0 st =>
if Nt = 0 then [] else
let M := ISeg.chainI mulF k0 st
let kM := (ISeg.chainI mulF).entry k0 st
let B := st + M.length
let T := testI c as wl e k dst
let S := (hTestF c as wl e k).length + (rnGates (0, [c])).length + 3
let lev0 := fun s => if Nt < 2 * s then kM else k0
let G := gridNodes T Nt S B lev0 (Nt - 1)
M ++ G ++ T (gidx Nt S B lev0 (Nt - 1) 0) (gidx Nt S B lev0 (Nt - 1) 1) (B + G.length)
end OPI
namespace OPI
open QAlgorithms QAlgorithms.OPI
variable {N c' out b : ℕ}
local notation "vl" => List.map Fin.val
/-- The chain of stages `j0, j0+1, …` (`n` of them). -/
def chainPI (c : ℕ) (as wl : List ℕ) (dst Nt b : ℕ) (ks : ℕ → ℕ) (mulFs : ℕ → List (List ℕ)) :
ℕ → ℕ → ISeg
| _, 0 => ISeg.idI
| j0, n + 1 => (stageI c as wl (b - j0 - 1) (ks j0) dst Nt (mulFs j0)).comp
(chainPI c as wl dst Nt b ks mulFs (j0 + 1) n)
/-- **The gradient preparation.** -/
def gradI (c w0 : ℕ) (as wl : List ℕ) (dst Nt b : ℕ) (ks : ℕ → ℕ) (mulFs : ℕ → List (List ℕ)) : ISeg :=
(ISeg.chainI ((rnGates (0, [w0])) ++ [[0, w0]])).comp (chainPI c as wl dst Nt b ks mulFs 1 (b - 1))
end OPI
end
-- ===== OPI.IRQuant =====
section
/-!
# The full quantum program as one segment
`quantSeg = gradI ∘ retryI (trialI …)`; since `retry` starts from `fail`, the segment computes a
constant program, represented in `[failI] ++ quantSeg 0 1` (`progQ_rep`).
-/
namespace OPI
namespace Lay
open QAlgorithms QAlgorithms.OPI TwoFoldOPI SymEnc
local notation "vl" => List.map Fin.val
variable (F : AvgCaseTI.FieldPres) (m t b' : ℕ) {r : ℕ} (gen : Bool) (H : Matrix (Fin r) (Fin m) F.F)
local notation "KD" => kdOf F m gen H
local notation "NN" => total (parOf F m t (b' + 1) (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)))
variable (ht : 1 ≤ t) (htb : t ≤ b' + 1)
/-- The trial circuit. -/
noncomputable def trialCirc (β : Fin m → F.F) : Circuit htcxGateSet (NN + (b' + 1)) :=
(decC F m t (b' + 1) gen H ht htb).circ β (basisOf gen H).G (bWof gen H) ++
relocCirc sysEmb (CsC F m t (b' + 1) gen H ht htb) ++
invCirc ((decC F m t (b' + 1) gen H ht htb).circ β (basisOf gen H).G (bWof gen H))
/-- The readout list. -/
noncomputable def readL {c : ℕ} (slot : Fin (m * bitsPerSymbol F) → Fin c) : List (Fin (NN + (b' + 1)) × Fin c) :=
readList (fun j => Fin.castAdd (b' + 1) (qS F m t (b' + 1) KD (KD * KD) j)) slot
/-- The accepting segment. -/
noncomputable def accSeg {c : ℕ} (slot : Fin (m * bitsPerSymbol F) → Fin c) : ISeg :=
(measAllI ((readL F m t b' gen H slot).map fun x => (x.1.val, x.2.val))).comp
(haltS (haltF (copyCirc slot)))
/-- **The segment of the quantum program.** -/
noncomputable def quantSeg {c : ℕ} (β : Fin m → F.F) (dG dz dst : Fin c) (slot : Fin (m * bitsPerSymbol F) → Fin c)
(R K Nt : ℕ) : ISeg :=
(gradI (gCtl F m t b' gen H).val (gradEmb (n := NN) (b := b' + 1) ⟨0, Nat.succ_pos b'⟩).val
(vl (gAs F m t b' gen H)) (vl (List.ofFn (gradEmb (n := NN) (b := b' + 1)))) dG.val Nt (b' + 1) ksT
(fun j => (revCirc (mulGates (gAs F m t b' gen H) (List.ofFn (gradEmb (n := NN) (b := b' + 1))) j
(b' + 1 - j))).map gfields)).comp
(retryI (trialI
(prepI (prepC F m t (b' + 1) gen H ht htb).fl.val dst.val R
((allJobs (decC F m t (b' + 1) gen H ht htb).D (prepC F m t (b' + 1) gen H ht htb).Rr
(prepC F m t (b' + 1) gen H ht htb).piv β).map
(rjData (b := b' + 1) (prepC F m t (b' + 1) gen H ht htb).fl (prepC F m t (b' + 1) gen H ht htb).f0
(prepC F m t (b' + 1) gen H ht htb).asR))
((relocCirc (sysEmb (n := NN) (b := b' + 1)) (revCirc (linCirc (prepC F m t (b' + 1) gen H ht htb).Rr
(prepC F m t (b' + 1) gen H ht htb).piv (prepC F m t (b' + 1) gen H ht htb).G
(prepC F m t (b' + 1) gen H ht htb).Z (prepC F m t (b' + 1) gen H ht htb).asL
(prepC F m t (b' + 1) gen H ht htb).fL))).map gfields)
((phCirc (regE F m t (b' + 1) (SymEnc.nIds m KD (KD * KD))) (prepC F m t (b' + 1) gen H ht htb).Rr
(b := b' + 1) (prepC F m t (b' + 1) gen H ht htb).scr (prepC F m t (b' + 1) gen H ht htb).asP
(prepC F m t (b' + 1) gen H ht htb).fP (List.finRange m)).map gfields))
((trialCirc F m t b' gen H ht htb β).map gfields) dz.val
(vl ((List.ofFn (decC F m t (b' + 1) gen H ht htb).wR).map (Fin.castAdd (b' + 1))))
(accSeg F m t b' gen H slot) (vl (sysWires NN (b' + 1)))) K)
end Lay
end OPI
end
-- ===== OPI.IRLay =====
section
/-!
# Block allocation on natural numbers
`ParN = (m, L, d, w, t, b, nI)`; block sizes as a list, offsets as prefix sums.
-/
namespace OPI
namespace Lay
/-- The layout parameters as a tuple. -/
abbrev ParN := ℕ × ℕ × ℕ × ℕ × ℕ × ℕ × ℕ
def toN (P : Par) : ParN := (P.m, P.L, P.d, P.w, P.t, P.b, P.nI)
/-- The block sizes. -/
def szL (x : ParN) : List ℕ :=
let m := x.1; let L := x.2.1; let d := x.2.2.1; let w := x.2.2.2.1; let t := x.2.2.2.2.1
let b := x.2.2.2.2.2.1; let nI := x.2.2.2.2.2.2
[m * (2 * L), m * L, (m * 2 * d) * w, t, w + 1, 1, t - 1, w, t + 2 * w + 2, L, L, 1, L, 2 * L, 1, 1,
b, b + 2 * w, 1, 2 * L, 2 * L, 1, 1, L, L, 1, nI * L, 4 * L, 1, 1, 1, L + w, L, 2 * L, 1, b, b + 2 * L, 1,
1, b]
/-- Block offsets. -/
def offN (x : ParN) (k : ℕ) : ℕ := ((szL x).take k).sum
/-- The wires of block `k`. -/
def blkN (x : ParN) (k : ℕ) : List ℕ := (List.range ((szL x).getD k 0)).map (offN x k + ·)
/-- Total number of wires. -/
def totalN (x : ParN) : ℕ := (szL x).sum
end Lay
end OPI
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI OPI.Lay
variable {α : Type} [Coding α]
end OPI.W6.IsPR
end
-- ===== OPI.IRLay2 =====
section
/-!
# The concrete wire families on natural numbers
-/
namespace OPI
namespace Lay
open TwoFoldOPI RelinProg
local notation "vl" => List.map Fin.val
/-- Field accessors of a parameter tuple. -/
def pL (x : ParN) : ℕ := x.2.1
def pd (x : ParN) : ℕ := x.2.2.1
def pw (x : ParN) : ℕ := x.2.2.2.1
/-- Symbol register wire `(i, c, j)`. -/
def regEN (x : ParN) (i c j : ℕ) : ℕ := offN x 0 + (j + pL x * c + 2 * pL x * i)
/-- The register `(i, c)`. -/
def bRegN (x : ParN) (i c : ℕ) : List ℕ := (List.range (pL x)).map (regEN x i c)
/-- The register `R_i`. -/
def RrN (x : ParN) (i : ℕ) : List ℕ := (List.range (pL x)).map (fun j => offN x 1 + (j + pL x * i))
/-- The resource of gadget `(i, c, g)`. -/
def resN (x : ParN) (i c g : ℕ) : List ℕ :=
(List.range (pw x)).map (fun j => offN x 2 + (j + pw x * (g + pd x * (c + 2 * i))))
/-- The `a` register of gadget `(i, c, g)`: block `g` of the register `(i, c)`. -/
def aEN (x : ParN) (i c g : ℕ) : List ℕ := (List.range (pw x)).map (fun j => regEN x i c (j + pw x * g))
/-- The decoder register of id `y`. -/
def clsRegN (x : ParN) (y : ℕ) : List ℕ := (List.range (pL x)).map (fun j => offN x 26 + (j + pL x * y))
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)
local notation "X" => toN (parOf F m t b nI)
/-! ### Shared scratch lists -/
/-- The shared lookup ancillas. -/
def asQN (x : ParN) : List ℕ :=
blkN x 8 ++ blkN x 9 ++ blkN x 10 ++ [offN x 11] ++ blkN x 12 ++ blkN x 13 ++ [offN x 14]
/-! ### Readout and `R` words -/
/-! ### The registers of the classical decoder -/
/-- The registers of the straight-line ids. -/
def rsOfN (x : ParN) (m B nI y : ℕ) : List ℕ :=
if y % B = 0 ∧ y / B < m then bRegN x (y / B) 0
else if B * B ≤ y ∧ (y - B * B) % B = 0 ∧ (y - B * B) / B < m then bRegN x ((y - B * B) / B) 1
else if y < nI then clsRegN x y else []
section Cls
variable (k k2 : ℕ)
local notation "nJ" => SymEnc.nIds m k k2
local notation "PQ" => parOf F m t b (SymEnc.nIds m k k2)
local notation "XQ" => toN (parOf F m t b (SymEnc.nIds m k k2))
local notation "BB" => GEP.Bd m (k + k2)
end Cls
end Lay
end OPI
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI OPI.Lay
variable {α : Type} [Coding α]
end OPI.W6.IsPR
end
-- ===== OPI.IRQuantN =====
section
/-!
# The quantum segment on natural-number data (layout substituted)
-/
namespace OPI
namespace Lay
open QAlgorithms QAlgorithms.OPI TwoFoldOPI SymEnc
local notation "vl" => List.map Fin.val
/-- **The quantum segment from natural-number data.** `X` is the layout, `bg` the gradient width. -/
def qSegN (X : ParN) (bg dG dz dst K R Nt kd : ℕ) (jobs : List (List ℕ × PTab)) (pivN : List ℕ)
(TG : List (List (PTab × PTab))) (zT : PTab) (Cf : List (List ℕ)) (slotN : List ℕ) : ISeg :=
let m := X.1; let L := pL X; let NN := totalN X
(gradI (offN X 38) NN (blkN X 39) ((List.range bg).map (NN + ·)) dG Nt bg ksT
(fun j => (mulGatesN (blkN X 39) ((List.range bg).map (NN + ·)) j (bg - j)).flatMap rnGates)).comp
(retryI (trialI
(prepIN (offN X 29) (offN X 30) dst R (blkN X 31) jobs NN bg kd m ((List.range m).map (RrN X)) pivN TG
(blkN X 32) (blkN X 33) (offN X 34) ((List.range m).map (fun i => bRegN X i 0)) (blkN X 35) (blkN X 36)
(offN X 37) zT)
Cf dz ((List.range (m * L)).map (offN X 1 + ·))
((measAllI ((List.range (m * L)).map (fun j => (regEN X (j / L) 0 (j % L), slotN.getD j 0)))).comp
(haltS (0 :: slotN)))
(List.range NN)) K)
/-- The resource wires of all gadgets. -/
def resAllX (X : ParN) : List (List ℕ) :=
(List.range X.1).flatMap (fun i => (List.range (pd X)).map (resN X i 0) ++ (List.range (pd X)).map (resN X i 1))
variable (F : AvgCaseTI.FieldPres) (m t b' : ℕ) {r : ℕ} (gen : Bool) (H : Matrix (Fin r) (Fin m) F.F)
local notation "KD" => kdOf F m gen H
local notation "nJ" => SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)
local notation "PQ" => parOf F m t (b' + 1) (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H))
local notation "XQ" => toN (parOf F m t (b' + 1) (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)))
local notation "NN" => total (parOf F m t (b' + 1) (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)))
variable (ht : 1 ≤ t) (htb : t ≤ b' + 1)
/-! ### Values of the remaining wires -/
/-! ### The preparation layout -/
end Lay
end OPI
end
-- ===== OPI.IRDecE =====
section
/-!
# First-order twins of the decoder gadgets `E` and `P`
* `eCircN`: gate fields of `eCirc` (EGad), tables `pgTab … (cswF …)` as parameters.
* `eGad_N`: the `E` gadget of coordinate `i` (DecJ).
* `pGad_N`, `pGadC_N`: the symbol-permutation gadget (DecJ), tables `pgTab … (pFun enc τ)`.
* Table data: `cswF` and `pFun (elemBits F) (β - ·)` tables from budgeted pattern lists.
-/
namespace OPI
open QAlgorithms OPI.W6
local notation "vl" => List.map Fin.val
/-! ### The `E` gadget -/
section E
variable {N : ℕ}
/-- **Twin of `eCirc`.** -/
def eCircN (S T Z as : List ℕ) (a f : ℕ) (T1 T2 : List (List Bool × List Bool)) : List (List ℕ) :=
rnGates (0, [a]) ++ [[0, a]] ++ (permGadN [a] (S ++ T) Z as f T1 T2).flatMap rnGates ++
(eqFlipN S (List.replicate S.length false) as a).flatMap rnGates
end E
namespace SymEnc
variable {n m L : ℕ} {K : Type} [Fintype K] [DecidableEq K] [Zero K]
{reg : Fin m × Bool × Fin L ↪ Fin n} {enc : K → Qubits L}
/-- **Twin of the circuit `revCirc (pGad …)`.** -/
def pGadCN (B Z as : List ℕ) (f : ℕ) (T1 T2 : List (List Bool × List Bool)) : List (List ℕ) :=
(permGadN [] B Z as f T1 T2).flatMap rnGates
end SymEnc
/-! ### Table data -/
end OPI
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI
variable {α : Type} [Coding α]
end OPI.W6.IsPR
end
-- ===== OPI.GEPI2 =====
section
/-!
# The decoder program as first-order instructions
-/
namespace OPI
namespace FM
open TwoFoldOPI QAlgorithms GEP
/-- A first-order instruction: destination, sources, opcode. -/
abbrev KI := ℕ × List ℕ × OpC
section Stage
variable (R C Kd : ℕ) (coefI : ℕ → ℕ → List ℕ) (a0srcI : ℕ → ℕ → List ℕ) (a0opI : ℕ → ℕ → OpC)
def stageI (t : ℕ) : List KI :=
if t = 1 then
(List.range R).flatMap (fun i => (List.range (C + 1)).map (fun l => (idA R C 0 i l, a0srcI i l, a0opI i l))) ++
(List.range R).map (fun i => (idU R C 0 i, [], (0, [])))
else if t < 2 then []
else if t < Tj R C then
if (t - 2) % (2 * R + 3) = 0 then
(List.range (C + 1)).map (fun l => (idP R C ((t - 2) / (2 * R + 3)) 0 l, [], (0, []))) ++
[(idF R C ((t - 2) / (2 * R + 3)) 0, [], (0, []))]
else if (t - 2) % (2 * R + 3) ≤ R then
let j := (t - 2) / (2 * R + 3)
let i := (t - 2) % (2 * R + 3) - 1
[(idS R C j i, [idA R C j i j, idU R C j i, idF R C j i], (1, [])),
(idF R C j (i + 1), [idA R C j i j, idU R C j i, idF R C j i], (2, []))]
else if (t - 2) % (2 * R + 3) ≤ 2 * R then
let j := (t - 2) / (2 * R + 3)
let i := (t - 2) % (2 * R + 3) - R - 1
(List.range (C + 1)).map (fun l => (idP R C j (i + 1) l, [idS R C j i, idA R C j i l, idP R C j i l], (3, [])))
else if (t - 2) % (2 * R + 3) = 2 * R + 1 then
let j := (t - 2) / (2 * R + 3)
(List.range (C + 1)).map (fun l => if l = j then (idN R C j l, [idP R C j R j], (4, []))
else (idN R C j l, [idP R C j R j, idP R C j R l], (5, [])))
else
let j := (t - 2) / (2 * R + 3)
(List.range R).flatMap (fun i => (List.range (C + 1)).map (fun l =>
if l = j then (idA R C (j + 1) i l, [idS R C j i, idA R C j i j, idN R C j l], (6, []))
else (idA R C (j + 1) i l, [idS R C j i, idA R C j i l, idA R C j i j, idN R C j l], (7, [])))) ++
(List.range R).map (fun i => (idU R C (j + 1) i, [idU R C j i, idS R C j i], (8, [])))
else if t ≤ Tj R C + R then
if t = Tj R C then (List.range C).map (fun j => (idX R C j 0, [], (0, [])))
else (List.range C).map (fun j => (idX R C j (t - Tj R C - 1 + 1),
[idS R C j (t - Tj R C - 1), idA R C C (t - Tj R C - 1) C, idX R C j (t - Tj R C - 1)], (3, [])))
else if t ≤ Tj R C + R + 1 + Kd then
if t = Tj R C + R + 1 then (List.range R).map (fun o => (idO R C o 0, [], (0, [])))
else (List.range R).map (fun o => (idO R C o (t - (Tj R C + R + 1) - 1 + 1),
[idO R C o (t - (Tj R C + R + 1) - 1), idX R C (t - (Tj R C + R + 1) - 1) R],
(9, coefI (t - (Tj R C + R + 1) - 1) o)))
else []
def progI : List KI := (List.range (Tmax R C Kd)).flatMap (stageI R C Kd coefI a0srcI a0opI)
end Stage
variable (F : AvgCaseTI.FieldPres) (N : ℕ)
/-- An instruction and its first-order form. -/
def KRel (I : KIns F.F) (x : KI) : Prop :=
I.dst = x.1 ∧ I.src = x.2.1 ∧ ∀ xs, E F (I.op xs) = opSem (ctxOf F N) x.2.2 (xs.map (E F))
end FM
end OPI
namespace OPI
namespace FM
open TwoFoldOPI QAlgorithms GEP
variable (F : AvgCaseTI.FieldPres) (N : ℕ) (hN : F.p ^ F.f.natDegree ≤ N)
(R C Kd : ℕ) (coef : ℕ → ℕ → F.F) (a0src : ℕ → ℕ → List ℕ) (a0op : ℕ → ℕ → List F.F → F.F)
(coefI : ℕ → ℕ → List ℕ) (a0opI : ℕ → ℕ → OpC)
(hcoef : ∀ j o, coefI j o = E F (coef j o))
(ha0 : ∀ i l xs, E F (a0op i l xs) = opSem (ctxOf F N) (a0opI i l) (xs.map (E F)))
end FM
end OPI
end
-- ===== OPI.GEPI3 =====
section
/-!
# Relinearization inputs and the tables of the compiled decoder program
-/
namespace OPI
namespace FM
open TwoFoldOPI QAlgorithms GEP RelinProg
variable (F : AvgCaseTI.FieldPres) (N : ℕ) (hN : F.p ^ F.f.natDegree ≤ N)
/-- Coefficients of a matrix of field elements on natural indices. -/
def matI (e r c : ℕ) (Mc : List (List (List ℕ))) (j o : ℕ) : List ℕ :=
if j < r ∧ o < c then (Mc.getD j []).getD o (zeroL e) else zeroL e
noncomputable def matE {r c : ℕ} (M : Fin r → Fin c → F.F) : List (List (List ℕ)) :=
List.ofFn (fun j => List.ofFn (fun o => E F (M j o)))
/-- The opcodes of the relinearization inputs. -/
def a0opI (e k k2 m : ℕ) (bDc bWc : List (List (List ℕ))) (i l : ℕ) : OpC :=
if l = k + k2 then (10, []) else if l < k then (11, matI e k m bDc l i) else (12, matI e k2 m bWc (l - k) i)
end FM
end OPI
namespace OPI
namespace FM
open TwoFoldOPI QAlgorithms GEP RelinProg SymEnc
variable (F : AvgCaseTI.FieldPres) (N : ℕ)
/-- Decoded blocks of a pattern. -/
def decBlocksL (p e w L k : ℕ) (bs : List Bool) : List (List ℕ) :=
(List.range k).map (fun j => decLS p e w ((bs.drop (j * L)).take L))
/-- The table entry of a first-order instruction. -/
def tabI (C : FCtx) (w L : ℕ) (x : KI) (bs : List Bool) : List Bool :=
encL w (opSem C x.2.2 (decBlocksL C.p C.e w L x.2.1.length bs))
end FM
end OPI
end
-- ===== OPI.IRDecCls =====
section
/-!
# First-order twin of the classical decoder `clsGates`
The register map `reg : ℕ → List (Fin n)` enters as a list `RS : List (List ℕ)` indexed by id
(`RS.getD x []`); instructions enter as `(dst, src, table)`.
* `compileN`, `compile_NL`: compiled straight-line programs (any encoding).
* `clsGates_N`: the classical decoder; tables `funTable (I.src.flatMap C.rs).length (tabFn (symEnc …) I)`.
* `clsTabs_eq`: for the field encoding, the instruction list in terms of the first-order program
(`KI`, `tabI`) related to it by `List.Forall₂ (KRel F N)` (e.g. `FM.decProg_rel`).
-/
namespace OPI
open QAlgorithms OPI.W6
local notation "vl" => List.map Fin.val
/-- **Twin of `compile`**: registers `RS` by id, instructions `(dst, src, table)`. -/
def compileN (RS : List (List ℕ)) (as : List ℕ) (f : ℕ) (Is : List (ℕ × List ℕ × List (List Bool × List Bool))) :
List RN :=
Is.flatMap (fun I => lookupN (I.2.1.flatMap (fun x => RS.getD x [])) (RS.getD I.1 []) as f I.2.2)
/-- The `(dst, src, table)` form of a program compiled with encoding `E` and registers `reg`. -/
def insTabs {V : Type} {n : ℕ} (E : Enc V) (reg : ℕ → List (Fin n)) (Is : List (KIns V)) :
List (ℕ × List ℕ × List (List Bool × List Bool)) :=
Is.map (fun I => (I.dst, I.src, funTable (I.src.flatMap reg).length (tabFn E I)))
namespace SymEnc
open GEP RelinProg
variable {n m L k k2 : ℕ} {K : Type} [Field K] [Fintype K] [DecidableEq K]
{reg : Fin m × Bool × Fin L ↪ Fin n} {enc : K → Qubits L} {dec : Qubits L → K}
{hdec : ∀ x, dec (enc x) = x}
/-- **Twin of the circuit `revCirc (clsGates …)`.** -/
def clsCN (RS : List (List ℕ)) (as : List ℕ) (f : ℕ) (Is : List (ℕ × List ℕ × List (List Bool × List Bool))) :
List (List ℕ) :=
(compileN RS as f Is).flatMap rnGates
end SymEnc
/-! ### The tables in first-order form (field encoding) -/
namespace FM
open TwoFoldOPI SymEnc GEP RelinProg
variable (F : AvgCaseTI.FieldPres) (N : ℕ)
/-- The `(dst, src, table)` form of a first-order program. -/
def clsTabs (C : FCtx) (w L : ℕ) (xs : List KI) : List (ℕ × List ℕ × List (List Bool × List Bool)) :=
xs.map (fun x => (x.1, x.2.1, funTable (x.2.1.length * L) (tabI C w L x)))
end FM
end OPI
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI
variable {α : Type} [Coding α]
end OPI.W6.IsPR
end
-- ===== OPI.IRQft =====
section
/-!
# First-order twins of the QFT gadgets over `2^t` (`QFT2`)
Gate fields of `hadGad`, `crGad`, `swGad` and of the gadget lists `phaseGL`, `swapsGL`, `qftGL` as
functions of natural-number wires; the tables of the controlled rotations (`crTab b s`) stay
parameters. Realizers at the bottom.
-/
namespace OPI
open QAlgorithms
variable {n b : ℕ}
local notation "vl" => List.map Fin.val
/-! ### Single gadgets -/
/-- Gate fields of a Hadamard gadget. -/
def hadGadN (q : ℕ) : List (List ℕ) := [[0, q]]
/-- The table of a controlled `R_s`. -/
def crTab (b s : ℕ) : List (List Bool × List Bool) := [([true, true], natBits b (2 ^ (b - s)))]
/-- Gate fields of a controlled rotation gadget (table `T`). -/
def crGadN (n b c t : ℕ) (scr as : List ℕ) (f : ℕ) (T : List (List Bool × List Bool)) : List (List ℕ) :=
(tablePhaseGatesN n b [c, t] scr as f T).flatMap rnGates
/-- Gate fields of a swap gadget. -/
def swGadN (c t : ℕ) : List (List ℕ) :=
([(1, [c, t]), (1, [t, c]), (1, [c, t])] : List RN).flatMap rnGates
/-! ### Gadget lists
A register is a list `V` of natural wires; level `j` of the QFT acts on `V[0..j]`. -/
/-- Phase gadgets of level `j` (controls `V[m]`, `m < j`, target `V[j]`, tables `Ts[m]`). -/
def phaseGLN (n b : ℕ) (scr as : List ℕ) (f : ℕ) (V : List ℕ) (Ts : List (List (List Bool × List Bool)))
(j : ℕ) : List (List (List ℕ)) :=
(List.range j).map (fun m => crGadN n b (V.getD m 0) (V.getD j 0) scr as f (Ts.getD m []))
/-- Swap gadgets of level `j`. -/
def swapsGLN (V : List ℕ) (j : ℕ) : List (List (List ℕ)) :=
(List.range j).reverse.map (fun i => swGadN (V.getD i 0) (V.getD (i + 1) 0))
/-- Level `j` of the QFT gadget list. -/
def qftLevelN (n b : ℕ) (scr as : List ℕ) (f : ℕ) (V : List ℕ) (Ts : List (List (List Bool × List Bool)))
(j : ℕ) : List (List (List ℕ)) :=
phaseGLN n b scr as f V Ts j ++ [hadGadN (V.getD j 0)] ++ swapsGLN V j
/-- The first `k` levels. -/
def qftGLNk (n b : ℕ) (scr as : List ℕ) (f : ℕ) (V : List ℕ) (Ts : List (List (List Bool × List Bool)))
(k : ℕ) : List (List (List ℕ)) :=
(List.range k).flatMap (qftLevelN n b scr as f V Ts)
/-- **Gadget list of the QFT on the register `V`** (gate fields per gadget). -/
def qftGLN (n b : ℕ) (scr as : List ℕ) (f : ℕ) (V : List ℕ) (Ts : List (List (List Bool × List Bool))) :
List (List (List ℕ)) :=
qftGLNk n b scr as f V Ts V.length
/-- The rotation tables of a QFT on `t` wires (`Ts[m]` for the rotation `R_{m+2}`). -/
def qftTabs (b t : ℕ) : List (List (List Bool × List Bool)) := (List.range t).map (fun m => crTab b (m + 2))
/-! ### The rotation tables without exponentials -/
/-- `natBits b (2^j)` without computing `2^j`. -/
def pow2Bits (b j : ℕ) : List Bool :=
if j < b then List.replicate (b - 1 - j) false ++ true :: List.replicate j false else List.replicate b false
/-- The table of a controlled `R_s`, computed without `2^(b-s)`. -/
def crTabN (b s : ℕ) : List (List Bool × List Bool) := [([true, true], pow2Bits b (b - s))]
/-- `qftTabs` computed without exponentials. -/
def qftTabsN (b t : ℕ) : List (List (List Bool × List Bool)) := (List.range t).map (fun m => crTabN b (m + 2))
end OPI
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI
variable {α : Type} [Coding α]
end OPI.W6.IsPR
end
-- ===== OPI.IRQftG =====
section
/-!
# First-order twins of the `QFT_p` and `QFT_q` gadget circuits
* `QLay.swL`, `QLay.tauL` (reversible gate lists, `RGate.toN`),
* `QG.csL`, `QG.phaseC`, `QG.qpeC`, `QG.circ`, `QG.circAll`, `QQ.RLL`, `QQ.circ` (gate fields).
The natural-number data of a `QFT_p` gadget is bundled into a tuple `QGD` (`QG.data`); the tables
(`phaseTab p w b`, `qftTabs b t`, `csTabs p w t`, the readout tables `pgTab … (subF p w)`,
`pgTab … (addF p w)`, the re-encoding tables `pgTab … (Fq.RL F)`, `pgTab … (Fq.RLinv F)`) are
parameters of the twins. The control shifts `2^(t-1-i)` only enter through `csTab`, which depends on
the shift modulo `p` only (`csTab_mod`).
-/
namespace OPI
open QAlgorithms TwoFoldOPI
variable {n b : ℕ}
local notation "vl" => List.map Fin.val
/-! ### Layout gate lists -/
namespace QLay
variable {p w t : ℕ} (L : QLay n p w t)
end QLay
/-! ### Controlled shifts -/
/-- The controlled-shift tables of a control register of `t` wires (most significant first). -/
def csTabs (p w t : ℕ) : List (List (List Bool × List Bool) × List (List Bool × List Bool)) :=
(List.range t).map (fun i => csTab p w (2 ^ (t - 1 - i)))
/-! ### The `QFT_p` gadget -/
/-- Gate fields of the phase-table circuit. -/
def qgPhaseN (n b : ℕ) (A B scr was : List ℕ) (wf : ℕ) (PT : List (List Bool × List Bool)) : List (List ℕ) :=
(tablePhaseGatesN n b (A ++ B) scr was wf PT).flatMap rnGates
/-- Gate fields of the phase estimation. -/
def qgQpeN (n b : ℕ) (B C Z as : List ℕ) (f : ℕ) (scr was : List ℕ) (wf : ℕ)
(QT : List (List (List Bool × List Bool)))
(CT : List (List (List Bool × List Bool) × List (List Bool × List Bool))) : List (List ℕ) :=
(qftGLN n b scr was wf C QT).flatten ++ (csListN B Z as f (C.zip CT)).flatMap rnGates ++
(qftGLN n b scr was wf C QT).flatten
/-- **Gate fields of the `QFT_p` gadget.** -/
def qgCircN (n b p : ℕ) (A B C top : List ℕ) (lh : ℕ) (lrest Z as : List ℕ) (f : ℕ) (scr was : List ℕ)
(wf : ℕ) (PT : List (List Bool × List Bool)) (QT : List (List (List Bool × List Bool)))
(CT : List (List (List Bool × List Bool) × List (List Bool × List Bool)))
(T1 T2 : List (List Bool × List Bool)) : List (List ℕ) :=
qgPhaseN n b A B scr was wf PT ++ qgQpeN n b B C Z as f scr was wf QT CT ++
(tauListN p C top lh lrest A Z as f T1 T2).flatMap rnGates ++
(qgQpeN n b B C Z as f scr was wf QT CT).reverse.flatMap invF ++ (swapRegsN A B).flatMap rnGates
/-- Natural-number data of a `QFT_p` gadget:
`(A, B, C, top, lh, lrest, Z, as, f, scr, was, wf)`. -/
abbrev QGD := List ℕ × List ℕ × List ℕ × List ℕ × ℕ × List ℕ × List ℕ × List ℕ × ℕ × List ℕ × List ℕ × ℕ
/-- `qgCircN` on a data tuple. -/
def qgCircD (n b p : ℕ) (PT : List (List Bool × List Bool)) (QT : List (List (List Bool × List Bool)))
(CT : List (List (List Bool × List Bool) × List (List Bool × List Bool)))
(T1 T2 : List (List Bool × List Bool)) (d : QGD) : List (List ℕ) :=
qgCircN n b p d.1 d.2.1 d.2.2.1 d.2.2.2.1 d.2.2.2.2.1 d.2.2.2.2.2.1 d.2.2.2.2.2.2.1 d.2.2.2.2.2.2.2.1
d.2.2.2.2.2.2.2.2.1 d.2.2.2.2.2.2.2.2.2.1 d.2.2.2.2.2.2.2.2.2.2.1 d.2.2.2.2.2.2.2.2.2.2.2 PT QT CT T1 T2
/-- **Gate fields of a list of `QFT_p` gadgets.** -/
def circAllN (n b p : ℕ) (PT : List (List Bool × List Bool)) (QT : List (List (List Bool × List Bool)))
(CT : List (List (List Bool × List Bool) × List (List Bool × List Bool)))
(T1 T2 : List (List Bool × List Bool)) (Ds : List QGD) : List (List ℕ) :=
Ds.flatMap (qgCircD n b p PT QT CT T1 T2)
namespace QG
variable {p w t : ℕ} (G : QG n b p w t)
/-- The natural-number data of a gadget. -/
def data : QGD :=
(vl (List.ofFn G.aE), vl (List.ofFn G.bE), vl (List.ofFn G.cE), vl G.top, G.lh.val, vl G.lrest, vl G.Z,
vl G.as, G.f.val, vl G.W.scr, vl G.W.as, G.W.f.val)
end QG
/-! ### The `QFT_q` gadget -/
/-- **Gate fields of the `QFT_q` gadget.** -/
def qqCircN (n b p : ℕ) (X ZR asR : List ℕ) (fR : ℕ) (R1 R2 PT : List (List Bool × List Bool))
(QT : List (List (List Bool × List Bool)))
(CT : List (List (List Bool × List Bool) × List (List Bool × List Bool)))
(T1 T2 : List (List Bool × List Bool)) (Ds : List QGD) : List (List ℕ) :=
(permGadN [] X ZR asR fR R1 R2).flatMap rnGates ++ circAllN n b p PT QT CT T1 T2 Ds
namespace QQ
variable {F : AvgCaseTI.FieldPres} {t : ℕ} (Q : QQ n b F t)
end QQ
end OPI
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI
variable {α : Type} [Coding α]
end OPI.W6.IsPR
end
-- ===== OPI.IRDecFull =====
section
/-!
# Gate fields of the full decoder circuit
-/
namespace OPI
open QAlgorithms TwoFoldOPI
local notation "vl" => List.map Fin.val
abbrev Tab := List (List Bool × List Bool)
/-- Data of a `QFT_q` gadget: `(X, ZR, asR, fR, gadgets)`. -/
abbrev QQD := List ℕ × List ℕ × List ℕ × ℕ × List QGD
/-- Shared data of all `QFT_q` gadgets: `(n, b, p, R1, R2, PT, QT, CT, T1, T2)`. -/
abbrev QSh := ℕ × ℕ × ℕ × Tab × Tab × Tab × List Tab × List (Tab × Tab) × Tab × Tab
def qqD (s : QSh) (d : QQD) : List (List ℕ) :=
qqCircN s.1 s.2.1 s.2.2.1 d.1 d.2.1 d.2.2.1 d.2.2.2.1 s.2.2.2.1 s.2.2.2.2.1 s.2.2.2.2.2.1 s.2.2.2.2.2.2.1
s.2.2.2.2.2.2.2.1 s.2.2.2.2.2.2.2.2.1 s.2.2.2.2.2.2.2.2.2 d.2.2.2.2
/-- Data of one coordinate: `(B0, B1, ZP, asP, fP, pT1, pT2, ZE, asE, aE, fE, Q0, Q1)`. -/
abbrev CoordD := List ℕ × List ℕ × List ℕ × List ℕ × ℕ × Tab × Tab × List ℕ × List ℕ × ℕ × ℕ × QQD × QQD
/-- Gate fields of one coordinate (`eT1, eT2` are the shared tables of the `E` gadget). -/
def cCircN (s : QSh) (eT1 eT2 : Tab) (d : CoordD) : List (List ℕ) :=
let B0 := d.1; let B1 := d.2.1; let ZP := d.2.2.1; let asP := d.2.2.2.1; let fP := d.2.2.2.2.1
let pT1 := d.2.2.2.2.2.1; let pT2 := d.2.2.2.2.2.2.1; let ZE := d.2.2.2.2.2.2.2.1
let asE := d.2.2.2.2.2.2.2.2.1; let aE := d.2.2.2.2.2.2.2.2.2.1; let fE := d.2.2.2.2.2.2.2.2.2.2.1
let Q0 := d.2.2.2.2.2.2.2.2.2.2.2.1; let Q1 := d.2.2.2.2.2.2.2.2.2.2.2.2
SymEnc.pGadCN B0 ZP asP fP pT1 pT2 ++ eCircN B0 B1 ZE asE aE fE eT1 eT2 ++ qqD s Q0 ++ qqD s Q1
/-- Gate fields of the full decoder: coordinates (head last), then the classical decoder. -/
def decCircN (s : QSh) (eT1 eT2 : Tab) (ds : List CoordD) (cls : List (List ℕ)) : List (List ℕ) :=
ds.reverse.flatMap (cCircN s eT1 eT2) ++ cls
namespace SymEnc
variable {F : AvgCaseTI.FieldPres} {m n b t : ℕ} {reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n}
{k k2 kR : ℕ} (X : DecFull F reg b t k k2 kR)
/-- The data of a `QFT_q` gadget. -/
def QQ.dataQ (Q : QQ n b F t) : QQD := (vl (List.ofFn Q.X), vl Q.ZR, vl Q.asR, Q.fR.val, Q.Gs.map QG.data)
/-- The shared data. -/
noncomputable def shOf (F : AvgCaseTI.FieldPres) (n b t : ℕ) : QSh :=
(n, b, F.p, pgTab (bitsPerSymbol F) 0 (Fq.RL F), pgTab (bitsPerSymbol F) 0 (Fq.RLinv F),
phaseTab F.p (Fq.w F) b, qftTabs b t, csTabs F.p (Fq.w F) t,
pgTab (Fq.w F + 1 + Fq.w F) (Fq.w F + 1) (subF F.p (Fq.w F)),
pgTab (Fq.w F + 1 + Fq.w F) (Fq.w F + 1) (addF F.p (Fq.w F)))
/-- The data of coordinate `i`. -/
noncomputable def DecFull.cData (i : Fin m) (β : F.F) : CoordD :=
(vl (List.ofFn (bReg reg i false)), vl (List.ofFn (bReg reg i true)), vl (X.D.W i).ZP, vl (X.D.W i).asP,
(X.D.W i).fP.val, pgTab (bitsPerSymbol F) 0 (pFun (elemBits F) (fun x => β - x)),
pgTab (X.D.W i).ZP.length 0 (pFun (elemBits F) (fun x => β - x)),
vl (X.D.W i).ZE, vl (X.D.W i).asE, (X.D.W i).aE.val, (X.D.W i).fE.val,
QQ.dataQ (X.D.Q i false), QQ.dataQ (X.D.Q i true))
end SymEnc
end OPI
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI
variable {α : Type} [Coding α]
end OPI.W6.IsPR
end
-- ===== OPI.IRDecConc =====
section
/-!
# The data of the concrete decoder on natural numbers
-/
namespace OPI
namespace Lay
open TwoFoldOPI SymEnc
local notation "vl" => List.map Fin.val
/-- The data of the concrete `QFT_p` gadget `(i, c, g)`. -/
def qgDataN (x : ParN) (i c g : ℕ) : QGD :=
(aEN x i c g, resN x i c g, blkN x 3, blkN x 4, offN x 5, blkN x 6, blkN x 7, asQN x, offN x 15, blkN x 16,
blkN x 17, offN x 18)
/-- The data of the concrete `QFT_q` gadget `(i, c)`. -/
def qqDataN (x : ParN) (i c : ℕ) : QQD :=
(bRegN x i c, blkN x 9, blkN x 10, offN x 11, (List.range (pd x)).map (qgDataN x i c))
/-- The data of the concrete coordinate `i` (with its `P_β` table). -/
def cDataN (x : ParN) (pT : Tab) (i : ℕ) : CoordD :=
(bRegN x i 0, bRegN x i 1, blkN x 23, blkN x 24, offN x 25, pT, pT, blkN x 19, blkN x 20, offN x 21, offN x 22,
qqDataN x i 0, qqDataN x i 1)
variable (F : AvgCaseTI.FieldPres) (m t b nI : ℕ) (ht : 1 ≤ t) (htb : t ≤ b)
local notation "PP" => parOf F m t b nI
local notation "X" => toN (parOf F m t b nI)
end Lay
end OPI
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI OPI.Lay
variable {α : Type} [Coding α]
end OPI.W6.IsPR
end
-- ===== OPI.IRDecSub =====
section
/-!
# First-order twins of the subtraction circuit `R ⊖= O`
* `subGad_N`: one coordinate (a permutation gadget with the tables of `fShift F (∓1)`).
* `subAllN`, `subAll_N`: all coordinates (registers as lists of natural-number lists).
* `subAllCN`, `subAllC_N`: the circuit `revCirc (subAll …)`.
* Table data: `fShiftTabB_eq` (the tables of `fShift F s` in coordinates, from a pattern budget).
-/
namespace OPI
open QAlgorithms OPI.W6 TwoFoldOPI
local notation "vl" => List.map Fin.val
namespace SymEnc
variable {F : AvgCaseTI.FieldPres} {m n : ℕ}
set_option hygiene false in
local notation "L" => bitsPerSymbol F
/-- **Twin of `subAll`**: output registers `Os`, registers `Rs` (per coordinate, in order). -/
def subAllN (Os Rs : List (List ℕ)) (Z as : List ℕ) (f : ℕ) (T1 T2 : List (List Bool × List Bool)) :
List RN :=
(Os.zip Rs).flatMap (fun oR => permGadN oR.1 oR.2 Z as f T1 T2)
/-- **Twin of the circuit `revCirc (subAll …)`.** -/
def subAllCN (Os Rs : List (List ℕ)) (Z as : List ℕ) (f : ℕ) (T1 T2 : List (List Bool × List Bool)) :
List (List ℕ) :=
(subAllN Os Rs Z as f T1 T2).flatMap rnGates
end SymEnc
/-! ### Table data -/
end OPI
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI
variable {α : Type} [Coding α]
end OPI.W6.IsPR
end
-- ===== OPI.IRTrialN =====
section
/-!
# The gate fields of the trial circuit on natural-number data (tables still symbolic)
-/
namespace OPI
namespace Lay
open QAlgorithms QAlgorithms.OPI TwoFoldOPI SymEnc
local notation "vl" => List.map Fin.val
/-- The trial circuit from its decoder fields `D` and subtraction fields `S`. -/
def trialCN (D S : List (List ℕ)) : List (List ℕ) := D ++ S ++ D.reverse.flatMap invF
variable (F : AvgCaseTI.FieldPres) (m t b' : ℕ) {r : ℕ} (gen : Bool) (H : Matrix (Fin r) (Fin m) F.F)
local notation "KD" => kdOf F m gen H
local notation "nJ" => SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)
local notation "PQ" => parOf F m t (b' + 1) (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H))
local notation "XQ" => toN (parOf F m t (b' + 1) (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)))
local notation "NN" => total (parOf F m t (b' + 1) (SymEnc.nIds m (kdOf F m gen H) (kdOf F m gen H * kdOf F m gen H)))
local notation "BB" => GEP.Bd m (kdOf F m gen H + kdOf F m gen H * kdOf F m gen H)
variable (ht : 1 ≤ t) (htb : t ≤ b' + 1)
/-- The decoder registers as a list. -/
def RSN (x : ParN) (m B nI : ℕ) : List (List ℕ) := (List.range nI).map (rsOfN x m B nI)
end Lay
end OPI
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI OPI.Lay
variable {α : Type} [Coding α]
end OPI.W6.IsPR
end
-- ===== OPI.TabData =====
section
/-!
# Table data: first-order twins of the lookup tables
Every lookup table of the program is `funTable k G` (or `pgTab k cl G`) for some function `G` on
bit patterns. Its twin is `tabB k N G'` with the pattern enumeration bounded by a budget `N`
(`allPatsB`), and a realizable entry function `G'` computed from first-order data
(`p`, `e = natDegree`, the coefficient list `fl` of `f`, coordinates `E F x` of field elements).
-/
namespace OPI
namespace TD
open QAlgorithms TwoFoldOPI FM W6
/-- A table over all patterns of length `k`, enumerated within the budget `N`. -/
def tabB (k N : ℕ) (G : List Bool → List Bool) : List (List Bool × List Bool) :=
(allPatsB k N).map (fun pat => (pat, G pat))
/-! ### Small arithmetic helpers -/
/-- `bitsVal c mod p`, by Horner modulo `p` (clamped at `1`). -/
def bvm (p : ℕ) (c : List Bool) : ℕ := bitsValMod (max p 1) c
/-- `2^j mod p`. -/
def pow2Mod (p j : ℕ) : ℕ := bvm p (true :: List.replicate j false)
/-! ### `phaseTab` (QFTpCirc) -/
/-- The entry `(a, y) ↦ ⌊2^b ((a·y) mod p)/p⌋`. -/
def phEntryN (p w b : ℕ) (pat : List Bool) : List Bool :=
ldivBits b (bvm p (pat.take w) * bvm p (pat.drop w) % max p 1) p
def phaseTabN (p w b N : ℕ) : List (List Bool × List Bool) := tabB (w + w) N (phEntryN p w b)
/-! ### Controlled shifts `csTab` (IRRev2 / QPE) -/
/-- The entry of `csF p w k` on a pattern `c ++ y` with one control bit. -/
def csEntryN (p w k : ℕ) (pat : List Bool) : List Bool :=
if pat.take 1 = [true] then shiftLN p w k (pat.drop 1) else pat.drop 1
/-- The tables of a controlled shift by `km` (`km = k mod p`). -/
def csTabN (p w km N : ℕ) : List (List Bool × List Bool) × List (List Bool × List Bool) :=
(tabB (1 + w) N (csEntryN p w km), tabB (1 + w) N (csEntryN p w (p - km)))
/-! ### Readout tables `subF` / `addF` (Readout, `tauList_N`) -/
def subTabN (p w k cl N : ℕ) : List (List Bool × List Bool) :=
tabB k N (fun pat => shiftLN p w (p - bvm p (pat.take cl)) (pat.drop cl))
def addTabN (p w k cl N : ℕ) : List (List Bool × List Bool) :=
tabB k N (fun pat => shiftLN p w (bvm p (pat.take cl)) (pat.drop cl))
/-! ### Controlled swaps `cswF` (EGad) -/
def cswTabN (n k N : ℕ) : List (List Bool × List Bool) :=
tabB k N (fun pat => cswF n (pat.take 1) (pat.drop 1))
variable (F : AvgCaseTI.FieldPres)
/-! ### Field elements from their bit encodings -/
/-! ### Trace-dual re-encoding `pgTab … (Fq.RL F)` / `(Fq.RLinv F)` (QFTq, `QQ.RLL`) -/
def rlTabN (p e w : ℕ) (fl : List ℕ) (k cl N : ℕ) : List (List Bool × List Bool) :=
tabB k N (fun pat => RLM p e w fl (pat.drop cl))
def rlinvTabN (p e w : ℕ) (fl : List ℕ) (k cl N : ℕ) : List (List Bool × List Bool) :=
tabB k N (fun pat => RLinvB p e w N fl (pat.drop cl))
/-! ### `P_β` tables `SymEnc.pFun` (DecJ) -/
def pTabN (p e w : ℕ) (βE : List ℕ) (k cl N : ℕ) : List (List Bool × List Bool) :=
tabB k N (fun pat => pFunL p e w βE (pat.drop cl))
/-! ### The phase table `SymEnc.zTab` (PrepPhase) -/
def zTabN (p e w b : ℕ) (fl : List ℕ) (N : ℕ) : List (List Bool × List Bool) :=
tabB (e * w + e * w) N (zEntry p e w b fl)
/-! ### Shift tables `SymEnc.fShift` (RSub, PrepR) -/
def fsTabN (p e w : ℕ) (fl sE : List ℕ) (k cl N : ℕ) : List (List Bool × List Bool) :=
tabB k N (fun pat => fShiftM p e w fl sE (pat.take cl) (pat.drop cl))
/-! ### Repeat-until-success job tables (PrepAll, PrepJobs) -/
def validTabN (p e w k N : ℕ) : List (List Bool × List Bool) := tabB k N (fun v => [validL p e w v])
def memTabN (p e w : ℕ) (βE : List ℕ) (k N : ℕ) : List (List Bool × List Bool) :=
tabB k N (fun v => [memSL p e w βE v])
def ltTabN (p k N : ℕ) : List (List Bool × List Bool) := tabB k N (fun v => [decide (IsPR.bitsValS p v < p)])
/-! ### Tables of the compiled decoder program (SSA `compile`, GEPI3) -/
def progTabN (p e : ℕ) (fl : List ℕ) (Nf w L : ℕ) (x : KI) (N : ℕ) : List (List Bool × List Bool) :=
tabB (x.2.1.length * L) N (tabI ⟨p, e, fl, Nf⟩ w L x)
/-- The controlled-shift tables of a `QFT_p` gadget (`csTabs p w t` of IRQftG). -/
def csTabsN (p w t N : ℕ) : List (List (List Bool × List Bool) × List (List Bool × List Bool)) :=
(List.range t).map (fun i => csTabN p w (pow2Mod p (t - 1 - i)) N)
end TD
end OPI
/-! ## Realizers -/
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI OPI.FM OPI.TD
variable {α : Type} [Coding α]
end OPI.W6.IsPR
/-! ### Realizers of the first-order opcode semantics and the compiled-program tables -/
namespace OPI.W6.IsPR
open OAI.ThreeMachine.StackCompiler OPI OPI.FM OPI.TD
variable {α : Type} [Coding α]
end OPI.W6.IsPR
end
-- ===== OPI.IRRref =====
section
/-!
# Reduced row echelon form in first-order form
First-order twins of `RREF.rrefOf`, `RREF.free`, `RREF.NV`, and of `basisOf` / `bWof` / `Lay.kdOf`,
working on coordinate lists (a field element is its list `E x` of power-basis coordinates, a vector is
a list of such lists, a matrix a list of vectors). The field context enters as `(p, e, fl, N)`
(`ctxOf F N = ⟨F.p, F.f.natDegree, flOf F, N⟩`).
Every field operation of the twin *normalizes* its output (`nrm`: exactly `e` coordinates, reduced
modulo `max p 2`), so that all intermediate values stay small on every input, not only on encodings
of field elements; on encodings the normalization is the identity.
The twin follows the recursion of `RREF.insert` / `RREF.rrefOf`, and the equality lemmas are proved
by that recursion, with `E` pushed through each field operation.
-/
namespace OPI
namespace RRefC
open FM
/-! ## Normalized field operations -/
/-- Normalization: exactly `e` coordinates, each reduced modulo `P`. -/
def nrm (e P : ℕ) (a : List ℕ) : List ℕ := (List.range e).map (fun i => a.getD i 0 % P)
/-- Addition. -/
def addR (p e : ℕ) (a b : List ℕ) : List ℕ := nrm e (max p 2) (addL (max p 2) a b)
/-- Subtraction. -/
def subR (p e : ℕ) (a b : List ℕ) : List ℕ := nrm e (max p 2) (subL (max p 2) a b)
/-- Multiplication. -/
def mulR (p e : ℕ) (fl a b : List ℕ) : List ℕ := nrm e (max p 2) (mulM p fl a b)
/-- Negation. -/
def negR (p e : ℕ) (a : List ℕ) : List ℕ := subR p e (zeroL e) a
/-- Inversion by a budgeted search (as `invM`). -/
def invR (p e : ℕ) (fl : List ℕ) (N : ℕ) (a : List ℕ) : List ℕ :=
nrm e (max p 2) (((allLB p e N).find? (fun c => decide (mulM p fl c a = oneL e))).getD (zeroL e))
/-- Sum of a list. -/
def sumR (p e : ℕ) (l : List (List ℕ)) : List ℕ := l.foldl (addR p e) (zeroL e)
variable (F : AvgCaseTI.FieldPres)
/-! ## Vectors and rows -/
/-- Entry `c` of a vector (zero outside). -/
def ent (e : ℕ) (u : List (List ℕ)) (c : ℕ) : List ℕ := u.getD c (zeroL e)
/-- First-order rows: `(pivot, row)`. -/
abbrev RowsC := List (ℕ × List (List ℕ))
/-- The coordinates of a vector. -/
noncomputable def vecE {m : ℕ} (v : Fin m → F.F) : List (List ℕ) := List.ofFn (fun c => E F (v c))
/-- The coordinates of reduced rows. -/
noncomputable def rowsE {m : ℕ} (B : RREF.Rows F.F m) : RowsC := B.map (fun pu => (pu.1.val, vecE F pu.2))
/-! ## The twin of `RREF.insert` -/
/-- The reduction `v − Σ v(p) u`. -/
def reduceC (p e : ℕ) (fl : List ℕ) (m : ℕ) (B : RowsC) (v : List (List ℕ)) : List (List ℕ) :=
(List.range m).map fun c =>
subR p e (ent e v c) (sumR p e (B.map fun pu => mulR p e fl (ent e v pu.1) (ent e pu.2 c)))
/-- The first nonzero column. -/
def firstNZC (e m : ℕ) (w : List (List ℕ)) : Option ℕ := (List.range m).find? fun c => !isZ (ent e w c)
/-- The normalized new row `w(q)⁻¹ w`. -/
def newRowC (p e : ℕ) (fl : List ℕ) (N m : ℕ) (w : List (List ℕ)) (q : ℕ) : List (List ℕ) :=
(List.range m).map fun c => mulR p e fl (invR p e fl N (ent e w q)) (ent e w c)
/-- Clearing column `q` from the old rows. -/
def clearC (p e : ℕ) (fl : List ℕ) (m : ℕ) (B : RowsC) (q : ℕ) (row : List (List ℕ)) : RowsC :=
B.map fun qu => (qu.1, (List.range m).map fun c =>
subR p e (ent e qu.2 c) (mulR p e fl (ent e qu.2 q) (ent e row c)))
/-- Insert a vector. -/
def insertC (p e : ℕ) (fl : List ℕ) (N m : ℕ) (B : RowsC) (v : List (List ℕ)) : RowsC :=
if (firstNZC e m (reduceC p e fl m B v)).isSome then
clearC p e fl m B ((firstNZC e m (reduceC p e fl m B v)).getD 0)
(newRowC p e fl N m (reduceC p e fl m B v) ((firstNZC e m (reduceC p e fl m B v)).getD 0)) ++
[((firstNZC e m (reduceC p e fl m B v)).getD 0,
newRowC p e fl N m (reduceC p e fl m B v) ((firstNZC e m (reduceC p e fl m B v)).getD 0))]
else B
/-- **The rows of a matrix** (twin of `RREF.rrefOf`). -/
def rrefC (p e : ℕ) (fl : List ℕ) (N m : ℕ) (Hc : List (List (List ℕ))) : RowsC :=
Hc.foldl (insertC p e fl N m) []
section Eq
variable {m : ℕ} [DecidableEq F.F]
end Eq
/-! ## The nullspace basis -/
/-- The free columns. -/
def freeC (m : ℕ) (B : RowsC) : List ℕ := (List.range m).filter fun c => !(B.any fun pu => decide (pu.1 = c))
/-- Entry `c` of the nullspace vector of the free column `fc`. -/
def nvEntC (p e : ℕ) (B : RowsC) (fc c : ℕ) : List ℕ :=
if c = fc then oneL e
else if (B.find? fun pu => decide (pu.1 = c)).isSome then
negR p e (ent e ((B.find? fun pu => decide (pu.1 = c)).getD (0, [])).2 fc)
else zeroL e
/-- The nullspace basis. -/
def nvC (p e m : ℕ) (B : RowsC) : List (List (List ℕ)) :=
(freeC m B).map fun fc => (List.range m).map fun c => nvEntC p e B fc c
section NV
variable {m : ℕ} [DecidableEq F.F]
end NV
/-! ## The basis of `D`, its pivots, its size, and the Schur products -/
/-- The rows of the basis. -/
def GC (p e : ℕ) (fl : List ℕ) (N m : ℕ) (gen : Bool) (Hc : List (List (List ℕ))) : List (List (List ℕ)) :=
if gen then nvC p e m (rrefC p e fl N m Hc) else (rrefC p e fl N m Hc).map Prod.snd
/-- The pivots of the basis. -/
def pivC (p e : ℕ) (fl : List ℕ) (N m : ℕ) (gen : Bool) (Hc : List (List (List ℕ))) : List ℕ :=
if gen then freeC m (rrefC p e fl N m Hc) else (rrefC p e fl N m Hc).map Prod.fst
/-- The size of the basis. -/
def kdC (p e : ℕ) (fl : List ℕ) (N m : ℕ) (gen : Bool) (Hc : List (List (List ℕ))) : ℕ :=
(pivC p e fl N m gen Hc).length
/-- The pairwise products of a list of rows, index `j k + j'` for the pair `(j, j')`. -/
def bWofC (p e : ℕ) (fl : List ℕ) (m : ℕ) (G : List (List (List ℕ))) : List (List (List ℕ)) :=
(List.range (G.length * G.length)).map fun x => (List.range m).map fun o =>
mulR p e fl (ent e (G.getD (x / G.length) []) o) (ent e (G.getD (x % G.length) []) o)
/-- The pairwise products of the basis rows. -/
def bWC (p e : ℕ) (fl : List ℕ) (N m : ℕ) (gen : Bool) (Hc : List (List (List ℕ))) : List (List (List ℕ)) :=
bWofC p e fl m (GC p e fl N m gen Hc)
section Basis
variable {m r : ℕ} [DecidableEq F.F] (N : ℕ) (hN : F.p ^ F.f.natDegree ≤ N)
include hN
end Basis
end RRefC
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_Part04.lean