Proof of Lemma 1, p. 4 — Φ(t+1) = Φ(t)(Σ_j p_j e^{−ηA_bj})(Σ_i q_i e^{ηA_ia})
ProvedQZeroSum19.GK.potential_updategibbs-distributiongrigoriadis-khachiyanp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-function
For a matrix and vectors , write
with the Gibbs distribution. For every step and moves , , the potential after the update , is
This identity expresses one iteration of Algorithm 1 as a multiplicative change of the potential, which is what the expectation bound of the next step controls.
Preamble
import Mathlib import Definitions.Def_QZeroSum19_GK_Setting open Matrix
Formal statement
namespace QZeroSum19.GK
/-- Proof of Lemma 1, p. 4, the `Φ(t + 1)` display: after the update `x ↦ x + η e_b`,
`y ↦ y + η e_a`,
`Φ' = Φ · (Σ_j p_j e^{−η A_bj}) · (Σ_i q_i e^{η A_ia})` with `p = G(−Aᵀx)`, `q = G(Ay)`. -/
theorem potential_update {n m : ℕ} (A : Matrix (Fin n) (Fin m) ℝ) (x : Fin n → ℝ)
(y : Fin m → ℝ) (η : ℝ) (a : Fin m) (b : Fin n) :
potential A (x + η • Pi.single b 1) (y + η • Pi.single a 1) =
potential A x y * (∑ j, gibbs (-(Aᵀ *ᵥ x)) j * Real.exp (-η * A b j)) *
(∑ i, gibbs (A *ᵥ y) i * Real.exp (η * A i a)) := by sorry
end QZeroSum19.GK
Source
van Apeldoorn and Gilyén, Quantum algorithms for zero-sum games, arXiv:1904.03180v1, p. 4, proof of Lemma 1, the Φ(t + 1) display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.