Section II, (35)–(37), pp. 7–8 — |⟨−γ,π/4|C|−γ,π/4⟩| ≥ |(m/2)γ + P^k(γ)| − m(9D^{1/2}|γ|)^{k+2}
ProvedQAOAE3Lin2.General.eq_37max-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoa
Let an instance of Max E3LIN2 with equations have every equation on three distinct bits, no triple carrying two equations, and every bit in at most equations, with . Let be odd and real. Then
where and is the sum of the polynomials (27).
This separates the quantity (7) into a polynomial main term and an error controlled by (34).
Formalization Note. is written as the expected satisfied count at minus . is inherited from (34).
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_General_Setting
Formal statement
namespace QAOAE3Lin2.General
theorem eq_37 {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) (γ : ℝ) :
|(m : ℝ) / 2 * γ + PkSum tri rhs k γ| - (m : ℝ) * (9 * Real.sqrt D * |γ|) ^ (k + 2) ≤
|expSat tri rhs (-γ) (Real.pi / 4) - (m : ℝ) / 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, pp. 7–8, Section II, (35)–(37)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.