Section III, (55), p. 11 — at β = π/4 the expected satisfied count of |−γ, π/4⟩ is m/2 + Σ ½ d_abc ⟨Z_aZ_bZ_c⟩
ProvedQAOAE3Lin2.Typical.eq_55Fix an instance of E3LIN2 with equations (any triples, any right-hand sides) and an angle . Measure the level-one QAOA state in the computational basis. The expected number of satisfied equations equals plus the sum, over the equations, of their clause terms:
Equivalently, the target (7) at , with as in (6), is the sum of the clause terms.
This identity reduces the analysis of the whole instance to one equation at a time; both the mean bound (50) and the variance bound of Section III start from it.
Formalization Note The left side is the expected number of satisfied equations; subtracting gives the paper's (7). The sum runs over the equations , which is the paper's sum over the triples with .
import Mathlib import Definitions.Def_QAOAE3Lin2_Typical_Setting
namespace QAOAE3Lin2.Typical
/-- (55), p. 11 (with (6) and p. 4): at `β = π/4` the expected number of satisfied equations of
`|−γ, π/4⟩` is `m/2` plus the sum over the equations of `½ d_abc ⟨Z_a Z_b Z_c⟩`. -/
theorem eq_55 {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (rhs : Fin m → Bool) (γ : ℝ) :
QAOAE3Lin2.General.expSat tri rhs (-γ) (Real.pi / 4) = (m : ℝ) / 2 + ∑ i, clauseTerm tri rhs i γ := by sorry
end QAOAE3Lin2.Typical
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.