Weighted form of Eq. (15) — OPT(G) ≤ W + ½ Σ_v max_{e∼v} w_e
ProvedQMaxCutBeyond.TwoQubit.weighted_eq_15p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-max-cutupper-bound
Let be a graph with nonnegative weights and . Then
where is the largest weight of an edge incident to ( if is isolated).
This is the weighted replacement of eq. (15) in the proof of Theorem 3; it is the upper bound on the optimum against which all candidate states are compared.
Formalization Note Stated as: every unit state has energy at most the right-hand side. The paper derives it by "exactly the same arguments" as eqs. (14)–(15), written there for unit weights; this item is that weighted form.
Preamble
import Mathlib import Definitions.Def_QMaxCutBeyond_TwoQubit_Setting
Formal statement
namespace QMaxCutBeyond.TwoQubit
/-- Weighted form of Eq. (15), proof of Theorem 3, p. 9:
`OPT(G) ≤ W + ½ Σ_{v∈V} max_{e∼v} w_e`, stated for every unit state. -/
theorem weighted_eq_15 {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
(w : Sym2 (Fin n) → ℝ) (hw : ∀ e, 0 ≤ w e)
(ψ : Config n → ℂ) (hψ : IsUnitState ψ) :
energy (hamiltonian G w) ψ ≤ totalWeight G w + (1 / 2) * ∑ v, maxIncident G w v := by sorry
end QMaxCutBeyond.TwoQubit
Source
Anshu, Gosset & Morenz, Beyond product state approximations for a quantum analogue of Max Cut, arXiv:2003.14394v1, proof of Theorem 3, p. 9 (weighted Eq. (15)); W defined on p. 10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.