Section III, (47), p. 9 — averaging over d₁₂₃ alone, the clause term becomes ½(sin γ)E_z[cos(γc₁)cos(γc₂)cos(γc₃)]
ProvedQAOAE3Lin2.Typical.eq_47Let the triples form an E3LIN2 family, fix right-hand sides for all equations, an equation (with bits ) and . Average the clause term over the two choices of the right-hand side of equation alone, keeping all other right-hand sides fixed. The result is
where are the polynomials (21) of equation , which do not involve .
In the paper's terms, the average of (24) over vanishes and (23) becomes (47). This is the first step of the average-case computation.
Formalization Note The average over is written as the mean of the clause term at the instance with right-hand side and at the instance with right-hand side for equation . The polynomials on the right are evaluated at the given right-hand sides; they do not depend on the right-hand side of equation .
import Mathlib import Definitions.Def_QAOAE3Lin2_Typical_Setting
namespace QAOAE3Lin2.Typical
/-- (47), p. 9: averaging the clause term of equation `i` over its own sign `d₁₂₃` alone gives
`½ (sin γ) E_z[cos(γc₁) cos(γc₂) cos(γc₃)]` (the `c`'s do not involve `d₁₂₃`). -/
theorem eq_47 {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (htri : QAOAE3Lin2.General.IsTripleFamily tri)
(rhs : Fin m → Bool) (i : Fin m) (γ : ℝ) :
(clauseTerm tri (Function.update rhs i false) i γ +
clauseTerm tri (Function.update rhs i true) i γ) / 2 =
(1 / 2) * Real.sin γ * QAOAE3Lin2.General.avgZ (fun x => Real.cos (γ * QAOAE3Lin2.General.cPoly tri rhs i 0 x) *
Real.cos (γ * QAOAE3Lin2.General.cPoly tri rhs i 1 x) * Real.cos (γ * QAOAE3Lin2.General.cPoly tri rhs i 2 x)) := by sorry
end QAOAE3Lin2.Typical
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.