Gate list of the compiled classical relinearization decoder in first-order form
ProvedOPI.FM.clsGatesC_FMLet with ; a field element is stored as a symbol of bits (its power-basis coordinates, bits each, so ). The classical part of the decoder is a straight-line program over (relinearization by Gaussian elimination), whose constants are a basis ( rows) of the dual code and the vectors ( rows) spanning its Schur square. A layout assigns to every straight-line id a register of wires, a list of ancilla wires and a flag wire . The reversible circuit (X, CNOT, Toffoli) compiles each instruction into a table lookup; turns it into a circuit over , and writes each gate as a list of naturals ( for , for , for CNOT).
Statement. Let and let be a list of wire lists with (default ) equal to the wire indices of for every . Then the list of gate fields of equals
where is the first-order (natural-number) form of the decoder program, with instructions and with the matrices , given by their coordinate lists; attaches to each instruction its lookup table over all bit patterns of the source registers, computed in the context (decode each block to coordinates, apply the opcode, re-encode); and is the explicit natural-number compilation of table lookups into gate fields.
This removes every field-valued object from the classical decoder part of the circuit, so this part can be output by the polynomial-time generator, which only manipulates natural numbers.
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 OPI.FM open QAlgorithms OPI.W6 local notation "vl" => List.map Fin.val open TwoFoldOPI SymEnc GEP RelinProg variable (F : AvgCaseTI.FieldPres) (N : ℕ)
theorem OPI.FM.clsGatesC_FM (hN : F.p ^ F.f.natDegree ≤ N) {n m k k2 : ℕ}
{reg : Fin m × Bool × Fin (bitsPerSymbol F) ↪ Fin n}
(C : ClsLay reg (elemBits F) (decodeElem F) (Fq.decode_elemBits F) k k2)
(bD : Fin k → Fin m → F.F) (bW : Fin k2 → Fin m → F.F)
(RS : List (List ℕ)) (hRS : ∀ x, vl (C.rs x) = RS.getD x []) :
(revCirc (clsGates C bD bW)).map gfields =
clsCN RS (vl C.as) C.f0.val (clsTabs (ctxOf F N) (Fq.w F) (bitsPerSymbol F)
(progI m (k + k2) k (fun j o => matI F.f.natDegree k m (matE F bD) j o) (a0src m k k2)
(a0opI F.f.natDegree k k2 m (matE F bD) (matE F bW)))) := by sorry