Weighted form of Eqs. (18)–(19) — OPT(G) ≤ W/2 + 3λ^Z_max(G), attained-by-a-basis-state lower bound W/2 + λ^Z_max(G)
ProvedQMaxCutBeyond.TwoQubit.weighted_eq_18_19basis-statep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1product-statequantum-max-cut
Let have nonnegative weights, , and its largest eigenvalue. There is a computational basis state such that
- attains : for every unit ;
- (eq. (18)) every unit state satisfies
- (eq. (19)) , so the best product state has energy at least .
Combining (18) and (19) yields a basis state of energy at least , the first ingredient of eq. (24).
Formalization Note The paper writes (17)–(19) for unit weights ( in place of ) and the proof of Theorem 3 reuses them weighted; this item is that weighted form. is not defined: (19) is stated through its basis-state witness , which is a product state.
Preamble
import Mathlib import Definitions.Def_QMaxCutBeyond_TwoQubit_Setting
Formal statement
namespace QMaxCutBeyond.TwoQubit
/-- Weighted form of Eqs. (18)–(19), p. 8: there is a computational basis state `|z⟩` attaining
`λ^Z_max(G)` (the largest energy of `H_Z(G)`), every unit state satisfies
`⟨ψ|H_G|ψ⟩ ≤ W/2 + 3 λ^Z_max(G)` (18), and `⟨z|H_G|z⟩ = W/2 + λ^Z_max(G)` (the basis-state
witness of (19)). -/
theorem weighted_eq_18_19 {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
(w : Sym2 (Fin n) → ℝ) (hw : ∀ e, 0 ≤ w e) :
∃ z : Config n,
(∀ ψ : Config n → ℂ, IsUnitState ψ →
energy (hamZ G w) ψ ≤ energy (hamZ G w) (basisState z)) ∧
(∀ ψ : Config n → ℂ, IsUnitState ψ →
energy (hamiltonian G w) ψ ≤ totalWeight G w / 2 + 3 * energy (hamZ G w) (basisState z)) ∧
energy (hamiltonian G w) (basisState z) =
totalWeight G w / 2 + energy (hamZ G w) (basisState z) := by sorry
end QMaxCutBeyond.TwoQubit
Source
Anshu, Gosset & Morenz, Beyond product state approximations for a quantum analogue of Max Cut, arXiv:2003.14394v1, p. 8, eqs. (17)–(19), proof of Theorem 5 (weighted form, as used in the proof of Theorem 3, p. 9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.