Grids of two-continuation segments represent a two-branch recursion as a DAG
ProvedOPI.grid_repPrograms are serialised as first-order DAGs, i.e. lists of nodes, where says that node of the list represents the program : the node has the head of , and its children have smaller indices and represent the subprograms of . A two-continuation segment maps two continuation indices and a start position to a list of nodes. It is valid for a binary program transformer if, whenever represent in , appending to gives a nonempty block whose last node represents . Assume every block of has the same length .
Let be programs with . Level is given: has length , and node represents for . The grid with levels appends, for and , the block at position , with continuations the nodes and . The node index of is . The theorem states that for all , all and all with ,
This is used for the majority votes of the gradient preparation, where is a measured test continuing with or . Sharing the subprograms gives a DAG with blocks instead of a tree of size . This keeps the generated program description polynomial.
import Definitions.Def_TwoFoldOPI_CL_Part04
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QAlgorithms_Defs_GradientMethods
import Definitions.Def_QAlgorithms_Defs_OPIOraclePrograms
import Definitions.Def_QAlgorithms_Defs_OPIUniformity
import Definitions.Def_QAlgorithms_Defs_Fourier
import Definitions.Def_TwoFoldOPI_elemBits
import Definitions.Def_TwoFoldOPI_schurSquare
import Definitions.Def_TwoFoldOPI_schurFailureSum
import Definitions.Def_CodingTheory
import Definitions.Def_OAIThreeMachineSched01
import Definitions.Def_CookLevin_Cost
import Definitions.Def_TwoFoldOPI_codeOf
import Definitions.Def_TwoFoldOPI_solves
import Definitions.Def_TwoFoldOPI_Input
import Definitions.Def_TwoFoldOPI_CLSerializableF
open OPI
open QAlgorithms QAlgorithms.OPI
variable {N c out : ℕ}
variable (T : ISeg2) (Nt S B : ℕ) (lev0 : ℕ → ℕ) (hS : ∀ k0 k1 st, (T k0 k1 st).length = S)
include hS
theorem OPI.grid_rep (F : Prog N c out → Prog N c out → Prog N c out) (hT : T.Valid F) (hS1 : 1 ≤ S)
(G : ℕ → ℕ → Prog N c out) (hG : ∀ r s, G (r + 1) s = F (G r s) (G r (s + 1)))
(D : List INode) (hB : D.length = B) (h0 : ∀ s ≤ Nt, Rep D (lev0 s) (G 0 s)) :
∀ R, ∀ r ≤ R, ∀ s, s + r ≤ Nt → Rep (D ++ gridNodes T Nt S B lev0 R) (gidx Nt S B lev0 r s) (G r s) := by sorry