# Expected value of a Haar random quantum state multiplied by a unitary

Consider a quantity $$\begin{equation} \mathbb{E}\big[\langle z|\rho|z\rangle\big], \end{equation}$$ where $$\rho = |\psi \rangle \langle \psi|$$ is a Haar-random state $$n$$-qubit quantum state and $$z$$ is the label of a fixed $$n$$-qubit basis vector. Now, consider $$\begin{equation} \sigma = \underset{\text{diagonal}~U}{\mathbb{E}}\big[U\rho U^{*}\big], \end{equation}$$ where $$\rho$$ is as defined before, and $$U$$ is a diagonal unitary matrix such that the diagonal entries are uniformly random complex phases. I am trying to prove that $$\begin{equation} \mathbb{E}\big[\langle z|\rho|z\rangle\big] = \mathbb{E}\big[\langle z|\sigma|z\rangle\big] \end{equation}$$

Intuitively, the result is clear as the Haar measure is invariant under left and right multiplication by a unitary. But, the RHS has two expectations - one nested inside the other - and I do not know how to simplify that.

With the chosen structure of $$U$$, i think it's even possible to prove the stronger statement: $$\langle z| \rho|z \rangle = \langle z| \sigma_\rho|z \rangle, \hspace{0.2em} \text{where} \hspace{0.2em} \sigma_\rho = \mathbb{E}_U \big[U\rho U^\dagger\big] \text{and} \hspace{0.3em} |z\rangle \hspace{0.3em} \text{a computational basis vector.}$$ You may write $$U = \sum_{k \in \{0, 1\}^n} e^{i \phi_k} |k\rangle \langle k|$$, for uniform $$\phi_k \in_R [0, 2\pi]$$ and calculate \begin{align*} U\rho U^\dagger &= \sum_{k, m} e^{i (\phi_k - \phi_m)} \langle k|\rho|m \rangle \cdot |k\rangle \langle m| \implies \\ \mathbb{E}_U \big[U\rho U^\dagger\big] &= \sum_{k, m} \mathbb{E}_\phi \big[e^{i (\phi_k - \phi_m)}\big] \cdot \langle k|\rho|m \rangle \cdot |k\rangle \langle m| \implies\\ \langle z |\sigma_\rho| z \rangle &= \sum_{k, m} \mathbb{E}_\phi \big[e^{i (\phi_k - \phi_m)}\big] \cdot \langle k|\rho|m \rangle \cdot \langle z|k\rangle \langle m|z \rangle \implies\\ \langle z |\sigma_\rho| z \rangle &= \sum_{k, m} \mathbb{E}_\phi \big[e^{i (\phi_k - \phi_m)}\big] \cdot \langle k|\rho|m \rangle \cdot \delta_{z,k} \delta_{z,m} = \langle z|\rho|z \rangle \end{align*}

I'm writing an alternate proof because it uses some interesting tools, computes the value of these expressions, and gives some insights into how we can interpret the quantities in consideration.

The first term is $$\mathbb{E}_{\mathrm{Haar}} \left[ \left\langle z | \rho | z \right\rangle \right]$$, where $$\rho := U | \psi_{0} \rangle \langle \psi_{0} | U^{\dagger}$$, $$U$$ distributed Haar-uniformly, and $$| \psi_{0} \rangle, | z \rangle$$ are some fixed states.

Let's start by rewriting, \begin{align} \left\langle z | \rho | z \right\rangle &= \operatorname{Tr}\left( \rho | z \rangle \langle z | \right) = \operatorname{Tr}\left( U | \psi_{0} \rangle \langle \psi_{0} | U^{\dagger} | z \rangle \langle z | \right) \\ &= \operatorname{Tr}\left( \hat{S} \left( U \otimes U^{\dagger} \right) \left( | \psi_{0} \rangle \langle \psi_{0} | \otimes | z \rangle \langle z | \right) \right), \end{align} where $$\hat{S}$$ is the SWAP operator and in the last equality, I've used the lemma, \begin{align} \operatorname{Tr}\left( X Y \right) = \operatorname{Tr}\left( \hat{S} X \otimes Y \right). \end{align}

Now, Haar-averaging the expectation value is equivalent to, \begin{align} \mathbb{E}_{U \sim \mathrm{Haar}} \left[ \left\langle z | \rho | z \right\rangle \right] &= \mathbb{E}_{U \sim \mathrm{Haar}} \left[ \operatorname{Tr}\left( \hat{S} \left( U \otimes U^{\dagger} \right) \left( | \psi_{0} \rangle \langle \psi_{0} | \otimes | z \rangle \langle z | \right) \right) \right]. \end{align}

Using another (wonderful) lemma, \begin{align} \int_{U \sim \mathrm{Haar}} dU U \otimes U^{\dagger} = \frac{\hat{S}}{d}, \end{align}

and noticing that the trace is linear, we can perform the Haar-average above to obtain, \begin{align} \mathbb{E}_{U \sim \mathrm{Haar}} \left[ \left\langle z | \rho | z \right\rangle \right] = \frac{1}{d} \operatorname{Tr}\left( \hat{S} \left( \hat{S} \right) \left( | \psi_{0} \rangle \langle \psi_{0} | \otimes | z \rangle \langle z | \right) \right). \end{align}

Moreover $$\hat{S}^{2} = I$$, that is, swapping twice does nothing, and so we have, \begin{align} \mathbb{E}_{U \sim \mathrm{Haar}} \left[ \left\langle z | \rho | z \right\rangle \right] = \frac{1}{d} \operatorname{Tr}\left( \left( | \psi_{0} \rangle \langle \psi_{0} | \otimes | z \rangle \langle z | \right) \right) = \frac{1}{d} \operatorname{Tr}\left( | \psi_{0} \rangle \langle \psi_{0} | \right) \operatorname{Tr}\left( | z \rangle \langle z | \right), \end{align} where we've used $$\operatorname{Tr}\left( A \otimes B \right) = \operatorname{Tr}\left( A \right) \operatorname{Tr}\left( B \right)$$.

Since both $$| z \rangle, | \psi_{0} \rangle$$ are normalized, we have, \begin{align} \mathbb{E}_{U \sim \mathrm{Haar}} \left[ \left\langle z | \rho | z \right\rangle \right] = \frac{1}{d}. \end{align}

What does this mean? Note that $$\left\langle z | \rho | z \right\rangle = \left| \left\langle z | U | \psi_{0} \right\rangle \right|^{2}$$, that is, it measures the probability to find a random state $$U | \psi_{0} \rangle$$ in the state $$| z \rangle$$. Since $$U| \psi_{0} \rangle$$ is (Haar-)uniformly distributed, the probability to find it in some state $$| z \rangle$$ is also uniformly distributed, i.e., $$\frac{1}{d}$$. Also, note that, the final result does not depend on either the choice of the initial state $$| \psi_{0} \rangle$$ or the state $$| z \rangle$$, reflecting our choice of the uniform measure.

For the second quantity, we follow a similar calculation. We have, $$\sigma = \mathbb{E}_{U \sim \mathrm{diag}} \left[ U \rho U^{\dagger} \right]$$, i.e., we average over diagonal unitaries uniformly distributed in some basis, let's call it $$\mathbb{B}$$.

Consider the spectral decomposition $$U = \sum\limits_{j=1}^{d} e^{i \phi_{j}} \Pi_{j}$$, where $$\{ \Pi_{j} \} = \mathbb{B}$$. Then, \begin{align} \sigma = \mathbb{E}_{U \sim \mathrm{diag}} \left[ U \rho U^{\dagger} \right] = \mathbb{E}_{U \sim \mathrm{diag}} \left[ \sum\limits_{j,k}^{d} e^{i \left( \phi_{j} - \phi_{k} \right)} \Pi_{j} \rho \Pi_{k}^{\dagger} \right] . \end{align}

Now, the uniform distribution over unitaries diagonal in $$\mathbb{B}$$ is essentially a uniform distribution over the phases $$\{ \phi \}$$. An average over these phases gives us $$\int_{\phi \sim \mathrm{uniform}[0, 2\pi]} d \phi e^{i \left( \phi_{j} - \phi_{k} \right)} = \delta_{j,k}$$. Therefore, \begin{align} \mathbb{E}_{U \sim \mathrm{diag}} \left[ \sum\limits_{j,k}^{d} e^{i \left( \phi_{j} - \phi_{k} \right)} \Pi_{j} \rho \Pi_{k}^{\dagger} \right] = \sum\limits_{j}^{d} \Pi_{j} \rho \Pi_{j} \equiv \mathcal{D}_{\mathbb{B}} \left( \rho \right), \end{align} where $$\mathcal{D}_{\mathbb{B}} (\cdot) \equiv \sum\limits_{j=1}^{d} \Pi_{j} \left( \cdot \right) \Pi_{j}$$ is the dephasing superoperator. Putting it all together, we have that the action of averaging uniformly over diagonal unitaries in a basis $$\mathbb{B}$$ is to dephase the state in the basis $$\mathbb{B}$$, i.e., \begin{align} \sigma = \mathbb{E}_{U \sim \mathrm{diag}} \left[ U \rho U^{\dagger} \right] = \mathcal{D}_{\mathbb{B}}(\rho). \end{align}

We're now ready to evaluate \begin{align} \mathbb{E}_{U \sim \mathrm{Haar}} \left\langle z | \sigma | z \right\rangle &= \mathbb{E}_{U \sim \mathrm{Haar}} \operatorname{Tr}\left( \sigma | z \rangle \langle z | \right) = \mathbb{E}_{U \sim \mathrm{Haar}} \operatorname{Tr}\left( \mathcal{D}_{\mathbb{B}} (\rho) | z \rangle \langle z | \right) \\ &= \mathbb{E}_{U \sim \mathrm{Haar}} \operatorname{Tr}\left( \rho \mathcal{D}_{\mathbb{B}} \left( | z \rangle \langle z | \right) \right), \end{align} where in the last equality I've used the self-adjointness of the dephasing superoperator -- which can be easily verified using the Kraus form above and the cyclicity of the trace -- which is used to "transfer" its action onto $$| z \rangle \langle z |$$ instead.

Now this quantity is in a form as the first one, namely, \begin{align} \mathbb{E}_{U \sim \mathrm{Haar}} \left\langle z | \sigma | z \right\rangle &= \mathbb{E}_{U \sim \mathrm{Haar}} \operatorname{Tr}\left( \rho \mathcal{D}_{\mathbb{B}} \left( | z \rangle \langle z | \right) \right) \\ &= \mathbb{E}_{U \sim \mathrm{Haar}} \operatorname{Tr}\left( U | \psi_{0} \rangle \langle \psi_{0} | U^{\dagger} \mathcal{D}_{\mathbb{B}} \left( | z \rangle \langle z | \right) \right) \\ &= \mathbb{E}_{U \sim \mathrm{Haar}} \operatorname{Tr}\left( \hat{S} \left( U \otimes U^{\dagger} \right) \left( | \psi_{0} \rangle \langle \psi_{0} | \otimes \mathcal{D}_{\mathbb{B}} \left( | z \rangle \langle z | \right) \right)\right), \end{align}

where in the last line I've used the SWAP trick as above. Then, performing the Haar average, and using $$\hat{S}^{2} = I$$, we have, \begin{align} \mathbb{E}_{U \sim \mathrm{Haar}} \left\langle z | \sigma | z \right\rangle = \frac{1}{d} \operatorname{Tr}\left( | \psi_{0} \rangle \langle \psi_{0} | \right) \operatorname{Tr}\left( \mathcal{D}_{\mathbb{B}} \left( | z \rangle \langle z | \right) \right) = \frac{1}{d}, \end{align} since both traces above are equal to one.

What does this quantity mean? Since $$\left\langle z | \sigma | z \right\rangle = \left\langle z | \mathcal{D}_{\mathbb{B}} (\rho) | z \right\rangle$$, this is equal to the fidelity between a fixed state $$| z \rangle$$ and a random state $$\rho$$ dephased in some basis $$\mathbb{B}$$. Once again, because the state $$U | \psi_{0} \rangle$$ is uniformly distributed, the fidelity equals that between two random states.

In closing, both averages are equal to $$1/d$$. That is, \begin{align} \mathbb{E}_{U \sim \mathrm{Haar}} \left\langle z | \rho | z \right\rangle = \frac{1}{d} = \mathbb{E}_{U \sim \mathrm{Haar}} \left\langle z | \sigma | z \right\rangle \end{align}

I'm also listing some references for the "swap trick" used above. It can be used for Measuring polynomial functions of states. In the high-energy literature, this has been dubbed the "replica trick" (since we have many copies of the original space; although the exact correspondence is disguised because of the twist operators in field theory). It has also been used to compute entanglement in a ground-breaking experiment and Monte-Carlo simulations. And finally, it can be used to linearize the measurement of the $$\alpha$$-Renyi entropies, see this wonderful paper; although there might be earlier (and better) references.

• Sorry if I'm asking a basic question but could you expand on the lemma $Tr(XY) = Tr(\hat{S}(X\otimes Y))$? $X$ and $Y$ belong to the same Hilbert space so a) are you creating a new Hilbert space in the right hand side and b) what is the effect of the swap operator here? It seems like this is almost saying $Tr(XY) = Tr(X)Tr(Y)$ which is false. Nov 7, 2020 at 14:29
• Thank you for your replies! I'd never heard of this trick before but it looks very interesting and the linked paper in your other answer is now on my reading list! Nov 7, 2020 at 18:18
• Glad it helped! :) It is one of my absolute favorites! In the high-energy literature, this has been dubbed the "replica trick" (since we have many copies of the original space; although the exact correspondence is disguised because of the twist operators in field theory). It has also been used to compute entanglement in a ground-breaking experiment and Monte-Carlo simulations. Nov 8, 2020 at 0:36
• We can also use it to linearize the measurement of the $\alpha$-Renyi entropies, see this wonderful paper. Nov 8, 2020 at 0:39
• Thank you for an excellent answer! Nov 17, 2020 at 6:42