Proof of Lemma 12, p. 14 — if y* = (y, z, h) ∈ Δ^{m+2} has A‴y* ≤ 2ε‴, then |h − 1/2| ≤ ε‴
ProvedQZeroSum19.LPReduce.h_near_halflinear-programminglp-reductionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1zero-sum-game
Let be the game matrix (6) (second row ) for arbitrary data , and let . If satisfies entrywise, then
In the proof of Lemma 12 this is applied with : an approximately optimal strategy of the game (6) puts weight close to on the homogenizing variable .
Formalization Note is the column inr 1 of Fin m ⊕ Fin 2. Only the first two rows of (6) enter.
Preamble
import Mathlib import Definitions.Def_QZeroSum19_LPReduce_Setting open Matrix
Formal statement
namespace QZeroSum19.LPReduce
theorem h_near_half {n m : ℕ} (A : Matrix (Fin n) (Fin m) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(α R κ : ℝ) (y' : Fin m ⊕ Fin 2 → ℝ) (hy' : y' ∈ stdSimplex ℝ (Fin m ⊕ Fin 2))
(hle : ∀ k, (gameMatrix A b c α R *ᵥ y') k ≤ 2 * κ) :
|y' (Sum.inr 1) - 1 / 2| ≤ κ := by sorry
end QZeroSum19.LPReduce
Source
van Apeldoorn and Gilyén, Quantum algorithms for zero-sum games, arXiv:1904.03180v1, p. 14, proof of Lemma 12, second case ("This implies that |h − 1/2| ≤ ε‴")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.