Section II, (25), p. 6 — at β = π/4 the clause term ½d⟨Z₁Z₂Z₃⟩ at −γ equals ⅛dE_z[Σ sin(γ(d ± c₁ ± c₂ ± c₃))]
ProvedQAOAE3Lin2.General.eq_25max-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoa
Let an instance of Max E3LIN2 be given in which every equation is on three distinct bits and no triple carries two equations. Fix an equation with sign and bits , and let be its polynomials (21). Then for every real ,
This exact single-clause formula is the starting point of both the worst-case analysis (Taylor expansion in ) and the typical-case analysis.
Formalization Note. The left side is the paper's (8) at , i.e. , the state at angle . The triple condition is needed: a second equation on the same triple would change the commutation step (11).
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_General_Setting
Formal statement
namespace QAOAE3Lin2.General
theorem eq_25 {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (rhs : Fin m → Bool)
(htri : IsTripleFamily tri) (i : Fin m) (γ : ℝ) :
(1 / 2) * sgn rhs i * corr tri rhs i (-γ) (Real.pi / 4) = clauseSin tri rhs i γ := 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. 6, Section II, (25) (with (8), p. 4, and (21), p. 6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.