Section III, p. 11 — over the 2^m instances, the variance of the expected satisfied count is at most ¼m(6D + 3)(D + 1)
ProvedQAOAE3Lin2.Typical.variance_boundaverage-casemax-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoavariance
Let the triples form an E3LIN2 family with equations in which every bit lies in at most equations, and let . Draw the right-hand sides uniformly from and let be the expected number of equations satisfied when is measured, a function of the instance. Then
With fixed, the standard deviation over instances is while the mean is of order ; this is what makes the average-case bound (50) typical.
Formalization Note The variance is over the instances (the 's), of the quantum expectation ; it is not the variance of the measurement outcome. and differ by the constant , so they have the same variance.
Preamble
import Mathlib import Definitions.Def_QAOAE3Lin2_Typical_Setting
Formal statement
namespace QAOAE3Lin2.Typical
/-- p. 11: the variance over the `2^m` instances of the expected number of satisfied equations of
`|−γ, π/4⟩` is at most `¼ m (6D + 3)(D + 1)`. -/
theorem variance_bound {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (D : ℕ)
(htri : QAOAE3Lin2.General.IsTripleFamily tri) (hocc : QAOAE3Lin2.General.BoundedOccurrence tri D) (γ : ℝ) :
varD (fun rhs => QAOAE3Lin2.General.expSat tri rhs (-γ) (Real.pi / 4)) ≤
(m : ℝ) * (6 * D + 3) * (D + 1) / 4 := by sorry
end QAOAE3Lin2.Typical
Source
Farhi, Goldstone, Gutmann, A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem, arXiv:1412.6062v2, p. 11, Section III, the paragraph after (57)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.