This is not an answer to Kate's question, but a remark that is too long for a comment. I answers (negatively) Tracy's comment. I am sure all this is clear to Kate.

The content of my comment is that you cannot take all the $U_i$'s and $V_j$'s commuting, and this is related to Grothendieck's inequality (see Pisier's very nice recent survey).

Indeed, then the $C^*$-algebra generated by the $U_i$'s and the $V_j$'s would be commutative and thus isomorphic to some $C(X)$ for a compact space $X$, and the linear functional $A\mapsto \langle Ax,y\rangle$ would correspond to a (signed) measure $\mu$ of total mass at most $1$ on $X$.

This would mean that you could write $\langle x_i,y_j\rangle$ as $\int f_i g_j d\mu$ where $f_i$ and $g_j \in C(X)$ have modulus one. Multiplying $g_j$ by the Radon-Nikodym derivative of $\mu$ with respect to $|\mu|$ we could as well assume that $\mu$ be positive. But Grothendieck's inequality says that such a decomposition is in general not possible unless $\sup_i \|f_i\|_2 \sup_j \|g_j\|_2\geq K_G$ where $K_G>1$ is Grothendieck's constant (complex case) and $\|\cdot\|_2$ is the $L^2$ norm with respect to $\mu$.

In fact (see remark 2.12 here), it is even known that, in general, one cannot take diagonal $D_i$'s as in Tracy Hall's comment unless $\sup_i \|D_i\|_2 \geq c n \log n$ for some $c$. Here for a diagonal matrix $D$, by $\|D\|_2$ I mean $(\sum_k |D_k|^2)^{1/2}$.

3more comments