A packing of the operator-norm ball of traceless Hermitian matrices: points, pairwise
ProvedBosonicLearn.hermitian_packingThe metric-entropy statement behind the size of the hard ensemble of Theorem 9.
There are absolute constants and such that for every there is a finite set of traceless Hermitian matrices with (i.e. ), of cardinality at least , such that for all distinct .
Proof idea: embed real matrices, , as . A standard Gaussian has with probability (GaussianMatrix.extreme_singular_values_deviation), every Frobenius ball of radius has Gaussian measure (Chernoff), and a greedy choice gives separated points in the good set.
Formalization Note The operator-norm bound is written as two Loewner inequalities and the squared Frobenius distance as ((X - Y) * (X - Y)).trace.re. The paper's ensemble of rotated projectors (Eq. (223)) is replaced by this statement.
import Mathlib open scoped Matrix ComplexOrder
namespace BosonicLearn
/-- **A packing of the operator-norm ball of traceless Hermitian matrices of size `exp(Ω(n²))`.**
Chen, Anna Mele, Anna Mele, Preskill, *When are bosonic Gaussian states classical to learn?*, arXiv:2609.26705, §8, proof of Theorem 9, Eq. (223), p. 66 ("a size M = 2^{Θ(n²)} ensemble"), and §5.1, p. 30 (`G_supp = {X ∈ Herm_0(n) : ‖X‖_op ≤ 4}`).
There are absolute constants `b, c > 0` and `n₀` such that for every `n ≥ n₀` there is a finite set `T` of traceless
Hermitian `n × n` matrices with `−4·1 ⪯ X ⪯ 4·1`, of cardinality at least `exp(c n²)`, any two distinct members of which
satisfy `‖X − Y‖_F² = Tr (X − Y)² ≥ b n`.
**Formalization Note.** The operator-norm bound is written as two Loewner inequalities and the Frobenius distance as
`Re Tr((X − Y)(X − Y))`. The paper's ensemble (rotated projectors) is replaced by this metric-entropy statement, which
is what the packing argument uses; it follows from the Gaussian measure of the operator-norm ball
(`GaussianMatrix.extreme_singular_values_deviation`) and of Frobenius balls. -/
theorem hermitian_packing :
∃ b : ℝ, 0 < b ∧ ∃ c : ℝ, 0 < c ∧ ∃ n₀ : ℕ, ∀ n : ℕ, n₀ ≤ n →
∃ T : Finset (Matrix (Fin n) (Fin n) ℂ),
Real.exp (c * (n : ℝ) ^ 2) ≤ (T.card : ℝ) ∧
(∀ X ∈ T, X.IsHermitian ∧ X.trace = 0 ∧
(((4 : ℝ) : ℂ) • (1 : Matrix (Fin n) (Fin n) ℂ) - X).PosSemidef ∧
(((4 : ℝ) : ℂ) • (1 : Matrix (Fin n) (Fin n) ℂ) + X).PosSemidef) ∧
∀ X ∈ T, ∀ Y ∈ T, X ≠ Y → b * n ≤ ((X - Y) * (X - Y)).trace.re := by sorry
end BosonicLearn