Bounds on Dimension Reduction in the Nuclear Norm

For all n ≥ 1, we give an explicit construction of m × m matrices A₁, …, A_n with m = 2^⌊n∕2⌋ such that for any d and d × d matrices A1′,…,An′ that satisfy∥Ai′−Aj′∥S1≤∥Ai−Aj∥S1≤(1+δ)∥Ai′−Aj′∥S1 (Formula presented) for all i, j ∈{1, …, n} and small enough δ = O(n^−c), where c > 0 is a universal constant, it must be the case that d ≥ 2^{⌊n∕2⌋−1}. This stands in contrast to the metric theory of commutative ℓ_p spaces, as it is known that for any p ≥ 1, any n points in ℓ_p embed exactly in ℓpd for d = n(n − 1)∕2. Our proof is based on matrices derived from a representation of the Clifford algebra generated by n anti-commuting Hermitian matrices that square to identity, and borrows ideas from the analysis of nonlocal games in quantum information theory.