How close or far apart are the distributions generated by two Haar random states?

Question

Consider two $n$ qubit Haar-random quantum states $|\psi\rangle$ and $|\phi\rangle$. Let $D_{|\psi\rangle}$ and $D_{|\phi\rangle}$ be the two probability distributions (over $n$-bit strings) obtained by measuring $|\psi\rangle$ and $|\phi\rangle$ respectively, in the standard basis. I had two questions:

1. What can we say about the total variation distance between $D_{|\psi\rangle}$ and $D_{|\phi\rangle}$ (with some probability over the choice of a particular $|\psi\rangle$ and $|\phi\rangle$)?
2. Are $D_{|\psi\rangle}$ and $D_{|\phi\rangle}$ computationally/statistically indistinguishable (again with some probability over the choice of a particular $|\psi\rangle$ and $|\phi\rangle$)?

EDIT: I managed to prove that they are not statistically indistinguishable, with overwhelming probability. However, are they computationally indistinguishable?

Answer 1

Since the Haar-measure is unitarily invariant, the $\mathbf{D}_\psi$ that we obtain will be independent of $\psi$. In fact, the $\mathbf{D}_\psi$ obtained from measuring $\psi$ with respect to any basis becomes $\psi$- and basis-independent.

As an example, let $\mathbb{B} = \{ \Pi_{j} = | j \rangle \langle j | \}_{j=1}^{d}$ be an orthonormal basis of $\mathcal{H}$, $\mathbf{p}(\psi,j) = \left| \left\langle \psi | j \right\rangle \right|^2 = \operatorname{Tr}\left[ | \psi \rangle \langle \psi | \Pi_{j} \right]$, and $\mathbb{E}_{U} [\cdots]$ denote Haar-averaging. Then, \begin{align} \mathbb{E}_{U} [\mathbf{p}(\psi,j)] &= \mathbb{E}_{U} \operatorname{Tr}\left[ U | 0 \rangle \langle 0 | U^{\dagger} \Pi_{j} \right] = \operatorname{Tr}\left[ \mathbb{E}_{U} \left[ U | 0 \rangle \langle 0 | U^{\dagger} \right] \Pi_{j} \right] \\ &=\frac{1}{d} \operatorname{Tr}\left[ | 0 \rangle \langle 0 | \right] \operatorname{Tr}\left[ \Pi_{j} \right] = \frac{1}{d}, \end{align} where in the second equality, I bring the expectation value inside the trace (since the trace is linear), and in the third equality, I've used the the following lemma: $\mathbb{E}_{U} [UXU^{\dagger}] = \operatorname{Tr}\left[ X \right] \frac{\mathbb{I}}{d}$. Notice that this average value does not depend on the choice of either $\psi$ or the basis $\mathbb{B}$. Namely, Haar-uniformity is such a strong assumption that it "coarse-grains" all details about the state of the system.

Moreover, since the fidelity is a Lipschitz continuous function, Levy's lemma ensures that deviations from this expected value of $\frac{1}{d}$ are exponentially suppressed in the dimension of the system. Namely, let $f(U)=\operatorname{Tr}\left[ U | 0 \rangle \langle 0 | U^{\dagger} \Pi_{j} \right] = \left| \left\langle \psi | j \right\rangle \right|^2$ be a function that inputs a Haar-random unitary $U$ and outputs the probability of obtaining the "classical string" associated to $|j\rangle$, then, for any $\epsilon >0$, \begin{align} \mathrm{Prob} \{ \left| f(U) - \frac{1}{d} \right| \geq \epsilon \} \leq \exp \left[ - \frac{d \epsilon^{2}}{4 K^{2}} \right] \end{align} Here $K$ is the Lipschitz constant associated to the function $f$, which for the fidelity can be chosen to be $2$.

See https://quantumcomputing.stackexchange.com/a/18174/1108 for a similar discussion.