Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.4, algorithmic part, with a word-RAM constructor

Open
TwoFoldOPI.theorem_7_4_RAMSerializable

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

coding-theoryoptimal-polynomial-intersectionquantum-algorithmsregev-reductionschur-product-codesword-ram

This is the algorithmic content of Theorem 7.4, with uniformity expressed through a word-RAM constructor.

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), whose canonical serializations are computed from the padded encoding 1m+r+q+t0 enc(x)1^{m+r+q+t}0\,\mathrm{enc}(x)1m+r+q+t0enc(x) by a polynomial-time word-RAM algorithm, and one polynomial PPP, such that 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_RAMSerializable, this gives TwoFoldOPI.theorem_7_4_algorithm.

Formalization Note. RAM-serializability is TwoFoldOPI.RAMSerializable; all other notions (membershipResources, membershipOutputLaw, solves, schurFailureSum) are exactly those of TwoFoldOPI.theorem_7_4. The polynomial PPP is chosen after the family and before every input, and all clauses are about the same program.

Retired. Superseded by TwoFoldOPI.theorem_7_4_RAMSerializableF: uniformity is now reduced through RAM-serializability on raw prefixes (TwoFoldOPI.RAMSerializableF), where the constructor itself recognises when a zero-padded prefix is long enough. This removes the separate parser lemmas.

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_RAMSerializable
Formal statement
namespace TwoFoldOPI

open QAlgorithms QAlgorithms.OPI

theorem theorem_7_4_RAMSerializable :
    ∃ construct : Input → PackedMembershipProgram, RAMSerializable 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