2019/01/28 by Regev, Oded, Vidick, Thomas · 1 citation
#FOS: Mathematics #Metric Geometry (math.MG)
paper · doi:10.48550/arxiv.1901.09480
\newcommand\schs\scriptstyleS1 For all n ≥ 1, we give an explicit construction of m × m matrices A1,…,An with m = 2\lfloor n/2 \rfloor such that for any d and d × d matrices A'1,…,A'n that satisfy ‖A'i-A'j‖\schs ≤ ‖Ai-Aj‖\schs ≤ (1+δ) ‖A'i-A'j‖\schs 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\lfloor n/2\rfloor -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.