Section II, (26)–(28), p. 6 — Taylor remainder |R^k| ≤ ⅛(|γ|^{k+2}/(k+2)!)E_z[Σ|d ± c₁ ± c₂ ± c₃|^{k+2}] for odd k
ProvedQAOAE3Lin2.General.eq_28max-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoataylor-expansion
Fix a Max E3LIN2 instance, an equation with sign and polynomials , and an odd . Expand (25) as
with as in (27). Then for every real the remainder satisfies
This isolates the linear term of each clause and bounds what is left after the polynomial part.
Formalization Note. is defined by (26) as (25) minus minus , so the statement is the remainder bound (28). is odd, as in (27)'s sum .
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_General_Setting
Formal statement
namespace QAOAE3Lin2.General
theorem eq_28 {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (rhs : Fin m → Bool)
(i : Fin m) (k : ℕ) (hk : Odd k) (γ : ℝ) :
|Rk tri rhs i k γ| ≤ (1 / 8) * |γ| ^ (k + 2) / ((k + 2).factorial : ℝ) *
avgZ (fun x =>
let d := sgn rhs i
let c₁ := cPoly tri rhs i 0 x
let c₂ := cPoly tri rhs i 1 x
let c₃ := cPoly tri rhs i 2 x
|d + c₁ + c₂ + c₃| ^ (k + 2) + |d + c₁ - c₂ - c₃| ^ (k + 2) +
|d - c₁ + c₂ - c₃| ^ (k + 2) + |d - c₁ - c₂ + c₃| ^ (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. 6, Section II, (26)–(28)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.