Consider an $n$ qubit Haar random quantum state $|\psi\rangle$. Consider a distribution $\mathcal{D}_1$ over $n$ bit strings defined as $$ p_x = |\langle x| \psi \rangle|^{2}, $$ for $x \in \{0, 1\}^{n}$. Consider another distribution $\mathcal{D}_2$, defined as follows:

  • Sample a string $y$ from $\mathcal{D}_1$.
  • Throw away the last $k$ bits from $y$ and replace it with a suffix sampled uniformly at random from $\{0, 1\}^{k}$. Output this string.

I am trying to calculate the expected total variation distance between $\mathcal{D}_1$ and $\mathcal{D}_2$, where the expectation is over the random state. Note that when $k = 0$, the total variation distance is $0$, as they are the same distribution. When $k = n$, $\mathcal{D}_2$ is the uniform distribution and one could bound the total variation distance by a constant.

My intuition is, as long as $k$ is sufficiently small ($\leq \text{poly}\log n$) the total variation distance should also be small. Is my intuition correct?

  • $\begingroup$ How do you define the expected total variation distance in this case? $\endgroup$
    – MonteNero
    Jul 17, 2022 at 7:02
  • $\begingroup$ The standard definition of total variation distance between two distributions should suffice, right? $\endgroup$
    – Tom Clancy
    Jul 17, 2022 at 23:23


Your Answer

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