# A question on random quantum states and the uniform distribution

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?

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