Section II, (6) and p. 4 — the expected satisfied count is m/2 + Σᵢ ½dᵢ⟨Z_aZ_bZ_c⟩
ProvedQAOAE3Lin2.General.eq_6_summax-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoa
Let an instance of Max E3LIN2 with equations be given, with signs , and let be the level-one QAOA state. For all real , the expected number of satisfied equations when is measured is
where is the triple of equation .
This is the operator identity of (5)–(6) taken in expectation. It reduces the analysis to one clause at a time.
Formalization Note. No hypothesis on the instance is needed. The right side uses that the state is a unit vector.
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_General_Setting
Formal statement
namespace QAOAE3Lin2.General
theorem eq_6_sum {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (rhs : Fin m → Bool)
(γ β : ℝ) :
expSat tri rhs γ β = (m : ℝ) / 2 + ∑ i, (1 / 2) * sgn rhs i * corr 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, pp. 3–4, Section II, (5)–(6) and p. 4, after (7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.