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?


1 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.

  • $\begingroup$ In the equality $\mathbb{E}_{U} \operatorname{Tr}\left[ U | 0 \rangle \langle 0 | U^{\dagger} \Pi_{j} \right] = \frac{1}{d}$, to apply the lemma you mention in the next line, don't we need to somehow get rid of the trace in the LHS? The lemma has no trace in the LHS. $\endgroup$
    – BlackHat18
    Commented Jun 29, 2021 at 9:56
  • $\begingroup$ In other words, why can we commute the trace operator and the expected value operator, for this case? $\endgroup$
    – BlackHat18
    Commented Jun 29, 2021 at 10:10
  • 1
    $\begingroup$ @BlackHat18 I'm simply using the linearity of the trace to bring the averaging $\mathbb{E}_{U}$ inside the trace (the average is an integral in this case) and then applying the lemma to obtain $\mathbb{E}_{U} \left[ U | 0 \rangle \langle 0 | U^{\dagger} \right] = \frac{1}{d} \operatorname{Tr}\left[ | 0 \rangle \langle 0 | \right] \mathbb{I}$. The left multiplication with the $\Pi_{j}$ is also linear (so I can apply the averaging while keeping the $\Pi_{j}$ fixed on the right). I have updated the answer and added more details, hope it makes sense. $\endgroup$ Commented Jun 29, 2021 at 11:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.