Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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).$$
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}[1]{\lvert #1\rangle}\newcommand{\braket}[2]{\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}[1]{\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.
