Lemma 3: Haar overlap concentration
OpenQAlgorithms.Papers.Independent.Intakenext100.P54.haar_overlap_concentrationLet , let be an integer, let be a normalized pure state on , and let be an orthogonal projector of rank . Suppose are independent measurable random unitaries, each having the normalized Haar law. For ,
Here a vector and its rank-one density operator are distinguished in the formalization. The result controls Haar overlap fluctuations; at rank zero the event has probability one and the upper bound is two.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P54
noncomputable section
open scoped BigOperators Matrix ComplexConjugate ComplexOrder NNReal ENNReal
open MeasureTheory ProbabilityTheory
namespace QAlgorithms.Papers.Independent.Intakenext100.P54
open QAlgorithms.Papers.Independent.Information100.P03 (PureEnsemble)
open QAlgorithms.Papers.Independent.Information100.P53 (fidelity)
open QAlgorithms.Papers.Independent.Dependency50.P07 (wordProb)
open QAlgorithms.Papers.Independent.Claimed50.P08 (classicalEntropy)
open QAlgorithms.Papers.Independent.Claimed50.P38 (tensorSuperop)
/-- Lemma 3, PDF pp.3,14–15: two-sided concentration of independent Haar overlaps.
Rank zero is included; its right-hand side is two. The paper's exp has base two. -/
theorem haar_overlap_concentration {Omega : Type*} [MeasurableSpace Omega]
(mu : Measure Omega) [IsProbabilityMeasure mu] (D K p : ℕ)
(hD : 0 < D) (hK : 0 < K) (hp : p ≤ D)
(phi : RSPVector (Fin D)) (P : Matrix (Fin D) (Fin D) ℂ)
(hHerm : P.IsHermitian) (hProj : P * P = P) (hRank : P.trace.re = p)
(U : Fin K → Omega → Matrix.unitaryGroup (Fin D) ℂ)
(hMeas : ∀ k, Measurable (U k)) (hInd : iIndepFun U mu)
(hHaar : ∀ k, Measure.map (U k) mu = QAlgorithms.Schur.unitaryHaar D)
(eps : ℝ) (heps : 0 < eps) (hepsOne : eps ≤ 1) :
mu {w | |(∑ k, ((U k w : Matrix (Fin D) (Fin D) ℂ) * pureDensity phi.val *
(U k w : Matrix (Fin D) (Fin D) ℂ)ᴴ * P).trace.re) /
(K : ℝ) - (p : ℝ) / D| ≥ eps * p / D} ≤
ENNReal.ofReal (2 * (2 : ℝ) ^ (-(K : ℝ) * p * eps ^ 2 / 6)) := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P54
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be any measurable space with a probability measure ; let be natural numbers with , , and ; let have Euclidean norm one; and let be a complex matrix satisfying , , and . For every family of measurable, jointly independent random unitary matrices , , each having the normalized Haar distribution on , and every real , the following probability bound holds:
The right side is embedded into the extended nonnegative reals used for measure values. The assumptions allow ; in that case the event is all of , because its threshold is zero, and the displayed upper bound is .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.