# Probability distribution of a pretty-good measurement

Let $\rho_{XE}$ be a classical-quantum state. That is, $$\rho_{XE} = \sum_{x}\Pr[X=x] \cdot |x\rangle \langle x | \otimes \rho_{x}$$ where every $\rho_{x}$ is a density matrix with $\mathrm{Tr}(\rho_{x})=1$.

Define the POVM $\{F_{x}\}_{x}$ to be the pretty-good measurement (PGM) on $E$, trying to predict $X$, defined by $$F_{x} = \Pr[X=x]\rho^{-1/2}\rho_{x}\rho^{-1/2}$$ where $\rho = \sum_{x}\Pr[X=x]\rho_{x}$ is the average encoding.

Question: Given a specific $x$, is it true that for every $y$, $\mathrm{Tr}(F_{x}\rho_{x}) \ge \mathrm{Tr}(F_{x}\rho_{y})$?

It seems like it should be true, but I can't figure out the proof. Moreover, a proof for $\mathrm{Tr}(F_{x}\rho_{x}) \ge (\mathrm{Tr}(F_{x}\rho_{y}))^2$ will be good as well.

• @NorbertSchuch I am not sure whether the fact that $X$ is classical is relevant or not, so I specified my settings of interest. It does smell like Cauchy-Schwartz, but I wasn't able to figure out the right way to prove it. – Daniel86 Mar 24 '16 at 12:28
• @NorbertSchuch Thank you for your comment, I hope it is more clear now. – Daniel86 Mar 24 '16 at 13:24
• @NorbertSchuch yes, the trace is $1$. You are probably right, but I thought it is better to explain the scenario - in which one tries to predict a classical value given a quantum side-information. – Daniel86 Mar 24 '16 at 13:41
• @NorbertSchuch It is neither a textbook not a homework question. It is a claim that would be useful for a work in progress of mine (quantum-computation related). It is hard for me to put things in closer context, however I did add a "relaxation" which may be easier to achieve. – Daniel86 Mar 25 '16 at 14:23
• Of course, my mistake. Corrected. – Daniel86 Mar 25 '16 at 17:41

The inequality $\mathrm{tr}[F_x\rho_y] \le \mathrm{tr}[F_x\rho_x]$ is true for the case of case of two outcomes, however generally wrong for the case of three or more outcomes.

(I.e., the bottomline is that a pretty good measurement will have a higher succeed probability on the correct codeword than on the average of all other codewords, but there might be (rare) codewords which have a higher success probability.)

Let us first provide a counterexample for the case of three outcomes. To this end, let $p_1=p_2=\tfrac12$ and $p_3=0$, and let \begin{align} \rho_1 &= \left(\begin{matrix}\tfrac13\\&\tfrac23\end{matrix}\right)\ , \\ \rho_2 &= \left(\begin{matrix}\tfrac23\\&\tfrac13\end{matrix}\right)\ , \\ \rho_3 &= \left(\begin{matrix}0\\&1\end{matrix}\right)\ . \end{align} Then, $\rho=\tfrac121\!\!1$, which yields $$F_1 = \left(\begin{matrix}\tfrac1{3}\\&\tfrac2{3}\end{matrix}\right)\ ,$$ and thus $\mathrm{tr}[F_1\rho_1]=\tfrac1{3}\tfrac13+\tfrac2{3}\tfrac23=\tfrac{5}{9}$, while $\mathrm{tr}[F_1\rho_3]=\tfrac2{3}=\tfrac{6}{9}>\tfrac{5}{9}$.

Note that the fact that $p_3=0$ bears no relevance, since the example is robust under perturbations.

Let us now prove the inequality for the case of two outcomes. To this end, let $\sigma_x\le 1\!\!1$. It holds that $$\mathrm{tr}[\sigma_x\rho]^2 = \mathrm{tr}[(\rho^{1/4}\sigma_x \rho^{1/4})(\rho^{1/2})] \stackrel{(*)}{\le} \mathrm{tr}[\rho]\,\mathrm{tr}[\sigma_x\sqrt{\rho}\sigma_x\sqrt{\rho}]\ ,$$ where in $(*)$ we have used Cauchy-Schwarz, and also repeatedly the cyclicity of the trace. It is now straightforward to check that the above inequality is equivalent to $$\frac{\mathrm{tr}[\sigma_x\sqrt{\rho}(1\!\!1-\sigma_x)\sqrt{\rho}]}{ \mathrm{tr}[\rho]-\mathrm{tr}[\rho\sigma_x]} \le \frac{\mathrm{tr}[\sigma_x\sqrt{\rho}\sigma_x\sqrt{\rho}]}{ \mathrm{tr}[\rho\sigma_x]}\ .$$

By choosing $\sigma_x = p_x\rho^{-1/2}\rho_x\rho^{-1/2}\equiv F_x$, this immediately yields the inequality $$\mathrm{tr}\left[F_x\frac{\rho-p_x\rho_x}{1-p_x} \right]\le \mathrm{tr}\left[F_x\rho_x\right]\ ,$$ where we have used that $\mathrm{tr}[\rho]=\mathrm{tr}[\rho_x]=1$, and thus $\mathrm{tr}[\rho\sigma_x]=\mathrm{tr}[p_x\rho_x]=p_x$.

In the case where $p_x\rho_x+p_y\rho_y = \rho$ (i.e., with only two outcomes), this immediately yields $$\mathrm{tr}[F_x\rho_y] \le \mathrm{tr}[F_x\rho_x]$$ and thus completes the proof.

• I apologize for the previous mishaps. Something was nagging me. I think I got it, eventually. The conclusion is correct, and exceptions to $Tr[F_x\rho_x] > Tr[F_x\rho_y]$ are actually many. As an aside, working out the 3 outcome example in the answer for $p_1 = p_2 = p$, $p_3 = 1-2p$ and $\rho_1$, $\rho_2$, $\rho_3$ as given, shows that the ineq. fails whenever $p>1/3$. – udrv Mar 30 '16 at 22:57
• However, the 1st inequality (Cauchy-Schwartz) in the 2 outcome proof is very general and yields something interesting. For $\sigma_x = F_x = p_x\rho^{-1/2}\rho_x\rho^{-1/2}$ and $Tr[F_x \rho] = p_x$ it gives $p_x^2 \le Tr[F_x\rho^{1/2}F_x\rho^{1/2}]$, or after some consolidating, $Tr[F_x\rho_x] \ge p_x$. Now substitute $p_x = Tr[F_x \rho] = \sum_{y\neq x}{p_y Tr[F_x\rho_y]} + p_x Tr[F_x \rho_x]$ and isolate the latter term to get $Tr[F_x\rho_x] \ge (1-p_x)^{-1} \sum_{y\neq x}{p_y Tr[F_x\rho_y]}$, or better, $$Tr[F_x\rho_x] \ge \frac{\sum_{y\neq x}{p_y Tr[F_x\rho_y]}}{\sum_{y\neq x}{p_y}}$$ – udrv Mar 30 '16 at 22:57
• @udrv Indeed. In fact, this is an immediate consequence of the very last inequality in the answer, when you choose $\rho_y$ to be the (normalized & weighted) sum over all $\rho_z$ with $z\ne x$, which is a way of reducing the $k$-outcome case to a $2$-outcome case. (Originally I thought that one could prove the $k$-outcome case that way but I had overlooked the need to re-normalize). BTW, it is Schwarz, not Schwartz (pleeeease ;-). – Norbert Schuch Mar 31 '16 at 7:17
• Oy, Schwarz, got it :) As for the k-outcome, same here. But I kept loosing other factors. – udrv Mar 31 '16 at 11:33

Edit: I still don't know if the first inequality you seek really holds, but the following does get pretty darn close :D

For every $x$ define $${\hat u}_x = \rho^{-1/4}\rho_x\;\rho^{-1/4}$$ and rewrite the quantities of interest as $$Tr(F_x\rho_x) = \text{Pr}(X=x)Tr\left(\rho^{-1/2}\rho_x\rho^{-1/2}\rho_x\right) = \text{Pr}(X=x)Tr \left[ \left(\rho^{-1/4}\rho_x\rho^{-1/4}\right)\left( \rho^{-1/4}\rho_x\rho^{-1/4} \right)\right] = \text{Pr}(X=x)Tr\left( {\hat u}_x^\dagger {\hat u}_x \right) \equiv \text{Pr}(X=x)\left( {\hat u}_x | {\hat u}_x \right)$$ $$Tr(F_x\rho_y) = \text{Pr}(X=x)Tr\left( \rho^{-1/2}\rho_x\rho^{-1/2}\rho_y\right) = \text{Pr}(X=x)Tr\left( {\hat u}_x^\dagger {\hat u}_y \right) \equiv \text{Pr}(X=x) \left( {\hat u}_x | {\hat u}_y \right)$$ Now play with the scalar products and get first a Cauchy-Schwartz inequality, $$\left( {\hat u}_x | {\hat u}_y \right) \le \sqrt{ \left( {\hat u}_x | {\hat u}_x \right) \left( {\hat u}_y | {\hat u}_y \right)}$$

This is not quite what we want, but notice now two things:

1) From $\rho = \sum_x{\text{Pr}[X=x]\;\rho_x}$ we have $$\rho^{-1/4} \rho\; \rho^{-1/4} \equiv \rho^{1/2} = \sum_x{\text{Pr}[X=x] \;{\hat u}_x}$$ wherefrom $$\rho = \sum_{x,y}{\text{Pr}[X=x]\;\text{Pr}[X=y]\;{\hat u}_x^\dagger {\hat u}_y}$$ and $$Tr\rho \equiv 1 = \sum_{x,y}{\text{Pr}[X=x]\;\text{Pr}[X=y]\;\left({\hat u}_x |{\hat u}_y\right)}$$

2) For any $x, y$ let $\rho_x = {\hat \gamma}_x {\hat \gamma}_x^\dagger$, $\rho_y = {\hat\gamma}_y {\hat\gamma}_y^\dagger$. We then have $$\left({\hat u}_x |{\hat u}_y\right) \equiv Tr\left( \rho^{-1/2}\rho_x\rho^{-1/2}\rho_y\right) = Tr\left( \rho^{-1/2}{\hat\gamma}_x {\hat\gamma}_x^\dagger\rho^{-1/2}{\hat\gamma}_y {\hat\gamma}_y^\dagger\right) = Tr \left({\hat\gamma}_x^\dagger \rho^{-1/2} {\hat\gamma}_y {\hat\gamma}_y^\dagger \rho^{-1/2}{\hat\gamma}_x \right) =\\ = Tr \left[\left({\hat\gamma}_y^\dagger \rho^{-1/2}{\hat\gamma}_x \right)^\dagger \left({\hat\gamma}_y^\dagger \rho^{-1/2}{\hat\gamma}_x \right)\right] \ge 0$$

From (1) and (2) it follows necessarily that $$0 \le \left({\hat u}_x |{\hat u}_y\right) \le 1\;\;\; \forall \;x,y$$ and in particular $$0 \le \left({\hat u}_y |{\hat u}_y\right) \le 1\;\;\; \forall \;y$$ Taking this back into the Cauchy-Schwartz inequality we are left with $$\left( {\hat u}_x | {\hat u}_y \right) \le \sqrt{ \left( {\hat u}_x | {\hat u}_x \right) \left( {\hat u}_y | {\hat u}_y \right)} \le \sqrt{ \left( {\hat u}_x | {\hat u}_x \right)}$$ and then $$\left(Pr[X=x] \left( {\hat u}_x | {\hat u}_y \right) \right)^2 \le Pr[X=x] \left( {\hat u}_x | {\hat u}_y \right)^2 \le Pr[X=x] \left( {\hat u}_x | {\hat u}_x \right)$$ So finally we arrive at $$\left[ Tr\left(F_x\rho_y\right) \right]^2 \le Tr\left(F_x \rho_x\right)$$ as desired.

Would be nice to figure out if indeed $Tr\left(F_x\rho_y\right) \le Tr\left(F_x \rho_x\right)$, maybe somebody else can chip in?

• Thank you for your answer, however note that $\hat{u}_x = \sqrt{Pr[X=x]}\rho^{-1/4}\rho_x \rho^{-1/4}$ and $\hat{u}_y = \sqrt{Pr[X=x]}\rho^{-1/4}\rho_y \rho^{-1/4}$ so $(\hat{u}_x,\hat{u}_x)=tr(F_x \rho_x)$ but this is not the case for $\hat{u}_y$. If it can be shown that $(\hat{u}_y,\hat{u}_y) \le 1$ then it would also be great, hence "losing" only a square root factor. This is the situation I was in prior to asking the question. – Daniel86 Mar 25 '16 at 10:55
• This is not an answer to the question, and I strongly doubt it is a step towards one (it is certainly not "pretty close"!). Namely, since Cauchy-Schwarz is tight, this would actually suggest the inequality is wrong! The point is that you have never used that $\rho$ has a relation to the $\rho_x$, and without doing so, you will never succeed (indeed, it is trivial to write down counterexamples). – Norbert Schuch Mar 25 '16 at 11:21
• @Daniel86 Right, forgot the $Pr[X=x]$ factor. I am out for the day, so I'll have to take a look later, but $({\hat u}_y, {\hat u}_y) \le 1$ looks feasible at first sight. – udrv Mar 25 '16 at 15:11
• @NorbertSchuch "it is trivial to write a counterexample": I don't understand. Counterex. to the ineq. in the answer? That would be countered. to Cauchy-Schwartz? If countered. to ineq. in OP then that would be an answer in itself, no? – udrv Mar 25 '16 at 15:14
• I wanted to say "it is trivial to write a counterexample to the original ineq. if you do not make use of the relation of $\rho$ and the $\rho_x$" -- which you don't. – Norbert Schuch Mar 25 '16 at 17:27