Section II, (33)–(34), p. 7 — |R^k(γ)| ≤ (9D^{1/2}|γ|)^{k+2} for odd k and D ≥ 1
ProvedQAOAE3Lin2.General.eq_34bounded-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, with . Let be odd. For every equation and every real , the remainder of (26) satisfies
It is the uniform, instance-free remainder bound: for each clause contributes at most .
Formalization Note. is added. The page's last step uses , which holds for and fails at . The page's justification "" does not give this step on its own, since ; the stated inequality is still true for .
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_General_Setting
Formal statement
namespace QAOAE3Lin2.General
theorem eq_34 {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (rhs : Fin m → Bool) (D : ℕ)
(htri : IsTripleFamily tri) (hocc : BoundedOccurrence tri D) (hD : 1 ≤ D)
(k : ℕ) (hk : Odd k) (i : Fin m) (γ : ℝ) :
|Rk tri rhs i k γ| ≤ (9 * Real.sqrt D * |γ|) ^ (k + 2) := 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, (33)–(34)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.