Section III, (49), p. 10 — E_d of the clause term is ½(sin γ)(cos γ)^{D₁+D₂+D₃}, with D₁ + D₂ + D₃ ⩽ 3D
ProvedQAOAE3Lin2.Typical.eq_49average-casemax-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoa
Let the triples form an E3LIN2 family in which every bit lies in at most equations. Fix an equation and , and let be the numbers of terms of its polynomials (21). Averaging over the right-hand-side vectors,
and
Summed over the equations this gives the mean bound (50).
Formalization Note counts the equations that share exactly the role- bit with equation . The bound is automatic for natural numbers and is not restated.
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_Typical_Setting
Formal statement
namespace QAOAE3Lin2.Typical
/-- (49), p. 10: the average over the instances of the clause term of equation `i` is
`½ (sin γ)(cos γ)^{D₁+D₂+D₃}`, and `D₁ + D₂ + D₃ ≤ 3D`. -/
theorem eq_49 {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (D : ℕ) (htri : QAOAE3Lin2.General.IsTripleFamily tri)
(hocc : QAOAE3Lin2.General.BoundedOccurrence tri D) (i : Fin m) (γ : ℝ) :
avgD (fun rhs => clauseTerm tri rhs i γ) =
(1 / 2) * Real.sin γ *
Real.cos γ ^ (QAOAE3Lin2.General.termCount tri i 0 + QAOAE3Lin2.General.termCount tri i 1 + QAOAE3Lin2.General.termCount tri i 2) ∧
QAOAE3Lin2.General.termCount tri i 0 + QAOAE3Lin2.General.termCount tri i 1 + QAOAE3Lin2.General.termCount tri i 2 ≤ 3 * D := by sorry
end QAOAE3Lin2.Typical
Source
Farhi, Goldstone, Gutmann, A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem, arXiv:1412.6062v2, p. 10, Section III, (49)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.