Lemma 1 — on a star with nonnegative weights, every unit state has energy at most max_e w_e + Σ_e w_e
ProvedQMaxCutBeyond.TwoQubit.lemma_1monogamyp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-max-cutstar-graph
Let be a star graph with nonnegative weights and the quantum Max Cut Hamiltonian. Then
The trivial bound is ; the lemma says the centre qubit cannot be maximally entangled with all leaves at once (monogamy of entanglement). Applied to the star of each vertex it gives the upper bound on used in Theorems 3 and 5.
Formalization Note Stated as: every unit state has . Since , this is equivalent to the norm bound. A star is a graph all of whose edges contain a centre ; other vertices may be isolated (their qubits are idle), which is the situation in which the lemma is applied.
Preamble
import Mathlib import Definitions.Def_QMaxCutBeyond_TwoQubit_Setting
Formal statement
namespace QMaxCutBeyond.TwoQubit
/-- Lemma 1, p. 6: for a star graph with nonnegative weights, `‖H_G‖ ≤ max_{e∈E} w_e +
Σ_{e∈E} w_e`, stated as: every unit state has energy at most that bound. -/
theorem lemma_1 {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
(w : Sym2 (Fin n) → ℝ) (hw : ∀ e, 0 ≤ w e) (c : Fin n) (hstar : IsStar G c)
(ψ : Config n → ℂ) (hψ : IsUnitState ψ) :
energy (hamiltonian G w) ψ ≤ maxEdgeWeight G w + totalWeight G w := by sorry
end QMaxCutBeyond.TwoQubit
Source
Anshu, Gosset & Morenz, Beyond product state approximations for a quantum analogue of Max Cut, arXiv:2003.14394v1, p. 6, Lemma 1, eq. (9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.