Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.4, algorithmic part, with a Cook–Levin constructor on raw prefixes

Proved
TwoFoldOPI.theorem_7_4_CLSerializableF

by sragavan · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theoryoptimal-polynomial-intersectionquantum-algorithmsregev-reductionschur-product-codesturing-machines

This is the algorithmic content of Theorem 7.4, with uniformity expressed through polynomial-time Cook–Levin machines.

Let Fq=Fp[X]/(f)\mathbb F_q=\mathbb F_p[X]/(f)Fq​=Fp​[X]/(f) be an explicitly presented finite field. An instance consists of an r×mr\times mr×m matrix HHH over Fq\mathbb F_qFq​ with a tag saying whether HHH is a generator matrix (CCC is its row space) or a parity-check matrix (C=ker⁡HC=\ker HC=kerH), forbidden values β∈Fqm\beta\in\mathbb F_q^mβ∈Fqm​ defining A=∏i(Fq∖{βi})A=\prod_i(\mathbb F_q\setminus\{\beta_i\})A=∏i​(Fq​∖{βi​}), and a precision ttt. Write D=C⊥D=C^\perpD=C⊥ and

E=∑c∈D∖{0}qdim⁡(D∗2)[Z(c)](q−1)wt(c).E=\sum_{c\in D\setminus\{0\}}\frac{q^{\dim (D^{*2})[Z(c)]}}{(q-1)^{\mathrm{wt}(c)}}.E=c∈D∖{0}∑​(q−1)wt(c)qdim(D∗2)[Z(c)]​.

There are

  • a family x↦construct(x)x\mapsto\mathrm{construct}(x)x↦construct(x) of oracle-free adaptive programs over {H,T,CNOT}\{H,T,\mathrm{CNOT}\}{H,T,CNOT} with m⋅bm\cdot bm⋅b output bits (bbb bits per field symbol), and
  • one polynomial PPP,

with the following properties. Two polynomial-time Cook–Levin machines, given the first sss bits of enc(x)0∞\mathrm{enc}(x)0^\inftyenc(x)0∞, decide whether s≥∣enc(x)∣s\ge|\mathrm{enc}(x)|s≥∣enc(x)∣ and s≥m+r+q+ts\ge m+r+q+ts≥m+r+q+t, and, when this holds, output the canonical serialization of construct(x)\mathrm{construct}(x)construct(x). For every finite field, every m,rm,rm,r, every (H,gen)(H,\mathrm{gen})(H,gen), every β\betaβ and every ϵ∈(0,1/4)\epsilon\in(0,1/4)ϵ∈(0,1/4), the program for the instance with t=⌈log⁡2(1/ϵ)⌉t=\lceil\log_2(1/\epsilon)\rceilt=⌈log2​(1/ϵ)⌉ satisfies, with succ\mathrm{succ}succ its probability of outputting a word of C∩AC\cap AC∩A:

  1. it uses at most P(m+r+q+t)P(m+r+q+t)P(m+r+q+t) qubits, classical bits and operations;
  2. if D≠{0}D\neq\{0\}D={0}, then 1−succ≤2∣D∣ E+ϵ1-\mathrm{succ}\le 2|D|\,E+\epsilon1−succ≤2∣D∣E+ϵ;
  3. if D={0}D=\{0\}D={0}, then succ=1\mathrm{succ}=1succ=1.

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.

Preamble
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
Formal statement
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
Source
Ragavan, Shutty, Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability, arXiv:2610.00502 (version held), §7.3, Theorem 7.4, p.40 (statement: running time, first failure bound, the case C⊥ = {0}) and its proof, pp.40–41.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me