Theorem 8.2 — correctness of the quadratic ansatz
OpenTwoFoldOPI.Supplement.theorem_8_2coding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-algorithmsregev-reductionschur-product-codes
Consider Algorithm 8.1 on an input consisting of an odd-order field , a nonsquare , a matrix with linearly independent rows and , a code generated by the rows of , a vector with no zero entry and , a vector with , and . The algorithm computes
finds with by Gaussian elimination, and returns .
On all such inputs, Algorithm 8.1 returns a full-support solution of . Given , the algorithm is deterministic and uses polynomially many field operations in .
This is the classical core of Lemma 8.4 and Theorem 8.5: orthogonality to products of codewords removes the quadratic part of the syndrome, and the nonsquare makes every output coordinate nonzero.
Differences from the source:
- generalization: the algorithm returns a full-support solution for the z found by Gaussian elimination → the system of step 3 is solvable, and f(z) has no zero entry and satisfies Bf(z) = s for every solution z; reason: covers whichever solution elimination selects
- encoding: deterministic, polynomially many field operations in m, n, ℓ, given ξ → a program of the published LinSysAmp field-operation machine without sampling instructions, on the input layout ansatzConfig (ξ included), halting within P(m + n + ℓ) steps and outputting f(z) for a solution z with probability 1; P chosen before the field; reason: the base mission's field-operation model (Lemma 7.3)
- encoding: V = im Bᵀ, E generated by the rows of A, a nonsquare ξ ∈ F_q^× → V and E are the row spaces of B and A; ξ ≠ 0 and ξ is not a square; h ⊥ V ∗ E^{∗2} is Σ_j h_j x_j = 0 for every x in the span of the products u ⊙ e ⊙ e′; reason: same objects, Lean names
Preamble
import Mathlib import Definitions.Def_LinSysAmp_Machine import Definitions.Def_TwoFoldOPI_Supplement_schurTriple import Definitions.Def_TwoFoldOPI_Supplement_ansatzY0 import Definitions.Def_TwoFoldOPI_Supplement_ansatzF import Definitions.Def_TwoFoldOPI_Supplement_ansatzConfig
Formal statement
namespace TwoFoldOPI
namespace Supplement
/-- **Theorem 8.2 (correctness of the quadratic ansatz).**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §8.1, Theorem 8.2, p.45: "On all inputs satisfying the conditions listed in it, Algorithm 8.1
returns a full-support solution to By = s. Given ξ, the algorithm is deterministic and uses
polynomially many field operations in m, n, ℓ."; Algorithm 8.1, p.45 (Input: an odd-order field
F_q and a nonsquare ξ ∈ F_q^×; a code V ⊆ F_q^m and B ∈ F_q^{n×m} with linearly independent rows
such that V = im B^⊤; a code E ⊆ F_q^m generated by the rows of A ∈ F_q^{ℓ×m}; h ∈ F_q^m nonzero in
every coordinate with h ⊥ V ∗ E^{∗2}; w ∈ F_q^m with rank(B diag(w) A^⊤) = n; s ∈ F_q^n. Steps:
1. y_0 = ¼(h^{−1} ⊙ w^{⊙2} − ξh); 2. f(z) = ¼ h ⊙ [(A^⊤z + w ⊙ h^{−1})^{⊙2} − ξ1]; 3. Gaussian
elimination for z ∈ F_q^ℓ with (B diag(w) A^⊤) z = 2(s − By_0); 4. return y = f(z)).
There is one polynomial `P` such that for every finite field `K` of odd order there is a program
`prog` of the field-operation machine with no sampling instruction, such that on every input
`(m, n, ℓ, ξ, B, A, h, w, s)` meeting the conditions of Algorithm 8.1 (with `V` the row space of
`B` and `E` the row space of `A`):
1. step 3 has a solution;
2. for every solution `z` of step 3, `y = f(z)` has no zero entry and `By = s`;
3. `prog` halts within `P(m + n + ℓ)` steps with at most `P(m + n + ℓ)` field operations;
4. `prog` outputs `f(z)` with probability `1` for one solution `z` of step 3.
**Formalization Note.** Clauses 1–2 are "returns a full-support solution to By = s" for whatever
solution Gaussian elimination selects; clauses 3–4 say that steps 1–4 are carried out exactly
(deterministic: no `sample`; field operations counted by the published `LinSysAmp` machine, whose
oracle is never called). The input layout is `ansatzConfig`, `ξ` included ("Given ξ"). `P` is chosen
before the field; the program may depend on the field (its literals). "Nonsquare `ξ ∈ F_q^×`" is
`ξ ≠ 0 ∧ ¬IsSquare ξ`. `h ⊥ V ∗ E^{∗2}` is `Σ_j h_j x_j = 0` for all `x ∈ schurTriple V E`. -/
theorem theorem_8_2 :
∃ P : Polynomial ℕ, ∀ (K : Type) [Field K] [Fintype K] [DecidableEq K],
Odd (Fintype.card K) →
∃ prog : LinSysAmp.Program K, (∀ i ∈ prog, ∀ d, i ≠ LinSysAmp.Instr.sample d) ∧
∀ (m n ℓ : ℕ) (ξ : K) (B : Matrix (Fin n) (Fin m) K) (A : Matrix (Fin ℓ) (Fin m) K)
(h w : Fin m → K) (s : Fin n → K),
ξ ≠ 0 → ¬ IsSquare ξ → LinearIndependent K B → (∀ j, h j ≠ 0) →
(∀ x ∈ schurTriple (Submodule.span K (Set.range B)) (Submodule.span K (Set.range A)),
∑ j, h j * x j = 0) →
(B * Matrix.diagonal w * A.transpose).rank = n →
(∃ z : Fin ℓ → K, (B * Matrix.diagonal w * A.transpose).mulVec z =
(2 : K) • (s - B.mulVec (ansatzY0 ξ h w))) ∧
(∀ z : Fin ℓ → K, (B * Matrix.diagonal w * A.transpose).mulVec z =
(2 : K) • (s - B.mulVec (ansatzY0 ξ h w)) →
(∀ j, ansatzF ξ A h w z j ≠ 0) ∧ B.mulVec (ansatzF ξ A h w z) = s) ∧
(∀ O : LinSysAmp.Oracle m K,
LinSysAmp.HaltsWithin m O prog (ansatzConfig m n ℓ ξ B A h w s) (P.eval (m + n + ℓ)) 0
((P.eval (m + n + ℓ) : ℕ) : ℝ)) ∧
∃ z : Fin ℓ → K, (B * Matrix.diagonal w * A.transpose).mulVec z =
(2 : K) • (s - B.mulVec (ansatzY0 ξ h w)) ∧
∀ O : LinSysAmp.Oracle m K,
LinSysAmp.outputProb m O prog (ansatzConfig m n ℓ ξ B A h w s) (P.eval (m + n + ℓ))
(ansatzF ξ A h w z) = 1 := by sorry
end Supplement
end TwoFoldOPI
Source
Ragavan, Shutty, Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §8.1, Theorem 8.2, p. 45