Section III, p. 11, closing sentence (pinned Chebyshev form with (50)'s bound) — the fraction of instances below m/2 + (m/2) sin γ cos^{3D} γ − t is ⩽ m(6D+3)(D+1)/(4t²)
ProvedQAOAE3Lin2.Typical.typical_concentrationFix any collection of triples forming an E3LIN2 family (three distinct bits per triple, no triple repeated) in which every bit lies in at most triples. Fix with and . Choose the right-hand sides of the equations uniformly at random among the possibilities, run the level-one QAOA with angles , and let be the expected number of satisfied equations of the measured string. Then
With fixed and , the right side is the constant : for large , on a typical instance, the QAOA satisfies in expectation at least minus a term of order equations. At this threshold is .
Formalization Note The paper's sentence ("with high probability … at least (54) minus a term of order ") has no explicit failure probability. It is pinned here by combining the paper's own mean bound (50) and its variance bound through Chebyshev's inequality, which the page invokes implicitly. The threshold uses (50)'s exact lower bound rather than (54), because (54) is false as a finite- inequality ( for every ). The range is added because (50)'s lower bound needs ; the paper's choice lies in it. The probability is over the right-hand sides only; is the quantum expectation, not a single measurement outcome.
import Mathlib import Definitions.Def_QAOAE3Lin2_Typical_Setting
namespace QAOAE3Lin2.Typical
/-- §III, p. 11, closing sentence, pinned by Chebyshev's inequality from (50) and the variance
bound: for fixed triples with every bit in at most `D + 1` equations and `γ ∈ [0, π/2]`, the
fraction of the `2^m` right-hand-side choices on which the expected satisfied count of
`|−γ, π/4⟩` is at most `m/2 + (m/2) sin γ cos^{3D} γ − t` is at most `m(6D + 3)(D + 1)/(4t²)`. -/
theorem typical_concentration {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (D : ℕ)
(htri : QAOAE3Lin2.General.IsTripleFamily tri) (hocc : QAOAE3Lin2.General.BoundedOccurrence tri D) (γ : ℝ) (hγ₀ : 0 ≤ γ)
(hγ₁ : γ ≤ Real.pi / 2) (t : ℝ) (ht : 0 < t) :
((Finset.univ.filter fun rhs : Fin m → Bool =>
QAOAE3Lin2.General.expSat tri rhs (-γ) (Real.pi / 4) ≤
(m : ℝ) / 2 + (m : ℝ) / 2 * Real.sin γ * Real.cos γ ^ (3 * D) - t).card : ℝ) / 2 ^ m ≤
(m : ℝ) * (6 * D + 3) * (D + 1) / (4 * t ^ 2) := by sorry
end QAOAE3Lin2.Typical
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.