Section II, (30)–(32), p. 7 — E_z[(d ± c₁ ± c₂ ± c₃)²] ≤ 1 + 9D
ProvedQAOAE3Lin2.General.eq_32bounded-occurrencemax-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoa
Under the hypotheses of (31), fix an equation with sign and polynomials . For every choice of signs ,
Together with hypercontractivity (29) this bounds every moment of the four clause arguments of (25).
Formalization Note. The paper's are independent, and all eight sign choices are covered. Lean's roles are the paper's .
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_General_Setting
Formal statement
namespace QAOAE3Lin2.General
theorem eq_32 {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (rhs : Fin m → Bool) (D : ℕ)
(htri : IsTripleFamily tri) (hocc : BoundedOccurrence tri D) (i : Fin m)
(ε : Fin 3 → ℝ) (hε : ∀ r, ε r = 1 ∨ ε r = -1) :
avgZ (fun x => (sgn rhs i + ε 0 * cPoly tri rhs i 0 x + ε 1 * cPoly tri rhs i 1 x +
ε 2 * cPoly tri rhs i 2 x) ^ 2) ≤ 1 + 9 * (D : ℝ) := by sorry
end QAOAE3Lin2.General
Source
Farhi, Goldstone, Gutmann, A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem, arXiv:1412.6062v2, p. 7, Section II, (30)–(32)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.