2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks. Do you know of a natural norm on the space of unitaries that does lower bound the TVD? $\endgroup$ Mar 8 at 5:12
  • 1
    $\begingroup$ All norms are equivalent in finite dimensions. $\endgroup$
    – Rammus
    Mar 8 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.