Lemma 10.4 — norm of the postselected state
ProvedDQI.Imperfect.lemma_10_4coding-theorydecoded-quantum-interferometrymax-xorsatp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
Let , let , and let be a deterministic syndrome decoder. For weights with , let be the unnormalized postselected syndrome state and . Then
This identity gives the normalization and postselection probability used by the main bound.
Formalization Note The condition ensures that every binomial denominator is positive.
Preamble
import Mathlib import Definitions.Def_DQI_Imperfect_Setting
Formal statement
namespace DQI.Imperfect
theorem lemma_10_4 (m n ℓ : ℕ) (hℓ : ℓ ≤ m)
(B : Matrix (Fin m) (Fin n) (ZMod 2)) (v : Fin m → ZMod 2) (dec : (Fin n → ZMod 2) → (Fin m → ZMod 2)) (w : Fin (ℓ + 1) → ℝ) :
(∑ s, (PtD B v dec ℓ w s) ^ 2) =
(∑ k, (w k) ^ 2 * (1 - epsk B dec k.val)) ∧
(∑ k, (w k) ^ 2 * (1 - epsk B dec k.val)) ≤ w ⬝ᵥ w := by sorry
end DQI.Imperfect
Source
Jordan et al., Optimization by Decoded Quantum Interferometry, arXiv:2408.08292v5, p. 40, Lemma 10.4, (174)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.