Section II, (40)–(41), p. 8 — max_r |(m/2)γ_r + P^k(γ_r)| ≥ m/(20D^{1/2}k), γ_r = cos(πr/k)/(10D^{1/2})
ProvedQAOAE3Lin2.General.eq_41chebyshevmax-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoa
Let a Max E3LIN2 instance with equations be given, let , let be odd, and let
Then
where is the sum of the polynomials (27).
This is the Chebyshev-node bound (39) applied to the main term of (37), on a grid of angles in .
Formalization Note. The maximum is stated as the existence of a grid index . is added so that . No condition on the triples is needed: is a polynomial in with only odd powers for every instance.
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_General_Setting
Formal statement
namespace QAOAE3Lin2.General
theorem eq_41 {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (rhs : Fin m → Bool) (D : ℕ)
(hD : 1 ≤ D) (k : ℕ) (hk : Odd k) :
∃ r ∈ Finset.range (k + 1), (m : ℝ) / (20 * Real.sqrt D * k) ≤
|(m : ℝ) / 2 * gammaGrid D k r + PkSum tri rhs k (gammaGrid D k r)| := 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. 8, Section II, (40)–(41)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.