  Consider the $n!$ different unitary matrices that permute $n$ $d$-dimensional
quantum systems. If $d\geq n$ then they are linearly independent. This paper
discusses a sense in which they are approximately orthogonal (with respect to
the Hilbert-Schmidt inner product) if $d\gg n^2$, or, in a different sense, if
$d\gg n$. Previous work had shown pairwise approximate orthogonality of these
matrices, but here we show a more collective statement, quantified in terms of
the operator norm distance of the Gram matrix to the identity matrix.
  This simple point has several applications in quantum information and random
matrix theory: (1) showing that random maximally entangled states resemble
fully random states, (2) showing that Boson sampling output probabilities
resemble those from Gaussian matrices, (3) improving the Eggeling-Werner scheme
for multipartite data hiding, (4) proving that the product test of
Harrow-Montanaro cannot be performed using LOCC without a large number of
copies of the state to be tested, (5) proving that the purity of a quantum
state also cannot be efficiently tested using LOCC, and (6, published
separately) helping prove that poly-size random quantum circuits are
poly-designs.
