**Abstract: **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.