Corollary 8 — and
ProvedQMCTriFree.Circuit.corollary_8lasserremonogamyp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-max-cut
Let be feasible for with edge values , fix an edge and . Then
- ;
- ,
where ranges over the neighbours of and over the neighbours other than .
These are the neighbour-product bounds that turn Lemma 12 into Lemma 18 once .
Formalization Note Only the -part is stated. Part 2 holds as printed, without a sign condition on . is Real.sqrt, which is on negative arguments.
Preamble
import Mathlib import Definitions.Def_QMCTriFree_Circuit_Lasserre set_option autoImplicit false open QMCProduct.HalfApprox Matrix MeasureTheory ProbabilityTheory
Formal statement
namespace QMCTriFree.Circuit
/-- King, arXiv:2209.02589v3, p. 8, Corollary 8 (the `x` part): for a feasible `M`, an edge
`(i, j)` and `β ∈ [0, 1]`,
(1) `∏_{k∼i : x_ik ≥ 0} √(1 − β² x_ik²) ≥ √(1 − β²)`, and
(2) `∏_{j≠k∼i : x_ik ≥ 0} √(1 − β² x_ik²) ≥ √(1 − β² (1 − x_ij)²)`. -/
theorem corollary_8 {n : ℕ} (w : Fin n → Fin n → ℝ) (hw : IsWeightedGraph w)
(M : Matrix (P2 n) (P2 n) ℝ) (hM : IsFeasible M) (i j : Fin n) (hij : i ≠ j)
(hwij : w i j ≠ 0) (β : ℝ) (hβ0 : 0 ≤ β) (hβ1 : β ≤ 1) :
Real.sqrt (1 - β ^ 2) ≤
∏ k ∈ (nbrs w i).filter (fun k => 0 ≤ xval M i k),
Real.sqrt (1 - β ^ 2 * xval M i k ^ 2) ∧
Real.sqrt (1 - β ^ 2 * (1 - xval M i j) ^ 2) ≤
∏ k ∈ ((nbrs w i).erase j).filter (fun k => 0 ≤ xval M i k),
Real.sqrt (1 - β ^ 2 * xval M i k ^ 2) := by sorry
end QMCTriFree.Circuit
Source
King, An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs, arXiv:2209.02589v3, p. 8, Corollary 8 (proof p. 27)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.