Section II, (31), p. 7 — E_z[c_i²] = Σ d_iab d_iab ≤ D
ProvedQAOAE3Lin2.General.eq_31bounded-occurrencemax-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoa
Let an instance of Max E3LIN2 have every equation on three distinct bits, no triple carrying two equations, and every bit in at most equations. Fix an equation and one of its bits, and let be the corresponding polynomial (21) with terms. Then
The terms of are products of distinct pairs, hence orthonormal, and the shared bit lies in at most equations besides the central one.
Formalization Note. The sum is the number of terms of , written as a count. Both conclusions, the identity and the bound, are stated.
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_General_Setting
Formal statement
namespace QAOAE3Lin2.General
theorem eq_31 {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) (r : Fin 3) :
avgZ (fun x => cPoly tri rhs i r x ^ 2) = (termCount tri i r : ℝ) ∧
termCount tri i r ≤ 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, (31)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.