Section III, (50), p. 10 — for γ ∈ [0, π/2], (m/2) sin γ cos^{3D} γ ⩽ E_d⟨−γ, π/4|C|−γ, π/4⟩ ⩽ (m/2) sin γ
ProvedQAOAE3Lin2.Typical.eq_50average-casemax-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoa
Let the triples form an E3LIN2 family with equations in which every bit lies in at most equations, and let . Draw the right-hand sides uniformly from and measure . Then the average over the instances of the expected number of satisfied equations, minus , satisfies
This is the mean performance of the level-one QAOA on a random-sign instance with fixed triples. Combined with the variance bound it yields the concentration statement of Section III.
Formalization Note is the expected satisfied count minus (p. 4). The range is added: the page leaves unspecified at this point, but the lower bound needs and , and the paper's choice lies in this range.
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_Typical_Setting
Formal statement
namespace QAOAE3Lin2.Typical
/-- (50), p. 10: for `γ ∈ [0, π/2]`, the average over the `2^m` instances of
`⟨−γ, π/4|C|−γ, π/4⟩` (the expected satisfied count minus `m/2`) lies between
`(m/2) sin γ cos^{3D} γ` and `(m/2) sin γ`. -/
theorem eq_50 {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (D : ℕ) (htri : QAOAE3Lin2.General.IsTripleFamily tri)
(hocc : QAOAE3Lin2.General.BoundedOccurrence tri D) (γ : ℝ) (hγ₀ : 0 ≤ γ) (hγ₁ : γ ≤ Real.pi / 2) :
(m : ℝ) / 2 * Real.sin γ * Real.cos γ ^ (3 * D) ≤
avgD (fun rhs => QAOAE3Lin2.General.expSat tri rhs (-γ) (Real.pi / 4) - (m : ℝ) / 2) ∧
avgD (fun rhs => QAOAE3Lin2.General.expSat tri rhs (-γ) (Real.pi / 4) - (m : ℝ) / 2) ≤
(m : ℝ) / 2 * Real.sin γ := 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, (50)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.