The converse question of the result I am asking about is here. Denote the operator norm by $\|\cdot \|_\infty$. That is $\|X\|_\infty = \max\{\|Xv\|:\|v\| = 1\}$ and $\|\cdot\|$ is the Euclidean 2-norm for vectors.
Let $V_1, V_2$ be (possibly rectangular) matrices that satisfy $V_i^\star V_i = I$ (where $\star$ denotes the transpose conjugate) such that
$$\|V_1 XV_1^\star - V_2X V_2^\star\|_\infty\leq \varepsilon$$
for all positive semidefinite $X$ with $\lVert X\rVert_\infty = 1$. Is it possible to then bound
$$\|V_1 - V_2\|_\infty$$
in terms of $\varepsilon$?
I just want to point out another possible positive answer that people may be interested in.
Claim: suppose $V_1, V_2 \in R^{n\times r}$ where $r \leq n$ and $V_1^{\star}V_1 =V_2^{\star}V_2 = I_{r}.$ If $\|V_1V_1^{\star} - V_2V_2^{\star}\| \leq \epsilon$, then there exists a rotation matrix $H \in R^{r\times r}$ where $H^{\star}H = I_{r}$ and $$ \|V_1 H - V_2\| \leq 2\epsilon. $$ One possible $H$ can be explicitly constructed: $H = U_Q V_Q^{\star}$ where $V_1^{\star}V_2 = U_Q \Sigma_Q V_Q^{\star}$ is the SVD of $V_1^{\star}V_2.$
Proof: It is sufficient to show $\|V_1 H - V_2\| \leq 2\epsilon$ for $H = U_QV_Q^{\star}.$
First, notice that $\|AV_2\| \leq \|A\| \|V_2\| \leq \|A\|$ for any $A \in R^{n\times n}$. Let $A = V_1V_1^{\star} - V_2V_2^{\star}$, since $V_2^{\star}V_2 = I_r$, we have $$ \|V_1V_1^{\star}V_2 - V_2\| \leq \epsilon. $$ We tend to show that $\|H - V_1^{\star}V_2\| \leq \epsilon$, then by the triangle inequality, we can complete the proof: $$ \|V_1 H - V_2\| \leq \|V_1V_1^{\star}V_2 - V_2\| + \|V_1 (H - V_1^{\star}V_2)\| \leq \epsilon + \|V_1\| \|H-V_1^{\star}V_2\| \leq 2\epsilon. $$
Note that in fact, $$ \|H - V_1^{\star}V_2\| = \|U_Q V_Q^{\star} - U_Q\Sigma_Q V_Q^{\star}\| \leq \|U_Q\|\|I_r - \Sigma_Q\|\|V_Q\| = \|I_r - \Sigma_Q\|. $$
Next, we want to bound $\|I_r - \Sigma_Q\|.$ Notice that $\|V_2^{\star}A\| \leq \|A\|$. Let $A = V_1V_1^{\star}V_2 - V_2$, we have $$ \|V_2^{\star}V_1V_1^{\star}V_2 - V_2^{\star}V_2\| \leq \|V_1V_1^{\star}V_2 - V_2\| \leq \epsilon. $$ Note that $V_2^{\star}V_2 = I_r$ and $V_1^{\star}V_2 = U_Q \Sigma_Q V_Q^{\star}$ again, then $$ \|V_Q \Sigma_Q^{2} V_Q^{\star} - I_r\| \leq \epsilon. $$ This implies that $\|\Sigma_Q^2 - I_r\| \leq \epsilon.$ Notice that for any $a \in R^{+}$, $$ |a-1| \leq |a-1||a+1| = |a^2 - 1|. $$ Therefore, since $\Sigma_Q$ is diagonal and non-negative (singular values), we have $\|\Sigma_Q - I_r\| \leq \|\Sigma_Q^2 - I_r\| \leq \epsilon.$ This completes the proof.
Remark: Here, $H = U_Q V_Q^{\star}$ is in fact also the optimizer of the following problem: $$ \min_{F \in R^{r\times r}, F^{\star}F = I_{r}} \|V_1F - V_2\|_{\mathrm{F}} $$ where $\|\cdot\|_{\mathrm{F}}$ is the Frobenius norm. See Orthogonal Procrustes problem for further reference.