# Bounding operator norm by total variation distance

Let $$P_U(y \mid x) = |\langle y | U | x \rangle|^2$$ denote the probability distribution of obtaining the bitstring $$y \in \{0,1\}^n$$ on a fixed input $$x \in \{0,1\}^n$$ w.r.t. the unitary $$U$$. For $$n$$-qubit unitaries $$U$$ and $$S$$ with probability distributions $$P_U(y \mid x)$$ and $$P_S(y \mid x)$$, respectively, it is relatively easy to show (see, e.g., page 194 in Nielsen and Chuang) that the total variation distance (TVD) between $$P_U(y \mid x)$$ and $$P_S(y \mid x)$$ is bounded above by the operator norm of $$U - S$$, times an exponential factor. In particular, $$\frac{1}{2}\sum_{y \in \{0,1\}^n}\left|P_U(y \mid x) - P_S(y \mid x)\right| \leq 2^n ||U - S||_{\mathrm{op}}.$$ Is there an inequality that goes the other way? I.e., a nontrivial upper bound on $$||U - S||_{\mathrm{op}}$$ in terms of the TVD? I feel like there must for the simple intuition that if $$U$$ and $$S$$ are within some small $$\epsilon > 0$$, then the distributions they generate must be close as well.

Let $$U=I$$ be the identity matrix and let $$S = \sum_{i} (-1)^{\delta_{0,i}} |i\rangle \langle i|$$ where $$\delta_{i,j}$$ is the Kronecker delta. That is, $$S$$ is almost the identity except $$|0\rangle \langle 0|$$ has a phase flip.
Now one can check that $$P_{U}(x|y) = P_{S}(x|y)$$ for all $$x$$ and $$y$$ so your TVD between $$P_U$$ and $$P_S$$ will be $$0$$. However, $$\|U-S\| = \|2 |0\rangle \langle0|\| = 2.$$ Hence we cannot lower bound the TVD by $$\|U-S\|$$ in the context of this question.