Given a set X of n unit vectors in arbitrary dimension and eps>0 the
Johnson-Lindenstrauss states that the pairwise correlations between the
vectors in X, i.e. their Gram matrix, can be approximately reproduced in
dimension d=O(log n/eps^2). The lemma has found numerous applications
that include metric embeddings, approximate nearest-neighbor search,
learning mixtures of Gaussians, and more.

We pose the question of the existence of a similar dimension reduction
procedure for unitary matrices. Given a set of n unitary matrices in
arbitrary dimension and eps>0, does there exist a dimension d, depending
on n and eps only, and n unitary matrices in dimension d whose pairwise
inner product Tr(UV*) approximately reproduces the pairwise inner
products between unitaries in X?

This question is motivated by problems in functional analysis (Connes
embedding conjecture), quantum information theory (entanglement and
non-locality), combinatorics (graph limits), the representation theory
of finitely presented groups and algebras, and more. I will motivate the
question, present some of the connections, and give an answer for the
special case of unitaries that are permutation matrices.

Based on joint work with Oded Regev and William Slofstra.