Let $U$ be an $n$-qubit unitary and $P_U(x) = |\langle x |U|0^n\rangle|$ the probability of measuring $x$ after acting $U$ on $|0^n\rangle$. For two $n$-qubit unitaries $U$ and $V$, one can prove that $$ |P_U(x) - P_V(x)| \leq 2\|U - V\|, $$ where $\|\cdot\|$ denotes the operator norm (see, e.g., page 194 in Nielsen and Chuang). Therefore, the total variation distance between the distributions $P_U$ and $P_V$ satisfies $$ \frac{1}{2}\sum_{x \in \{0,1\}^n} |P_U(x) - P_V(x)| \leq 2^n\|U - V\|. $$ I am interested if it is known if this bound can in general be improved to $$ \frac{1}{2}\sum_{x \in \{0,1\}^n} |P_U(x) - P_V(x)| \leq f(n)\|U - V\| $$ for some sub-exponential function $f$. If so, how; if not, why not?

  • 1
    $\begingroup$ You can check if your inequality $\frac{1}{2}\sum_{x \in \{0,1\}^n} |P_U(x) - P_V(x)| \leq 2^n\|U - V\| $ can be attained. If so, then $f(n)$ is not possible. $\endgroup$
    – narip
    Commented May 13, 2023 at 11:20


Your Answer

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