  The Johnson-Lindenstrauss Lemma is a classic result which implies that any
set of n real vectors can be compressed to O(log n) dimensions while only
distorting pairwise Euclidean distances by a constant factor. Here we consider
potential extensions of this result to the compression of quantum states. We
show that, by contrast with the classical case, there does not exist any
distribution over quantum channels that significantly reduces the dimension of
quantum states while preserving the 2-norm distance with high probability. We
discuss two tasks for which the 2-norm distance is indeed the correct figure of
merit. In the case of the trace norm, we show that the dimension of low-rank
mixed states can be reduced by up to a square root, but that essentially no
dimensionality reduction is possible for highly mixed states.
