Section III, (57), p. 11 — clause terms whose (25) expressions share no d are uncorrelated over the d's
ProvedQAOAE3Lin2.Typical.eq_57average-casemax-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoa
Let the triples form an E3LIN2 family and let . For an equation , call its dependency set the equation itself together with all equations sharing exactly one bit with it: these are the 's that appear in (25) for . If the dependency sets of two equations and are disjoint, then, averaging over uniformly random right-hand sides,
Only pairs of linked equations therefore contribute to the variance of (55).
Formalization Note The paper's (57) is written for without the factor of (55); both sides of the identity scale by , so the statement is the same. The dependency set contains the equation itself, so two terms sharing their own are never declared unlinked.
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_Typical_Setting
Formal statement
namespace QAOAE3Lin2.Typical
/-- (57), p. 11: if no sign `d` appearing in (25) for equation `i` appears in (25) for equation
`i'`, the two clause terms are uncorrelated over the instances. -/
theorem eq_57 {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (htri : QAOAE3Lin2.General.IsTripleFamily tri)
(i i' : Fin m) (hdis : Disjoint (deps tri i) (deps tri i')) (γ : ℝ) :
avgD (fun rhs => clauseTerm tri rhs i γ * clauseTerm tri rhs i' γ) =
avgD (fun rhs => clauseTerm tri rhs i γ) *
avgD (fun rhs => clauseTerm tri rhs i' γ) := 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. 11, Section III, (56)–(57)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.