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.

  • $\begingroup$ @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. $\endgroup$ – Daniel86 Mar 24 '16 at 12:28
  • $\begingroup$ @NorbertSchuch Thank you for your comment, I hope it is more clear now. $\endgroup$ – Daniel86 Mar 24 '16 at 13:24
  • $\begingroup$ @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. $\endgroup$ – Daniel86 Mar 24 '16 at 13:41
  • $\begingroup$ @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. $\endgroup$ – Daniel86 Mar 25 '16 at 14:23
  • $\begingroup$ Of course, my mistake. Corrected. $\endgroup$ – 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.

  • $\begingroup$ 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$. $\endgroup$ – udrv Mar 30 '16 at 22:57
  • $\begingroup$ 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}}$$ $\endgroup$ – udrv Mar 30 '16 at 22:57
  • $\begingroup$ @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 ;-). $\endgroup$ – Norbert Schuch Mar 31 '16 at 7:17
  • $\begingroup$ Oy, Schwarz, got it :) As for the k-outcome, same here. But I kept loosing other factors. $\endgroup$ – 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?

  • $\begingroup$ 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. $\endgroup$ – Daniel86 Mar 25 '16 at 10:55
  • 1
    $\begingroup$ 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). $\endgroup$ – Norbert Schuch Mar 25 '16 at 11:21
  • $\begingroup$ @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. $\endgroup$ – udrv Mar 25 '16 at 15:11
  • $\begingroup$ @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? $\endgroup$ – udrv Mar 25 '16 at 15:14
  • $\begingroup$ 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. $\endgroup$ – Norbert Schuch Mar 25 '16 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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