Lemma 10.3 — average ideal objective matrix
ProvedDQI.Imperfect.lemma_10_3coding-theorydecoded-quantum-interferometrymax-xorsatp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
For any binary matrix and , choose uniformly. The ideal objective matrix from (147) has average
where is the tridiagonal matrix in (70), with adjacent entry and zero diagonal. This identifies the average ideal matrix without a distance condition.
Formalization Note Uniform expectation is the sum over all binary vectors divided by ; ensures the shell normalizations are defined.
Preamble
import Mathlib import Definitions.Def_DQI_Imperfect_Setting
Formal statement
namespace DQI.Imperfect
theorem lemma_10_3 (m n ℓ : ℕ) (hℓ : ℓ ≤ m)
(B : Matrix (Fin m) (Fin n) (ZMod 2)) :
((1 / ((2 : ℝ) ^ m)) •
(∑ v : Fin m → ZMod 2, Abar B v ℓ)) = DQI.Semicircle.Atri m ℓ 0 := by sorry
end DQI.Imperfect
Source
Jordan et al., Optimization by Decoded Quantum Interferometry, arXiv:2408.08292v5, p. 38, Lemma 10.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.