Let $U$ be an $n$-qubit unitary, and let $p_U(x) = |\langle x | U | 0\rangle |^2$ be the probability of obtaining $x \in \{0,1\}^n$ on the all zero input. Given two $n$-qubit unitaries $U$ and $V$, it is straightforward to show (see, e.g., Nielsen and Chuang, page 194) that for all $x \in \{0,1\}^n$, $|p_U(x) - p_V(x)| \leq 2 \|U - V\|$, where the righthand side is the operator norm between $U$ and $V$. Therefore, summing over all $x$ implies $\| p_U - p_V \|_{\text{TVD}} \leq 2^n \|U - V\|$, where the LHS is the total variation distance.

I am interested if this bound can ever be saturated. If not, are there $U$ and $V$ such that $\| p_U - p_V \|_{\text{TVD}}$ is exponential in $n$?

  • 1
    $\begingroup$ I guess not really your question, but $U=V$? $\endgroup$
    – DaftWullie
    Commented Jul 27, 2023 at 13:39
  • $\begingroup$ Fair enough, though let's say nontrivially saturate it $\endgroup$ Commented Jul 27, 2023 at 13:40
  • 2
    $\begingroup$ The total variational distance, as you defined it, is bounded above by 2. So no, you cannot make it exponential in $n$. To see it, $$ \|p_u - p_v\| = \sum_x |p_u(x)-p_v(x)| \leq \sum_x |p_u(x)| + |p_v(x)| = \sum_x p_u(x) + p_v(x) = 2 $$ $\endgroup$
    – Rammus
    Commented Jul 27, 2023 at 15:40
  • $\begingroup$ @Rammus That should be an answer I think $\endgroup$ Commented May 22 at 15:09


Your Answer

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

Browse other questions tagged or ask your own question.