Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Section II, (25), p. 6 — at β = π/4 the clause term ½d₁₂₃⟨Z₁Z₂Z₃⟩ equals ⅛d₁₂₃E_z[Σ sin(γ(d₁₂₃ ± c₁ ± c₂ ± c₃))]

Proved
QAOAE3Lin2.Typical.eq_25

by mikedeng1 · Oct 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

max-e3lin2p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1qaoa

Let the triples form an E3LIN2 family (each triple has three distinct bits, no triple repeated), take any right-hand sides, an equation iii with bits 1,2,31,2,31,2,3 and sign d123d_{123}d123​, and an angle γ∈R\gamma\in\mathbb Rγ∈R. Let c1,c2,c3c_1,c_2,c_3c1​,c2​,c3​ be the polynomials (21) collecting the equations that share exactly one bit with equation iii. Then

12d123⟨−γ,π/4∣Z1Z2Z3∣−γ,π/4⟩=18d123 Ez[sin⁡(γ(d123+c1+c2+c3))+sin⁡(γ(d123+c1−c2−c3))+sin⁡(γ(d123−c1+c2−c3))+sin⁡(γ(d123−c1−c2+c3))].\tfrac12 d_{123}\langle-\gamma,\pi/4|Z_1Z_2Z_3|-\gamma,\pi/4\rangle=\tfrac18 d_{123}\,\mathbb E_z\big[\sin(\gamma(d_{123}+c_1+c_2+c_3))+\sin(\gamma(d_{123}+c_1-c_2-c_3))+\sin(\gamma(d_{123}-c_1+c_2-c_3))+\sin(\gamma(d_{123}-c_1-c_2+c_3))\big].21​d123​⟨−γ,π/4∣Z1​Z2​Z3​∣−γ,π/4⟩=81​d123​Ez​[sin(γ(d123​+c1​+c2​+c3​))+sin(γ(d123​+c1​−c2​−c3​))+sin(γ(d123​−c1​+c2​−c3​))+sin(γ(d123​−c1​−c2​+c3​))].

This is the exact single-clause formula at β=π/4\beta=\pi/4β=π/4. It expresses a quantum expectation as a classical average over bit strings, and it shows that the clause term depends only on d123d_{123}d123​ and on the signs of the equations sharing exactly one bit with equation iii; equations sharing two bits with it drop out.

Formalization Note The left side is the summand of (55), i.e. the paper's (8) with β=π/4\beta=\pi/4β=π/4 and the state ∣−γ,π/4⟩|-\gamma,\pi/4\rangle∣−γ,π/4⟩. Ez\mathbb E_zEz​ is the uniform average over all 2n2^n2n bit strings. The hypothesis that the triples are strictly increasing and pairwise distinct encodes "exactly 3 variables" and dabc∈{0,±1}d_{abc}\in\{0,\pm1\}dabc​∈{0,±1} of (6).

Preamble
import Mathlib
import Definitions.Def_QAOAE3Lin2_Typical_Setting
Formal statement
namespace QAOAE3Lin2.Typical

/-- (25), p. 6: at `β = π/4`, `½ d₁₂₃ ⟨−γ, π/4| Z₁Z₂Z₃ |−γ, π/4⟩` equals
`⅛ d₁₂₃ E_z[Σ sin(γ(d₁₂₃ ± c₁ ± c₂ ± c₃))]` over the four sign patterns. -/
theorem eq_25 {n m : ℕ} (tri : Fin m → Fin n × Fin n × Fin n) (htri : QAOAE3Lin2.General.IsTripleFamily tri)
    (rhs : Fin m → Bool) (i : Fin m) (γ : ℝ) :
    clauseTerm tri rhs i γ = QAOAE3Lin2.General.clauseSin tri rhs i γ := 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. 6, Section II, (25) (with (8), p. 4 and (19)–(21), p. 6)
Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me