Lemma 10.6 — average matrix with decoding failures
ProvedDQI.Imperfect.lemma_10_6coding-theorydecoded-quantum-interferometrymax-xorsatp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
For a binary matrix , a fixed deterministic syndrome decoder, and , average the imperfect-decoder objective matrix over uniform . Then
Here the entry of counts, for each coordinate , the pairs in with , divided by . The matrix records the effect of misidentified errors on the averaged observable.
Formalization Note The same decoder is used at every ; the uniform average is over all phase vectors.
Preamble
import Mathlib import Definitions.Def_DQI_Imperfect_Setting
Formal statement
namespace DQI.Imperfect
theorem lemma_10_6 (m n ℓ : ℕ) (hℓ : ℓ ≤ m)
(B : Matrix (Fin m) (Fin n) (ZMod 2)) (dec : (Fin n → ZMod 2) → (Fin m → ZMod 2)) :
((1 / ((2 : ℝ) ^ m)) •
(∑ v : Fin m → ZMod 2, AbarD B v dec ℓ)) =
DQI.Semicircle.Atri m ℓ 0 - Emat B dec ℓ := by sorry
end DQI.Imperfect
Source
Jordan et al., Optimization by Decoded Quantum Interferometry, arXiv:2408.08292v5, p. 41, Lemma 10.6, (180)–(182)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.