Eq. (7.14) — concentration of Lipschitz functions of independent Haar unitaries
ProvedSpectrumLB.eq_7_14p2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationquantum-lower-boundsspectrum-estimation
Let be -Lipschitz, , with respect to the -sum of Hilbert–Schmidt metrics:
where . If are independent Haar-random unitaries, then for every ,
This is the concentration-of-measure input of the spectral separation (Lemma 7.3). The paper imports it from Meckes, The Random Matrix Theory of the Classical Compact Groups, Theorem 5.17, and does not prove it.
Differences from the source:
- encoding: ‖·‖₂ Hilbert–Schmidt norm and the L2-sum metric → √(Σ_i Σ_{x,y} |(U_i)_{xy} − (U'i){xy}|²) written out; reason: the same metric
- encoding: u (implicitly positive), Λ-Lipschitz → u ≥ 0, Λ > 0; reason: at u = 0 the bound is trivial; Λ appears in a denominator
Preamble
import Mathlib import Definitions.Def_SpectrumLB_haarK open MeasureTheory open scoped Matrix ComplexOrder MatrixOrder
Formal statement
namespace SpectrumLB
/-- **Eq. (7.14) (concentration of Lipschitz functions of Haar unitaries).**
Fanizza, O'Donnell, Wadhwa, *Spectrum Estimation is Almost as Hard as Tomography*, arXiv:2607.29680, §7.2, Eqs. (7.13)–(7.14), p. 36: "Let F : U(d)^{×K} → R be a real function that is Λ-Lipschitz with
respect to the L2-sum of Hilbert–Schmidt metrics on U(d) … By a standard result on the concentration of
Lipschitz functions of independent Haar-random unitaries, see e.g. [Mec19, Theorem 5.17], we have
Pr(|F(U_1, ⋯, U_K) − E F(U_1, ⋯, U_K)| ≥ u) ≤ 2e^{−(d−2)u^2/(24Λ^2)}."
**Formalization Note.** The metric of (7.13) is written out: `√(Σ_i ‖U_i − U'_i‖_2^2)` with the
Hilbert–Schmidt (Frobenius) norm `‖A‖_2^2 = Σ_{x,y} |A_{xy}|^2`. `Λ > 0` and `u ≥ 0`. The paper imports this
from [Mec19] and does not prove it; it is a milestone so that the goal is unconditional. -/
theorem eq_7_14 (d K : ℕ) (Λ : ℝ) (hΛ : 0 < Λ)
(F : (Fin K → Matrix.unitaryGroup (Fin d) ℂ) → ℝ)
(hF : ∀ U V : Fin K → Matrix.unitaryGroup (Fin d) ℂ,
|F U - F V| ≤ Λ * Real.sqrt (∑ i, ∑ x, ∑ y,
‖(U i : Matrix (Fin d) (Fin d) ℂ) x y - (V i : Matrix (Fin d) (Fin d) ℂ) x y‖ ^ 2))
(u : ℝ) (hu : 0 ≤ u) :
haarK d K {U | u ≤ |F U - ∫ V, F V ∂haarK d K|} ≤
ENNReal.ofReal (2 * Real.exp (-(((d : ℝ) - 2) * u ^ 2) / (24 * Λ ^ 2))) := by sorry
end SpectrumLB
Source
Fanizza, O'Donnell, Wadhwa, Spectrum Estimation is Almost as Hard as Tomography, arXiv:2607.29680, §7.2, Eqs. (7.13)–(7.14), p. 36 (citing [Mec19, Theorem 5.17])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.