p. 11 — each clause term of (55) is at most in absolute value
ProvedQAOAE3Lin2.Typical.clauseTerm_abs_leConsider an E3LIN2 instance on bits with equations: equation is on the triple of bits, and is its sign. Let be the level-one QAOA state for this instance at phase angle and mixer angle , and let
be the clause term of equation , the summand of (55). Then for every instance, every equation and every real ,
The reason is that has eigenvalues and the QAOA state is a unit vector, so the expectation lies in . This bound is what turns the count of correlated pairs of equations on p. 11 into the variance bound : each covariance of two clause terms is at most .
Formalization Note The expectation is written as the sum over basis strings of the measurement probability of times the product of the three spins , which is exact because the 's are diagonal. No hypothesis on the triples is needed.
import Mathlib import Definitions.Def_QAOAE3Lin2_Typical_Setting
namespace QAOAE3Lin2.Typical
/-- p. 11 (the variance paragraph after (57)): the clause term of equation `i`,
`½ d_abc ⟨−γ, π/4| Z_a Z_b Z_c |−γ, π/4⟩`, has absolute value at most `½`, because `d_abc = ±1`
and the expectation of the `±1`-valued observable `Z_a Z_b Z_c` in a unit vector lies in
`[−1, 1]`. -/
theorem clauseTerm_abs_le {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (rhs : Fin m → Bool)
(i : Fin m) (γ : ℝ) :
|clauseTerm tri rhs i γ| ≤ 1 / 2 := by sorry
end QAOAE3Lin2.Typical