Theorem 7.4, algorithmic part, with a Cook–Levin constructor on raw prefixes
ProvedTwoFoldOPI.theorem_7_4_CLSerializableFThis is the algorithmic content of Theorem 7.4, with uniformity expressed through polynomial-time Cook–Levin machines.
Let be an explicitly presented finite field. An instance consists of an matrix over with a tag saying whether is a generator matrix ( is its row space) or a parity-check matrix (), forbidden values defining , and a precision . Write and
There are
- a family of oracle-free adaptive programs over with output bits ( bits per field symbol), and
- one polynomial ,
with the following properties. Two polynomial-time Cook–Levin machines, given the first bits of , decide whether and , and, when this holds, output the canonical serialization of . For every finite field, every , every , every and every , the program for the instance with satisfies, with its probability of outputting a word of :
- it uses at most qubits, classical bits and operations;
- if , then ;
- if , then .
Together with the bridge TwoFoldOPI.uniformFamily_of_CLSerializableF, this gives TwoFoldOPI.theorem_7_4_algorithm.
Formalization Note. Serializability is TwoFoldOPI.CLSerializableF. All other notions (membershipResources, membershipOutputLaw, solves, schurFailureSum) are exactly those of TwoFoldOPI.theorem_7_4. All clauses are about the same program. This statement replaces TwoFoldOPI.theorem_7_4_RAMSerializableF, whose word-RAM constructor would have to be written instruction by instruction.
import Mathlib import Definitions.Def_CodingTheory import Definitions.Def_QAlgorithms_Defs_OPIOraclePrograms import Definitions.Def_QAlgorithms_Defs_OPIUniformity import Definitions.Def_TwoFoldOPI_elemBits import Definitions.Def_TwoFoldOPI_Input import Definitions.Def_TwoFoldOPI_codeOf import Definitions.Def_TwoFoldOPI_schurFailureSum import Definitions.Def_TwoFoldOPI_solves import Definitions.Def_TwoFoldOPI_CLSerializableF
namespace TwoFoldOPI
open QAlgorithms QAlgorithms.OPI
theorem theorem_7_4_CLSerializableF :
∃ construct : Input → PackedMembershipProgram, CLSerializableF construct ∧
(∀ x, (construct x).oracles = 0 ∧
(construct x).outputBits = x.m * bitsPerSymbol x.F) ∧
∃ P : Polynomial ℕ,
∀ (F : AvgCaseTI.FieldPres) (m r : ℕ) (gen : Bool) (H : Matrix (Fin r) (Fin m) F.F)
(β : Fin m → F.F) (ε : ℝ), 0 < ε → ε < 1 / 4 →
let x : Input := ⟨F, m, r, gen, H, β, ⌈Real.logb 2 (1 / ε)⌉₊⟩
let D := CodingTheory.dualCode F.F (Fin m) (codeOf gen H)
let succ := membershipOutputLaw (construct x).program (fun _ => 1) (solves x)
membershipResources (construct x).program (fun _ => 1) ≤ P.eval x.scale ∧
(D ≠ ⊥ → 1 - succ ≤ 2 * (Nat.card D : ℝ) * schurFailureSum D + ε) ∧
(D = ⊥ → succ = 1) := by sorry
end TwoFoldOPI