Lemma 10.5 — objective matrix after imperfect decoding
ProvedDQI.Imperfect.lemma_10_5coding-theorydecoded-quantum-interferometrymax-xorsatp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
Let be the weight- errors correctly recovered by a deterministic decoder of . For the normalized Hadamard transform of the postselected state , the expected max-XORSAT objective is
The entry of is the sum of over and with , divided by . This is the objective matrix for the retained, correctly decoded errors.
Formalization Note The hypothesis that the transformed state has squared norm one states the paper's normalization condition. The formalization assumes .
Preamble
import Mathlib import Definitions.Def_DQI_Imperfect_Setting
Formal statement
namespace DQI.Imperfect
theorem lemma_10_5 (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) → ℝ)
(hnorm : (∑ x, (hadamard (PtD B v dec ℓ w) x) ^ 2) = 1) :
expObj B v (hadamard (PtD B v dec ℓ w)) =
w ⬝ᵥ (AbarD B v dec ℓ).mulVec w := by sorry
end DQI.Imperfect
Source
Jordan et al., Optimization by Decoded Quantum Interferometry, arXiv:2408.08292v5, pp. 40–41, Lemma 10.5, (176)–(178)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.