Section II, p. 4 — (7) is an odd function of γ
ProvedQAOAE3Lin2.General.eq_7_oddmax-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoa
For every Max E3LIN2 instance with equations and all real , let be the expected number of satisfied equations of the measured state . Then
Since the quantity (7) at is , this says exactly that (7) is an odd function of . It is what turns a lower bound on into a lower bound on (7) itself, by replacing with .
Formalization Note. The identity holds for every , as the paper's sentence asserts without restriction on .
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_General_Setting
Formal statement
namespace QAOAE3Lin2.General
theorem eq_7_odd {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (rhs : Fin m → Bool)
(γ β : ℝ) :
expSat tri rhs (-γ) β = (m : ℝ) - expSat tri rhs γ β := 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. 4, Section II, after (7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.