Lemma 10.2 — objective matrix of the ideal state
ProvedDQI.Imperfect.lemma_10_2coding-theorydecoded-quantum-interferometrymax-xorsatp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
For the binary max-XORSAT instance , take the Hadamard transform of the ideal syndrome state in (140), with weights . If the resulting state is normalized, its measured objective expectation is
where is the symmetric matrix of (147): its entry sums over the pairs , for which , divided by . This expresses the observable in the weight basis, including collisions of syndrome values.
Formalization Note The normalized-state hypothesis is the equality of the transformed state's squared norm to one; keeps its shell denominators nonzero.
Preamble
import Mathlib import Definitions.Def_DQI_Imperfect_Setting
Formal statement
namespace DQI.Imperfect
theorem lemma_10_2 (m n ℓ : ℕ) (hℓ : ℓ ≤ m)
(B : Matrix (Fin m) (Fin n) (ZMod 2)) (v : Fin m → ZMod 2) (w : Fin (ℓ + 1) → ℝ)
(hnorm : (∑ x, (hadamard (Pt B v ℓ w) x) ^ 2) = 1) :
expObj B v (hadamard (Pt B v ℓ w)) =
w ⬝ᵥ (Abar B v ℓ).mulVec w := by sorry
end DQI.Imperfect
Source
Jordan et al., Optimization by Decoded Quantum Interferometry, arXiv:2408.08292v5, p. 36, Lemma 10.2, (146)–(148)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.