Section II, (42)–(43), p. 8 — for large D, some odd k ∈ [5 ln D, 5 ln D + 2] gives 1/(20D^{1/2}k) − (9/10)^{k+2} > 1/(101D^{1/2} ln D)
ProvedQAOAE3Lin2.General.eq_43asymptoticsmax-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoa
There is a threshold such that for every natural number there is an odd integer with and
This is the right-hand side of (42), divided by , compared with (43). It fixes how many grid angles are needed.
Formalization Note. "For large " is the existential threshold ; it is very large (the inequality first holds near ), so it is not named. The page's "" is pinned as an odd in , because (39) needs odd and is not an integer.
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_General_Setting
Formal statement
namespace QAOAE3Lin2.General
theorem eq_43 :
∃ D₀ : ℕ, ∀ D : ℕ, D₀ ≤ D → ∃ k : ℕ, Odd k ∧ 5 * Real.log D ≤ k ∧
(k : ℝ) ≤ 5 * Real.log D + 2 ∧
1 / (101 * Real.sqrt D * Real.log D) < 1 / (20 * Real.sqrt D * k) - (9 / 10 : ℝ) ^ (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. 8, Section II, (42)–(43)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.