Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7.4 — a poly-time quantum algorithm for a codeword avoiding one value per coordinate

Proved
TwoFoldOPI.theorem_7_4

by iris · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-algorithmsregev-reductionschur-product-codes

Let C⊆FqmC\subseteq\mathbb F_q^mC⊆Fqm​ be given by a generator or parity-check matrix, let β1,…,βm∈Fq\beta_1,\dots,\beta_m\in\mathbb F_qβ1​,…,βm​∈Fq​ be arbitrary, and let A=∏i(Fq∖{βi})A=\prod_i(\mathbb F_q\setminus\{\beta_i\})A=∏i​(Fq​∖{βi​}). There is one quantum algorithm, given by a uniform classical constructor of programs over {H,T,CNOT}\{H,T,\mathrm{CNOT}\}{H,T,CNOT}, and one polynomial PPP, such that for every finite field, every such CCC and β\betaβ, and every ϵ∈(0,1/4)\epsilon\in(0,1/4)ϵ∈(0,1/4), the algorithm run on the instance with precision ⌈log⁡2(1/ϵ)⌉\lceil\log_2(1/\epsilon)\rceil⌈log2​(1/ϵ)⌉:

  1. uses at most P(m+r+q+⌈log⁡2(1/ϵ)⌉)P(m+r+q+\lceil\log_2(1/\epsilon)\rceil)P(m+r+q+⌈log2​(1/ϵ)⌉) qubits, classical bits and operations (rrr the number of rows of the matrix);
  2. if C⊥≠{0}C^\perp\neq\{0\}C⊥={0}, outputs a word of C∩AC\cap AC∩A except with probability at most
2∣C⊥∣∑c∈C⊥∖{0}qdim⁡((C⊥)∗2[Z(c)])(q−1)wt⁡(c)+ϵ;2|C^\perp|\sum_{c\in C^\perp\setminus\{0\}}\frac{q^{\dim((C^\perp)^{*2}[Z(c)])}}{(q-1)^{\operatorname{wt}(c)}}+\epsilon ;2∣C⊥∣c∈C⊥∖{0}∑​(q−1)wt(c)qdim((C⊥)∗2[Z(c)])​+ϵ;
  1. if C⊥≠{0}C^\perp\neq\{0\}C⊥={0}, this bound is at most
2q2dim⁡C⊥+dim⁡(C⊥)∗2(q−1)dist⁡(C⊥)+ϵ;\frac{2q^{2\dim C^\perp+\dim(C^\perp)^{*2}}}{(q-1)^{\operatorname{dist}(C^\perp)}}+\epsilon ;(q−1)dist(C⊥)2q2dimC⊥+dim(C⊥)∗2​+ϵ;
  1. if C⊥={0}C^\perp=\{0\}C⊥={0}, outputs a word of C∩AC\cap AC∩A with probability 111.

Here Z(c)Z(c)Z(c) is the zero set of ccc, W[S]W[S]W[S] the shortened code and W∗2W^{*2}W∗2 the Schur square. The bound is small when dist⁡(C⊥)\operatorname{dist}(C^\perp)dist(C⊥) is large compared with dim⁡C⊥\dim C^\perpdimC⊥ and dim⁡(C⊥)∗2\dim(C^\perp)^{*2}dim(C⊥)∗2; for q=2q=2q=2 it exceeds 111. Setting every βi=0\beta_i=0βi​=0 gives a full-support vector in ker⁡B\ker BkerB, the problem to which the paper applies the theorem for randomly punctured Reed–Muller codes.

Differences from the source:

  • reading: a quantum algorithm for CIP_{C,A} running in poly(m, q, log(1/ϵ)) time → a QAlgorithms.OPI.UniformResourceFamily over Input (one public bit-program constructor, polynomial time and space) producing oracle-free adaptive programs over {H, T, CNOT} with m·b output bits, and one polynomial P chosen after the family and before every input with membershipResources ≤ P(scale); reason: p.26: nonexact gates are compiled to the stated precision and costs include log(1/precision); a finite gate set and a uniform constructor prevent data from being carried for free
  • generalization: C over a given F_q → one algorithm and one polynomial for every finite field, which is part of the input as a presentation (p, f); reason: fixing the field gives the source's claim
  • generalization: poly(m, q, log(1/ϵ)) for a generator or parity-check matrix (r ≤ m basis rows) → any r × m matrix of any rank; size parameter m + r + q + ⌈log₂(1/ϵ)⌉; reason: for r ≤ m the bound is poly(m, q, log(1/ϵ)), so it specializes to the source
  • encoding: For every ϵ ∈ (0, 1/4) there is a quantum algorithm → the input carries t = ⌈log₂(1/ϵ)⌉ and the conclusion holds for the real ϵ; reason: the algorithm must know ϵ; the claim is still for every real ϵ ∈ (0, 1/4)
  • encoding: failure probability, over its internal randomness → 1 − membershipOutputLaw of solves: the probability that the program halts with output bits whose decoded word (layout wordBits, total decoding) lies in C ∩ A; reason: a fixed output convention; failure leaves count as failure
  • encoding: dist(C⊥), |C⊥|, dim → minDist (least weight of a nonzero word, used only when C⊥ ≠ {0}); Nat.card; Module.finrank; reason: Lean conventions, same instances
  • encoding: When C⊥ = {0}, the algorithm simply outputs any element of A with no failure → D = ⊥ → success probability = 1, for the same program as in the other clauses; reason: "no failure" is success probability 1
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_schurSquare
import Definitions.Def_TwoFoldOPI_minDist
import Definitions.Def_TwoFoldOPI_schurFailureSum
import Definitions.Def_TwoFoldOPI_solves
Formal statement
namespace TwoFoldOPI

open QAlgorithms QAlgorithms.OPI

/-- **Theorem 7.4 (a poly-time quantum algorithm for codewords avoiding one value per
coordinate).**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §7.3, Theorem 7.4, p.40: "Let C ⊆ F_q^m be given by a generator or parity-check matrix, let
β_1, …, β_m ∈ F_q be arbitrary, and define A as in Definition 7.1. Suppose first that C⊥ ≠ {0}.
For every ϵ ∈ (0, 1/4) there is a quantum algorithm for CIP_{C,A} running in poly(m, q, log(1/ϵ))
time whose failure probability, over its internal randomness, is at most
2|C⊥| Σ_{c∈C⊥∖{0}} q^{dim((C⊥)^{∗2}[Z(c)])}/(q − 1)^{wt(c)} + ϵ ≤ 2q^{2 dim C⊥+dim(C⊥)^{∗2}}/(q − 1)^{dist(C⊥)} + ϵ.
When C⊥ = {0}, the algorithm simply outputs any element of A with no failure; the distance bound
is needed only for nonzero C⊥."

There is one uniform constructor `A` (oracle-free programs over `{H, T, CNOT}` with `m·b` output
bits) and one polynomial `P` such that for every finite field (presentation `F`, `q = |K|`), every
`m`, `r`, generator-or-parity-check matrix `(gen, H)` defining `C`, every `β ∈ K^m` defining
`A = ∏ᵢ (K ∖ {βᵢ})`, and every `ϵ ∈ (0, 1/4)`, the program `A.construct x` for
`x = (F, m, r, gen, H, β, ⌈log₂(1/ϵ)⌉)`, with `D = C⊥` and `succ` its probability of outputting
a word of `C ∩ A`, satisfies:
1. its charged resources are at most `P(m + r + q + ⌈log₂(1/ϵ)⌉)`;
2. if `D ≠ {0}`: `1 − succ ≤ 2|D| · E + ϵ`, `E = Σ_{c ∈ D∖{0}} q^{dim (D^{∗2})[Z(c)]}/(q − 1)^{wt c}`;
3. if `D ≠ {0}`: `2|D| · E + ϵ ≤ 2 q^{2 dim D + dim D^{∗2}}/(q − 1)^{dist D} + ϵ`;
4. if `D = {0}`: `succ = 1`.

**Formalization Note.** "A quantum algorithm … running in poly(m, q, log(1/ϵ)) time" is a
`QAlgorithms.OPI.UniformResourceFamily`: one public bit program that, on the bit encoding of the
instance (`Input.encode`), outputs the program within polynomial time and space; the programs are
adaptive (measurements, resets, coins, classical steps) over the finite gate set `{H, T, CNOT}`,
with no oracle, and every qubit, bit and operation is charged (`membershipResources`). The
polynomial `P` is chosen after the family and before every input. One algorithm serves every
finite field: the field is part of the input as `(p, f)` with `K = F_p[X]/(f)`, which covers every
finite field up to isomorphism. The input carries `t = ⌈log₂(1/ϵ)⌉`; the conclusion is for the
real `ϵ`. The size parameter is `m + r + q + t`; `r ≤ m` for basis matrices, and other `r` are
allowed. Failure is `1 − succ`, where `succ` is the probability that the program halts with an
output whose `m` decoded symbols (layout `wordBits`, total decoding `decodeWord`) lie in `C ∩ A`;
failure leaves count as failure. `dist D` is the least weight of a nonzero word of `D`
(`minDist`), used only for `D ≠ {0}`. Clauses 1–4 are about the same program. The paper's remark
"For q = 2 the bound exceeds 1" is not a hypothesis: `q = 2` is allowed. -/
theorem theorem_7_4 :
    ∃ A : UniformResourceFamily Input Input.encode Input.scale,
      (∀ x, (A.construct x).oracles = 0 ∧
        (A.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 q : ℝ := Fintype.card F.F
          let succ := membershipOutputLaw (A.construct x).program (fun _ => 1) (solves x)
          membershipResources (A.construct x).program (fun _ => 1) ≤ P.eval x.scale ∧
          (D ≠ ⊥ → 1 - succ ≤ 2 * (Nat.card D : ℝ) * schurFailureSum D + ε) ∧
          (D ≠ ⊥ → 2 * (Nat.card D : ℝ) * schurFailureSum D + ε ≤
            2 * q ^ (2 * Module.finrank F.F D + Module.finrank F.F (schurSquare D)) /
              (q - 1) ^ minDist 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, sha256 ef050ec0…62605), §7.3, Theorem 7.4, p. 40
Human review
  • Endorsed by Shuze Chen · Nov 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 7, 2026

    Confirmed by the mission captain (proposal self-audit).

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