# Prove that Shannon and von Neumann entropies satisfy $H(P)\ge S(\rho)$ with $P$ diagonal of $\rho$

Suppose there is some $$n$$-qubit state $$\rho$$. It is well known fact that, given some orthonormal basis $$U = \{|u_i\rangle\}$$, if $$p_i = \langle u_i| \rho |u_i \rangle$$ (that is, measuring $$\rho$$ with $$U$$ produce the result $$u_i$$ with probability $$p_i$$) and $$P = (p_1,...)$$, then $$H(P) \geq S(\rho)$$.

Although that statement is written in papers and even in Wikipedia, I haven't found any proper proof nor I have been able to prove it myself. I would be glad for some help.

This can be seen through "twirling" with a bunch of unitaries.

Call your density operator $$\rho$$. Let $$U_i$$ be a unitary with $$\pm 1$$ on the diagonal, and zeros everywhere else when expressed in your basis. Consider all $$2^d$$ such unitaries where $$d$$ is the dimension of your density matrix. I leave it to you to show that $$\rho_D = \frac{1}{2^d}\sum\limits_i U_i\rho U^\dagger_i$$, where $$\rho_D$$ is the diagonal matrix with entries $$p_i$$.

Using the concavity of entropy and the unitary invariance of entropy, we have that $$H(P) = S(\rho_D) = S\left(\frac{1}{2^d}\sum_i U_i\rho U^\dagger_i\right) \geq \frac{1}{2^d}\sum\limits_i S(U_i\rho U^\dagger_i) = S(\rho).$$

• Thanks! thats seems correct (i fixed the direction of the inequality, it was exactly the opposite). Do you have any intuition for the matrices $U_i$?
– Woka
Sep 6, 2020 at 10:56
• Yes, sorry about the typo and thanks for the fix. The construction of the $U_i$ is just to acheive the same result as the measurement but I'm not sure I can offer any deeper insight there. Rammus' comment is also a very clean way to do it if you're happy with using data processing.
– rnva
Sep 6, 2020 at 16:59
• After a few thoughts... Are you sure the entropy in invariant for unitary multiplication? Look at the proof which actually does it much easier. Define $\Pi_t = |u_t \rangle \langle u_t|$. Then $S(\sum_t \Pi_t \rho \Pi_t) = S(\sum_t \Pi_t p_t) = S(P) = H(P)$. And on the other hand, due to invariant of unitary + concaviity, $S(\sum_t \Pi_t \rho \Pi_t) \geq \sum_t S(\Pi_t \rho \Pi_t) = 2^n S(\rho) \geq S(\rho)$ which concludes the proof.
– Woka
Sep 9, 2020 at 13:32
• The von Neumann entropy is a function of the eigenvalues of the state. This cannot change after a unitary transformation. However, the projector $\Pi_t$ is not a unitary. Also there are $n$, not $2^n$ possibilities for the index $t$, if $n$ is meant to be the dimension of the state.
– rnva
Sep 10, 2020 at 14:16
• You are right, missed that they aren't unitary. Thanks!
– Woka
Sep 11, 2020 at 13:23

I will expand on my comment as an answer because it is not as immediate as I initially thought it was. Let $$D(\rho \| \sigma ) := \mathrm{Tr}[\rho( \log \rho - \log \sigma)]$$ be the relative entropy where $$\rho$$ is a state and $$\sigma$$ is a positive semidefinite operator. We can write the von Neumann entropy of a state $$\rho$$ in terms of the relative entropy, $$S(\rho) = -D(\rho \| \mathbb{1}).$$

Now the relative entropy satisfies something known as the data processing inequality) DPI which states that for any CPTP map $$\mathcal{N}$$ we have $$D(\rho \| \sigma) \geq D(\mathcal{N}(\rho) \| \mathcal{N}(\sigma)).$$

Let us take the CPTP map $$\mathcal{M}(\rho) = \sum_i |i \rangle \langle i | \rho | i \rangle \langle i |$$ which is defined by the measurement in your question. This map when applied to $$\rho$$ prepares the state $$\sum_i p(i) | i \rangle \langle i |$$ where $$p(i)$$ is the probability of obtaining outcome $$i$$ when measuring the state $$\rho$$. Now by the above we have \begin{aligned} S(\rho) &= -D(\rho \| \mathbb{1}) \\ &\leq -D(\mathcal{M}(\rho) \| \mathcal{M}( \mathbb{1})) \\ &= -D(\mathcal{M}(\rho) \| \mathbb{1}) \\ &= S(\mathcal{M}(\rho)) \\ &= H(p). \end{aligned}

Let $$\newcommand{\ket}{\lvert #1\rangle}\newcommand{\braket}{\langle #1 | #2\rangle}\{\ket{u_k}\}_k$$ be some orthonormal basis for the space, and define $$p_k\equiv \langle u_k|\rho| u_k\rangle$$. Let $$\newcommand{\bs}{\boldsymbol{#1}}\bs p\in\mathbb R^n$$ denote the corresponding vector. Write the eigendecomposition of $$\rho$$ as $$\rho = \sum_\ell \lambda_\ell |\lambda_\ell\rangle\!\langle\lambda_\ell\rvert, \qquad \lambda_\ell\ge0, \quad \sum_\ell \lambda_\ell=1.$$ From these, we see that $$p_k = \sum_\ell \lambda_\ell \lvert \braket{u_k}{\lambda_\ell}\rvert^2 = \sum_\ell M_{k,\ell}\lambda_\ell \equiv (M\bs\lambda)_k,$$ where $$M_{k,\ell}\equiv \lvert \braket{u_k}{\lambda_\ell}\rvert^2$$ is easily seen to be a bistochastic matrix, due to the completeness of both the bases $$\{\ket{u_k}\}_k$$ and $$\{\ket{\lambda_\ell}\}_\ell$$. See also Schur-Horn's lemma.
We therefore proved that $$\bs p=M\bs\lambda$$ for some bistochastic matrix $$M$$. This is equivalent to $$\bs p\preceq \bs\lambda$$, where $$\preceq$$ here denotes the majorization preorder. This, in turn, implies that $$H(\bs p)\ge H(\bs \lambda)$$ (see e.g. this related answer on math.SE). Because by definition of the von Neumann entropy $$H(\bs\lambda)=S(\rho)$$, we reach the conclusion.