Bounding operator norm by total variation distance

Question

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.

Answer 1

No you cannot, here's a counterexample.

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.