Set of unitaries with "spread-like" properties

Question

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.

Answer 1

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.