Theorem 10.1 — first imperfect-decoding bound
ProvedDQI.Imperfect.theorem_10_1Let define a max-XORSAT objective . Fix , real weights , and one deterministic decoder of syndromes . Let be its misidentified errors of weight , , , and . Prepare the postselected state (171), apply the binary Hadamard transform, normalize, and measure a binary string. If is uniform in , then the expected measured objective obeys
The bound quantifies the objective loss from imperfect decoding without assuming a minimum dual-code distance.
Formalization Note This is the first inequality of (172). The printed second inequality is false without a sign condition and is a separate companion item. The conditions and ensure that the shell normalizations and measured-state expectation have their intended meanings. The decoder is fixed independently of .
import Mathlib import Definitions.Def_DQI_Imperfect_Setting
namespace DQI.Imperfect
theorem theorem_10_1 (m n ℓ : ℕ) (hℓ : ℓ ≤ m)
(B : Matrix (Fin m) (Fin n) (ZMod 2)) (dec : (Fin n → ZMod 2) → (Fin m → ZMod 2)) (w : Fin (ℓ + 1) → ℝ)
(hN : 0 < (∑ k, (w k) ^ 2 * (1 - epsk B dec k.val))) :
((w ⬝ᵥ (DQI.Semicircle.Atri m ℓ 0).mulVec w) -
2 * epsMax B dec ℓ * ((m : ℝ) + 1) * (w ⬝ᵥ w)) /
(∑ k, (w k) ^ 2 * (1 - epsk B dec k.val)) ≤
avgV m (fun v => expObj B v (hadamard (PtD B v dec ℓ w))) := by sorry
end DQI.Imperfect
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.