Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.28 — average-case CIP via Regev's reduction

Open
TwoFoldOPI.Supplement.theorem_5_28

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

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

Let C⊆FqMC\subseteq\mathbb F_q^MC⊆FqM​ be a linear code and let D\mathcal DD be a distribution on represented instances III (public data plus fixed classical function oracles, with target set A(I)A(I)A(I)) that is translation-invariant: I+vI+vI+v has law D\mathcal DD for every fixed v∈FqMv\in\mathbb F_q^Mv∈FqM​, where the translation action satisfies A(I+v)=A(I)+vA(I+v)=A(I)+vA(I+v)=A(I)+v, (I+v)+w=I+(v+w)(I+v)+w=I+(v+w)(I+v)+w=I+(v+w), I+0=II+0=II+0=I. Assume A(I)≠∅A(I)\neq\emptysetA(I)=∅ on the support, and write ∣A⟩|A\rangle∣A⟩ for the uniform state on A=A(I)A=A(I)A=A(I). Assume, uniformly over the support:

  1. a coherent decoder solves QDPC⊥,QFT†∣A⟩\mathrm{QDP}_{C^\perp,\mathrm{QFT}^\dagger|A\rangle}QDPC⊥,QFT†∣A⟩​ with probability at least a known Pdec>0P_{\mathrm{dec}}>0Pdec​>0, using TdecT_{\mathrm{dec}}Tdec​ gates and QdecQ_{\mathrm{dec}}Qdec​ oracle queries;
  2. for every δ>0\delta>0δ>0 a state δ\deltaδ-close to ∣A⟩|A\rangle∣A⟩ in trace distance can be prepared with Tprep(q,M,log⁡(1/δ))T_{\mathrm{prep}}(q,M,\log(1/\delta))Tprep​(q,M,log(1/δ)) gates and Qprep(q,M,log⁡(1/δ))Q_{\mathrm{prep}}(q,M,\log(1/\delta))Qprep​(q,M,log(1/δ)) queries.

Fix ϵ∈(0,1/4)\epsilon\in(0,1/4)ϵ∈(0,1/4) and put τ=log⁡2(16/(ϵPdec))\tau=\log_2(16/(\epsilon P_{\mathrm{dec}}))τ=log2​(16/(ϵPdec​)). Then there is a quantum algorithm for CIPC,D\mathrm{CIP}_{C,\mathcal D}CIPC,D​ with success probability at least Pdec−ϵP_{\mathrm{dec}}-\epsilonPdec​−ϵ,

expected gate complexity O ⁣(Tdec+Tprep(q,M,τ)+poly(M,log⁡q,τ)Pdec),expected query complexity O ⁣(Qdec+Qprep(q,M,τ)Pdec).\text{expected gate complexity } O\!\left(\frac{T_{\mathrm{dec}}+T_{\mathrm{prep}}(q,M,\tau)+\mathrm{poly}(M,\log q,\tau)}{P_{\mathrm{dec}}}\right),\qquad \text{expected query complexity } O\!\left(\frac{Q_{\mathrm{dec}}+Q_{\mathrm{prep}}(q,M,\tau)}{P_{\mathrm{dec}}}\right).expected gate complexity O(Pdec​Tdec​+Tprep​(q,M,τ)+poly(M,logq,τ)​),expected query complexity O(Pdec​Qdec​+Qprep​(q,M,τ)​).

A bounded-time version has the same success guarantee and gate and query bounds larger by a factor O(log⁡(1/ϵ))O(\log(1/\epsilon))O(log(1/ϵ)).

This is the average-case form of Regev's reduction used in Part II: decoding in the Fourier domain gives code intersection on average over a translation-invariant instance distribution.

Differences from the source:

  • reading: an instance representation is public classical data plus optional fixed classical function oracles specifying A(I), with a translation action (Definitions 5.26–5.27, left abstract) → a RepModel: a type of representations with public data, classical function oracles evaluated reversibly, a finite target set and a translation action satisfying the three laws; programs see only the public data and query the oracles; reason: the paper fixes no concrete representation; this is the most general interface with the stated properties
  • reading: public data and oracle access for I + v can be constructed or simulated from I, v, with all costs included in the preparation and decoding costs → decoders and preparations for I + v are programs chosen from (pub I, v) that query the oracles of I, with their costs bounded by T_dec, Q_dec, T_prep, Q_prep; reason: states the simulation clause of Definition 5.27 as part of the cost hypotheses
  • reading: a state δ-close to |A⟩ can be prepared → a coherent oracle program from |0⟩ whose first M·b qubits (work qubits traced out) are within trace distance δ of |A⟩ in the published word layout; reason: same preparation convention as the published Theorem 5.30
  • reading: expected gate complexity and expected query complexity → for the trial program repeated until it accepts: per-trial expected count divided by the acceptance probability; gate cost counts qubits, classical bits and every non-query operation, query cost counts queries; success is Pr[accept and output in C ∩ A(I)]/Pr[accept], averaged over I; reason: Wald's identity for the restart loop of the proof; same convention as the published TwoFoldOPI.expectedCost
  • encoding: O(·), poly(M, log q, τ) and O(log(1/ϵ)) → one constant K and one polynomial P chosen before every instance; P(M + ⌈log₂ q⌉ + ⌈τ⌉); bounded-time factor K(1 + ⌈log₂(1/ϵ)⌉); reason: explicit quantifiers for the asymptotic notation, as in the published Theorem 5.30
  • encoding: oracle queries (controlled evaluations use at most two queries) → programs use uncontrolled queries and their inverses only; reason: a controlled query costs at most two uncontrolled ones (p.26), a constant factor absorbed by O(·)
  • encoding: success averaged over I ← D → tsum over representations weighted by the probability mass function of D; reason: Lean convention for expectations over a discrete distribution
Preamble
import Mathlib
import Definitions.Def_CodingTheory
import Definitions.Def_QAlgorithms_Defs_GradientMethods
import Definitions.Def_QAlgorithms_Defs_QuantumOutputMetrics
import Definitions.Def_QAlgorithms_Defs_OPIOraclePrograms
import Definitions.Def_TwoFoldOPI_elemBits
import Definitions.Def_TwoFoldOPI_wordBits
import Definitions.Def_TwoFoldOPI_decodeWord
import Definitions.Def_TwoFoldOPI_uniformState
import Definitions.Def_TwoFoldOPI_Supplement_RepModel
import Definitions.Def_TwoFoldOPI_Supplement_coherentCounts
import Definitions.Def_TwoFoldOPI_Supplement_qdpSuccessO
import Definitions.Def_TwoFoldOPI_Supplement_prefixDensity
import Definitions.Def_TwoFoldOPI_Supplement_leafAverage
import Definitions.Def_TwoFoldOPI_Supplement_leafWorst
Formal statement
namespace TwoFoldOPI

namespace Supplement

open QAlgorithms QAlgorithms.OPI

/-- **Theorem 5.28 (average-case CIP via Regev's reduction).**
Ragavan, Shutty, *Quantum Algorithms for OPI Variants Beyond Locality and Classical
Decodability*, arXiv:2610.00502 (version held, sha256 ef050ec0…62605), §5.2, Theorem 5.28, p.27: "Let C ⊆ F_q^M be a linear code and let D be translation-invariant
in the sense of Definition 5.27, with A(I) ≠ ∅ on its support. Write |A⟩ for the uniform state on
A = A(I). Assume, uniformly for every represented instance in this support: • A coherent decoder, as
in the computational conventions above, solves QDP_{C⊥,QFT†|A⟩} with probability at least a known
lower bound P_dec > 0, using T_dec gates and Q_dec oracle queries. • For every δ > 0, a state
δ-close to |A⟩ can be prepared using T_prep(q, M, log(1/δ)) gates and Q_prep(q, M, log(1/δ)) queries.
These are worst-case requirements over represented instances; decoder success is averaged over the
uniform hidden codeword as in the definition of QDP. Fix ϵ ∈ (0, 1/4) and put τ = log_2(16/(ϵP_dec)).
There is a quantum algorithm for CIP_{C,D} with success probability at least P_dec − ϵ, expected
gate complexity O((T_dec + T_prep(q, M, τ) + poly(M, log q, τ))/P_dec), and expected query
complexity O((Q_dec + Q_prep(q, M, τ))/P_dec). A bounded-time version has the same success guarantee
and gate and query bounds larger by a factor O(log(1/ϵ))."; Definitions 5.25–5.27, pp.26–27;
"Computational conventions", p.26.

One constant `K` and one polynomial `P` serve every instance. For every field presentation `F`,
code `C ⊆ F^M`, represented-instance model `Mo` (`RepModel`: public data, classical function
oracles, target sets, translation action) and distribution `D` on representations with
`D(I + v) = D` for every `v` and `A(I) ≠ ∅` on its support; every `P_dec > 0`, `T_dec`, `Q_dec` and
decoder `dec(pub I, v)` that, for every `I` in the support and every `v`, is coherent with at most
`T_dec` gates plus qubits and `Q_dec` queries to the oracles of `I` and solves
`QDP_{C⊥,QFT†|A(I+v)⟩}` with probability `≥ P_dec`; every `T_prep, Q_prep` such that for every
`δ > 0` a coherent `prep(pub I, v)` with at most `T_prep(log₂(1/δ))` gates plus qubits and
`Q_prep(log₂(1/δ))` queries leaves its register of `M` symbols within trace distance `δ` of
`|A(I+v)⟩`; and every `ϵ ∈ (0, 1/4)`, with `τ = log₂(16/(ϵ P_dec))`,
`G = (T_dec + T_prep(τ) + P(M + ⌈log₂ q⌉ + ⌈τ⌉))/P_dec` and `Q = (Q_dec + Q_prep(τ))/P_dec`:
1. (restarts) there is a trial program `T(pub I)` with oracle access to `I` whose acceptance
   probability is positive, whose restart loop has expected gate cost `≤ K·G` and expected query
   cost `≤ K·Q` on every `I` in the support, and whose restart-loop success, averaged over
   `I ← D`, is `≥ P_dec − ϵ`;
2. (bounded time) there is a program `B(pub I)` with worst-case gate cost
   `≤ K(1 + ⌈log₂(1/ϵ)⌉)·G` and query cost `≤ K(1 + ⌈log₂(1/ϵ)⌉)·Q` on every `I` in the support,
   whose probability of outputting a word of `C ∩ A(I)`, averaged over `I ← D`, is `≥ P_dec − ϵ`.

**Formalization Note.** Programs are `QAlgorithms.OPI.AdaptiveMembershipProgram`s over
`{H, T, CNOT}` querying the oracles of the representation (no controlled queries); they may depend
on the public data `pub I`, never on `I` itself. The theorem is non-uniform, as printed: the
programs may depend on the whole setting (`F, C, Mo, D`, the decoders, `ϵ`). The cost clause of
Definition 5.27 is the reading that decoders and preparations for `I + v` are built from
`(pub I, v)` and query the oracles of `I`, their costs included in `T_dec`, `Q_dec`, `T_prep`,
`Q_prep`. "Coherent" is `coherentCounts ≠ none` (gates and queries only); gate costs include the
qubits ("including its work registers"); preparations are coherent from `|0⟩` and the prepared
register is the first `M·b` wires (layout `wordBits`), work wires traced out. "Expected
complexity" is that of "repeat the trial until it accepts" (Wald's identity: per-trial expectation
divided by the acceptance probability); its success is `Pr[accept ∧ good]/Pr[accept]`. Gate cost
counts qubits, classical bits, gates, resets, measurements and classical steps; query cost counts
queries. `O(·)`, `poly(·)` are `K` and `P` chosen before everything; `O(log(1/ϵ))` is
`K(1 + ⌈log₂(1/ϵ)⌉)`. Averages over `I ← D` are `tsum`s against the probability mass function. -/
theorem theorem_5_28 :
    ∃ (Kc : ℕ) (P : Polynomial ℕ),
      ∀ (F : AvgCaseTI.FieldPres) (M : ℕ) (C : Submodule F.F (Fin M → F.F))
        (Mo : RepModel F.F M) (D : PMF Mo.Rep),
      (∀ v, D.map (fun I => Mo.shift I v) = D) →
      (∀ I ∈ D.support, (Mo.target I).Nonempty) →
      ∀ (Pdec : ℝ) (Tdec Qdec w : ℕ)
        (dec : Mo.Pub → (Fin M → F.F) → AdaptiveMembershipProgram htcxGateSet
          (fun k => Mo.inW k + Mo.outW k) (fun _ => false)
          (M * bitsPerSymbol F + (M * bitsPerSymbol F + w)) 0 0),
      0 < Pdec →
      (∀ I ∈ D.support, ∀ v, ∃ g k : ℕ, coherentCounts (dec (Mo.pub I) v) = some (g, k) ∧
          g + (M * bitsPerSymbol F + (M * bitsPerSymbol F + w)) ≤ Tdec ∧ k ≤ Qdec ∧
          Pdec ≤ qdpSuccessO F M w (Mo.oracles I) (CodingTheory.dualCode F.F (Fin M) C)
            (uniformState (Mo.target (Mo.shift I v))) (dec (Mo.pub I) v)) →
      ∀ Tprep Qprep : ℝ → ℕ,
      (∀ δ : ℝ, 0 < δ → ∃ (w' : ℕ)
          (prep : Mo.Pub → (Fin M → F.F) → AdaptiveMembershipProgram htcxGateSet
            (fun k => Mo.inW k + Mo.outW k) (fun _ => false) (M * bitsPerSymbol F + w') 0 0),
          ∀ I ∈ D.support, ∀ v, ∃ g k : ℕ, coherentCounts (prep (Mo.pub I) v) = some (g, k) ∧
            g + (M * bitsPerSymbol F + w') ≤ Tprep (Real.logb 2 (1 / δ)) ∧
            k ≤ Qprep (Real.logb 2 (1 / δ)) ∧
            traceDistance
              (prefixDensity (M * bitsPerSymbol F) (M * bitsPerSymbol F + w')
                ((adaptiveExecution (Mo.oracles I) (prep (Mo.pub I) v)
                  (pureDensity (zeroKet _)) (fun _ => false)).map fun leaf => leaf.1.2).sum)
              (pureDensity (∑ x, uniformState (Mo.target (Mo.shift I v)) x •
                ket (wordBits F M x))) ≤ δ) →
      ∀ ε : ℝ, 0 < ε → ε < 1 / 4 →
        let τ : ℝ := Real.logb 2 (16 / (ε * Pdec))
        let G : ℝ := ((Tdec : ℝ) + (Tprep τ : ℝ) +
          ((P.eval (M + Nat.clog 2 (Fintype.card F.F) + ⌈τ⌉₊) : ℕ) : ℝ)) / Pdec
        let Q : ℝ := ((Qdec : ℝ) + (Qprep τ : ℝ)) / Pdec
        let good : Mo.Rep → (Fin (M * bitsPerSymbol F) → Bool) → Prop := fun I bits =>
          decodeWord F M bits ∈ C ∧ decodeWord F M bits ∈ Mo.target I
        (∃ (N c : ℕ) (T : Mo.Pub → AdaptiveMembershipProgram htcxGateSet
            (fun k => Mo.inW k + Mo.outW k) (fun _ => false) N c (M * bitsPerSymbol F + 1)),
          (∀ I ∈ D.support,
            0 < membershipOutputLaw (T (Mo.pub I)) (Mo.oracles I)
                (fun o => ∃ bits, o = some bits ∧ bits (Fin.last _) = true) ∧
            ((((N + c : ℕ) : ℝ) + leafAverage (T (Mo.pub I)) (Mo.oracles I)
                (fun cnt => cnt 1 + cnt 2 + cnt 3 + cnt 4)) /
              membershipOutputLaw (T (Mo.pub I)) (Mo.oracles I)
                (fun o => ∃ bits, o = some bits ∧ bits (Fin.last _) = true)) ≤ (Kc : ℝ) * G ∧
            (leafAverage (T (Mo.pub I)) (Mo.oracles I) (fun cnt => cnt 0) /
              membershipOutputLaw (T (Mo.pub I)) (Mo.oracles I)
                (fun o => ∃ bits, o = some bits ∧ bits (Fin.last _) = true)) ≤ (Kc : ℝ) * Q) ∧
          Pdec - ε ≤ ∑' I, (D I).toReal *
            (membershipOutputLaw (T (Mo.pub I)) (Mo.oracles I)
                (fun o => ∃ bits, o = some bits ∧ bits (Fin.last _) = true ∧
                  good I (bits ∘ Fin.castSucc)) /
              membershipOutputLaw (T (Mo.pub I)) (Mo.oracles I)
                (fun o => ∃ bits, o = some bits ∧ bits (Fin.last _) = true))) ∧
        (∃ (N c : ℕ) (Bt : Mo.Pub → AdaptiveMembershipProgram htcxGateSet
            (fun k => Mo.inW k + Mo.outW k) (fun _ => false) N c (M * bitsPerSymbol F)),
          (∀ I ∈ D.support,
            ((N + c + leafWorst (Bt (Mo.pub I)) (Mo.oracles I)
                (fun cnt => cnt 1 + cnt 2 + cnt 3 + cnt 4) : ℕ) : ℝ) ≤
              (Kc : ℝ) * (1 + (⌈Real.logb 2 (1 / ε)⌉₊ : ℝ)) * G ∧
            (leafWorst (Bt (Mo.pub I)) (Mo.oracles I) (fun cnt => cnt 0) : ℝ) ≤
              (Kc : ℝ) * (1 + (⌈Real.logb 2 (1 / ε)⌉₊ : ℝ)) * Q) ∧
          Pdec - ε ≤ ∑' I, (D I).toReal *
            membershipOutputLaw (Bt (Mo.pub I)) (Mo.oracles I)
              (fun o => ∃ bits, o = some bits ∧ good I bits)) := 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), §5.2, Theorem 5.28, p. 27

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