How does elementwise closeness of two bases relate to how close the bases are as a whole?

Question

The following is about different ways to determine "how close two orthonormal bases are"; it is motivated by this recent question and can be seen as an extension of this old question of mine.

---

Given any two orthonormal bases $\{\phi_i\}_{i=1}^n$, $\{\psi_i\}_{i=1}^n$ of $\mathbb C^n$ one can define the following two measures of "closeness":

1. The bases are elementwise $\varepsilon$-close in the sense that $\|\phi_i-\psi_i\|\leq \varepsilon$ for all $i$
2. The bases are $\varepsilon$-close in an overall, "unitary" sense: Let $U\in\mathbb C^{n\times n}$ be the unitary which maps $\{\phi_i\}_{i=1}^n$ to $\{\psi_i\}_{i=1}^n$ (i.e., $U=\sum_{i=1}^n|\psi_i\rangle\langle\phi_i|$). Then $\|{\bf1}-U\|_\infty$ (with $\|\cdot\|_\infty$ the usual operator norm) is a measure for how close the bases are

The vague, intuitive question is now:

How do these concepts relate to each other, i.e., if two orthonormal bases are elementwise $\varepsilon$-close, what upper bound for $\|{\bf1}-U\|_\infty$ can one get? And what about the converse?

One way to make this question more precise is via the fact that elementwise closeness also corresponds to a norm, namely a version of the $L_{2,\infty}$-norm $\|X\|_{2,\infty}:=\max_{i=1,\ldots,n}\|X|i\rangle\|$—but now adjusted to the basis we are interested in: Define \begin{align*} \|\cdot\|_\phi:\mathbb C^{n\times n}&\to\mathbb R_+\\ X&\mapsto \max_{i=1,\ldots,n}\|X|\phi_i\rangle\|\,. \end{align*} Because $\{\phi_i\}_{i=1}^n$ is a basis, $\|\cdot\|_\phi$ is a norm and, more importantly, $\|{\bf1}-U\|_\phi=\max_{i=1,\ldots,n}\|\,|\phi_i\rangle-|\psi_i\rangle\|$ which shows that $\|\phi_i-\psi_i\|\leq \varepsilon$ for all $i$ if and only if $\|{\bf1}-U\|_\phi\leq \varepsilon$. Hence this norm really captures the essence of the first concept of closeness we considered.

Now we have two different norms on the same space which means they have to be equivalent, that is, there exist constants $C_1,C_2\geq 0$ such that $C_1\|X\|_\infty\leq\|X\|_\phi\leq C_2\|X\|_\infty$ for all $X\in\mathbb C^{n\times n}$. Based on this formulation the precise question would be:

Given any orthonormal basis $\{\phi_i\}_{i=1}^n$, what are the optimal constants $C_1,C_2$ for our unitary case, i.e., what is the largest $C_1$ and the smallest $C_2$ such that $$C_1\|{\bf1}-U\|_\infty\leq\|{\bf1}-U\|_\phi\leq C_2\|{\bf1}-U\|_\infty$$ for all unitaries $U$?

Answer 1

The answer consists of the following three aspects:

1. If $\|{\bf1}-U\|_\infty\leq \varepsilon$, then $\|\phi_i-\psi_i\|\leq \varepsilon$ for all $i$
2. If $\|\phi_i-\psi_i\|\leq \varepsilon$ for all $i$, then $\|{\bf1}-U\|_\infty\leq \varepsilon\sqrt n$
3. The bound from 2. is optimal and can, in general, not be made independent of the system's dimension $n$

Or, in the language of equivalent norms: $$\boxed{\frac1{\sqrt n}\|{\bf1}-U\|_\infty\leq\|{\bf1}-U\|_\phi\leq \|{\bf1}-U\|_\infty}$$ and the coefficients are optimal, that is, there exist unitaries $U_1,U_2$ such that $\|{\bf1}-U_1\|_\infty=\|{\bf1}-U_1\|_\phi$ and, more interestingly, $\|{\bf1}-U_2\|_\infty=\sqrt n\|{\bf1}-U_2\|_\phi$. Let us go through these three claims one by one.

Step 1:

This is the easy part: for all $X$ $$ \|X\|_{\phi}=\max_{z\in\{\phi_1,\ldots,\phi_n\}}\|X|z\rangle\|\leq\max_{\|z\|=1}\|X|z\rangle\|=\|X\|_\infty $$ Equality ($\|{\bf1}-U_1\|_\infty=\|{\bf1}-U_1\|_\phi$) holds, e.g., for any diagonal unitary $U_1$. Hence $C_2=1$ and this choice is optimal.

Step 2:

Assume that $\|\phi_i-\psi_i\|\leq \varepsilon$ for all $i$ (equivalently: $\|{\bf1}-U\|_\phi\leq\varepsilon$) and let any $x\in\mathbb C^n$, $\|x\|=1$ be given. Then we expand $x=\sum_{i=1}^n\langle\phi_i|x\rangle|\phi_i\rangle$ (i.e., $\sum_{i=1}^n|\langle\phi_i|x\rangle|^2=\|x\|^2$) and compute \begin{align*} \|({\bf1}-U)|x\rangle\|=\|\,|x\rangle-U|x\rangle\|&=\Big\|\sum_{i=1}^n\langle\phi_i|x\rangle(\phi_i-\psi_i)\Big\|\\ &\leq\sum_{i=1}^n|\langle\phi_i|x\rangle|\,\|\phi_i-\psi_i\|\\ &\leq \Big( \sum_{i=1}^n|\langle\phi_i|x\rangle|^2 \Big)^{1/2}\Big( \sum_{i=1}^n\|\phi_i-\psi_i\|^2\Big)^{1/2}\\ &\leq \|x\|\Big( \sum_{i=1}^n\big(\max_j\|\,|\phi_j\rangle-U|\phi_j\rangle\|\big)^2\Big)^{1/2}\\ &=\|x\|\big(n\|{\bf1}-U\|_\phi^2\big)^{1/2}=\sqrt n\|{\bf1}-U\|_\phi\|x\|\,. \end{align*} The second step was the triangle inequality and the third step was Cauchy-Schwarz. For the operator norm this implies: $$ \|{\bf1}-U\|_\infty=\max_{\|x\|=1}\|({\bf1}-U)|x\rangle\|\leq \max_{\|x\|=1}\sqrt n\|{\bf1}-U\|_\phi\|x\|=\sqrt n\|{\bf1}-U\|_\phi\leq\varepsilon\sqrt n $$ This shows that the choice $C_1=\frac1{\sqrt n}$ is valid.

Step 3:

Proving that $C_1=\frac1{\sqrt n}$ is optimal and that, hence, the $\sqrt n$ cannot be avoided is arguably the trickiest part. To recap, given some "small" $\varepsilon>0$ (more precisely: $\varepsilon\in(0,\frac2{\sqrt n})$ we have to construct a unitary $U$ such that $\|{\bf1}-U\|_\phi\leq\varepsilon$, but $\|{\bf1}-U\|_\infty=\varepsilon\sqrt n$. We do so via the following Hamiltonian: define $H=\frac1n|{\bf e}\rangle\langle{\bf e}|$ with $|{\bf e}\rangle:=\sum_{i=1}^n|\phi_i\rangle$. This $H$—resp. the generated unitary $U:=e^{ic H}$, $c\in\mathbb R$—admits the following important property:

Lemma. For all $c\in\mathbb R$ it holds that ${\bf1}-U=(1-e^{ic})H$

Proof. Because $H^2=H$ (and thus $H^j=H$ for all $j\in\mathbb N$), we compute $$ U={\bf1}+\sum_{j=1}^\infty\frac{i^jc^j H^j}{j!}={\bf1}+H\sum_{n=1}^\infty\frac{i^jc^j}{j!}={\bf1}-H(1-e^{ic})\,.\tag*{$\square$} $$

I claim that this $U$ (for some appropriate $c\in\mathbb R$) now has the desired properties. Using the previous lemma, for all $i=1,\ldots,n$ \begin{align*} \|({\bf1}-U)|\phi_i\rangle\|=|1-e^{ic}|\|H|\phi_i\rangle\|=\frac{|1-e^{ic}|}n\|\,|{\bf e}\rangle\|={\frac{|1-e^{ic}|}{\sqrt n}} \end{align*} Hence $\|{\bf1}-U\|_{\phi}=(|1-e^{ic}|)/\sqrt n$ meaning one can certainly choose $c$ such that ${\frac{|1-e^{ic}|}{\sqrt n}}=\varepsilon$. On the other hand, $\|H\|_\infty=(\|{\bf e}\|^2)/n=1$ which implies $$ \|{\bf1}-U\|_\infty=|1-e^{ic}|\|H\|_\infty=|1-e^{ic}|=\sqrt n\|{\bf1}-U\|_{\phi}=\varepsilon\sqrt n\,. $$ This shows that, while the $\{\phi_i\}_i$, $\{\psi_i\}_i:=\{U\phi_i\}_i$ are elementwise $\varepsilon$-close, the unitary has distance $\varepsilon\sqrt n$ from the identity matrix which is what we had to show.