# Set of unitaries with “spread-like” properties

I'm interested in finding two sets of $N$ unitary $N \times N$ matrices $U_{1}, \ldots, U_{N}$, $V_{1}, \ldots, V_{N}$ such that:

$\sup\limits_{X, Y}\sum\limits_{j,k = 1}^{N} |\mathrm{Tr}(YU_{j}XV_{k}^{\ast})|^2 \ll N$

where the sup is over all Hermitian traceless matrices with Frobenius norm $1$ nad $\ll$ means that the sum is asymptotically smaller than $N$.

The motivation comes from a problem in quantum information theory. An explicit construction of such sets of $U_{j}$ and $V_{k}$ would be the most desirable result, although pseudorandom constructions would also be very interesting. This statement is true if instead of taking unitaries we take matrices with independent Gaussian entries (rescaled properly so that on average each column has norm 1 etc.); however, I don't know how to show that random unitaries satisfy this property, so a hint for such a proof would also be welcome.

I would like to think of such unitaries as having some sort of "spread" property similar to objects showing up in the study of pseudorandomness like mutually unbiased bases, randomness extractors etc. However, I'm not sure if there is any definite connection to those notions.

-
The obvious choice is, identifying ${\bf C}^N$ with $l^2_N$, to let $U_j$ be the shift by $j$ units and $V_k$ be multiplication by $e^{2\pi ik/N}$. Did you try to compute the sup for them? –  Nik Weaver Jul 7 '12 at 0:39

Here is a suggestion on how to obtain random unitaries from random gaussians. No idea on how to derandomize the construction. This is inspired by Pisier's remark 16.9 in his survey on Grothendieck's theorem (the numerotation refers to the director's cut version).

Let me assume that you can prove that if $A_j,B_k$ are $2N$ iid matrices with independent entries $\mathcal N_{\mathbb C}(0,1/N)$, then $$\mathbb E \sup_{X,Y} \left( \sum\limits_{j,k = 1}^{N} |\mathrm{Tr}(YA_{j}X B_{k}^{\ast})|^2\right)^{1/2} \ll N.$$

(if you only know that you have this inequality with high probability but not in expectation, you can perhaps adapt the argument below if the probability is high enough).

The key property of $A_j$ and $B_k$ is that by the properties of gaussian variables, in the polar decomposition $A_j = U_j |A_j|$ abd $B_k =V_k |B_k|$, $U_j$ (resp. $V_k$) is uniform in $\mathcal U(N)$ and independent from $|A_j|$ (resp. $|B_k|$). Moreover by unitary invariance of $A_j$, $\mathbb E[|A_j|] = c_N Id$ for some constant $c_N$, and by standard random matrix/free probability facts $c_N$ has a positive and finite limit as $N \to \infty$.

By taking the conditional expectation with respect to $\sigma(U_j,V_k, 1 \leq j,k\leq N)$, you therefore have $$c_N^2 \mathbb E \sup_{X,Y} \left( \sum\limits_{j,k = 1}^{N} |\mathrm{Tr}(YU_{j}X V_{k}^{\ast})|^2\right)^{1/2}\leq \mathbb E\sup_{X,Y} \left( \sum\limits_{j,k = 1}^{N} |\mathrm{Tr}(YA_{j}X B_{k}^{\ast})|^2\right)^{1/2},$$ which proves that your inequality holds with uniform random unitaries.

-
Thanks! I will read the answer more carefully later, but it seems that it solves the the question about random unitaries. Can you provide a reference for "by standard random matrix/free probability facts"? I know a little about random matrix theory, though not that much, and hardly anything about free probability. –  Michal Kotowski Jul 13 '12 at 16:10
Ok. So $c_N=\mathbb E \frac 1 N Tr(|A|)$. The fact that $c_N$ has a limit which is explicitely computable is a particular fact that $\mathbb E \frac 1 N Tr(f(A^*A)$ has a limit for every continuous function $f$, in term of the Marchenko-Pastur distribution. See for example en.wikipedia.org/wiki/Marchenko%E2%80%93Pastur_distribution –  Mikael de la Salle Jul 15 '12 at 20:16