Theorem 7.4 — a poly-time quantum algorithm for a codeword avoiding one value per coordinate
ProvedTwoFoldOPI.theorem_7_4coding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-algorithmsregev-reductionschur-product-codes
Let be given by a generator or parity-check matrix, let be arbitrary, and let . There is one quantum algorithm, given by a uniform classical constructor of programs over , and one polynomial , such that for every finite field, every such and , and every , the algorithm run on the instance with precision :
- uses at most qubits, classical bits and operations ( the number of rows of the matrix);
- if , outputs a word of except with probability at most
- if , this bound is at most
- if , outputs a word of with probability .
Here is the zero set of , the shortened code and the Schur square. The bound is small when is large compared with and ; for it exceeds . Setting every gives a full-support vector in , 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.