Theorem 5.28 — average-case CIP via Regev's reduction
OpenTwoFoldOPI.Supplement.theorem_5_28coding-theoryoptimal-polynomial-intersectionp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsregev-reductionschur-product-codes
Let be a linear code and let be a distribution on represented instances (public data plus fixed classical function oracles, with target set ) that is translation-invariant: has law for every fixed , where the translation action satisfies , , . Assume on the support, and write for the uniform state on . Assume, uniformly over the support:
- a coherent decoder solves with probability at least a known , using gates and oracle queries;
- for every a state -close to in trace distance can be prepared with gates and queries.
Fix and put . Then there is a quantum algorithm for with success probability at least ,
A bounded-time version has the same success guarantee and gate and query bounds larger by a factor .
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