Finite probability laws, convolution powers, and mixing times
DefinitionQSDMixing_GU_Supplement_FiniteProbabilityfourier-analysismarkov-chainp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-mixing-timequantum-state-discrimination
A finite probability law on a finite set is a function with total mass one. For a finite abelian group, the convolution power is the law of a sum of independent -distributed increments, with the point mass at zero.
The file defines both the distance and total-variation distance, and defines the abelian mixing time as the least integer for which is within the requested tolerance of the uniform law. Its value is if no time qualifies.
These definitions provide the classical probability layer used by Theorems 4--6.
Definition code
import Mathlib
set_option autoImplicit false
namespace QSDMixing.GU.Supplement
noncomputable local instance probabilityWalkDecidableEq {α : Type} : DecidableEq α :=
Classical.decEq α
/-- A probability mass function on a finite type, kept as real-valued data so the paper's
finite sums can be written literally. -/
structure FiniteProbability (α : Type) [Fintype α] where
toFun : α → ℝ
nonneg : ∀ x, 0 ≤ toFun x
sum_one : ∑ x, toFun x = 1
instance {α : Type} [Fintype α] : CoeFun (FiniteProbability α) (fun _ => α → ℝ) :=
⟨FiniteProbability.toFun⟩
/-- The uniform mass function on a nonempty finite type. -/
noncomputable def uniformMass (α : Type) [Fintype α] : α → ℝ :=
fun _ => 1 / (Fintype.card α : ℝ)
/-- The finite-space ℓ¹ distance used in Theorem 5. -/
noncomputable def l1Distance {α : Type} [Fintype α] (p q : α → ℝ) : ℝ :=
∑ x, |p x - q x|
/-- Total variation distance on a finite space. -/
noncomputable def totalVariation {α : Type} [Fintype α] (p q : α → ℝ) : ℝ :=
(1 / 2 : ℝ) * l1Distance p q
/-- Convolution of two real mass functions on a finite additive group. -/
noncomputable def addConvolution {A : Type} [AddCommGroup A] [Fintype A]
(p q : A → ℝ) (z : A) : ℝ :=
∑ x, p x * q (z - x)
/-- The law of a sum of `t` independent increments with common law `p`; at time zero it is
the point mass at zero. -/
noncomputable def convolutionPower {A : Type} [AddCommGroup A] [Fintype A]
(p : A → ℝ) : ℕ → A → ℝ
| 0 => fun z => if z = 0 then 1 else 0
| t + 1 => addConvolution (convolutionPower p t) p
/-- The classical ℓ¹ mixing time of the abelian walk, with copy counts starting at one and
value `⊤` if no time qualifies. -/
noncomputable def abelianMixingTime {A : Type} [AddCommGroup A] [Fintype A]
(p : A → ℝ) (ε : ℝ) : ℕ∞ :=
sInf {T : ℕ∞ | ∃ t : ℕ, 1 ≤ t ∧ T = t ∧
l1Distance (convolutionPower p t) (uniformMass A) ≤ ε}
end QSDMixing.GU.Supplement
Source
Zhou, Leditzky, A mixing time method for estimating the sample complexity of quantum state discrimination, arXiv:2609.40182 (held version, sha256 62fb68dd…), Theorems 4–6, pp.20–25, eqs. (19), (21)–(25)