A quantum Johnson-Lindenstrauss lemma via unitary t-designs

Understand

The famous Johnson-Lindenstrauss lemma states that for any set of n vectors, there is a linear transformation into a space of dimension O(log n) that approximately preserves all their lengths.

• In fact, a Haar random unitary transformation followed by projection onto the first O(log n) coordinates followed by a scaling works as a valid transformation with high probability.
• In this work, we show that the Haar random unitary can be replaced by a uniformly random unitary chosen from a finite set called an approximate unitary t-design for t = O(log n).
• Choosing a unitary from such a design requires only polylogarithmic random bits as opposed to exponential in dimension random bits required to choose a Haar random unitary with reasonable precision.