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?
