# Is the quantum state discrimination success probability always $\lambda_0\langle\mu(0),\rho_0\rangle+\lambda_1\langle\mu(1),\rho_1\rangle$?

Consider the standard quantum state discrimination setup: Alice sends Bob either $$\rho_0$$ or $$\rho_1$$. She picks $$\rho_0$$ and $$\rho_1$$ with probabilities $$\lambda_0$$ and $$\lambda_1$$, respectively. Bob performs some two-outcome measurement $$\mu$$ on the state he receives and has to decide whether Alice sent $$\rho_0$$ or $$\rho_1$$. We assume Bob knows the possible states $$\rho_0,\rho_1$$, as well as the probabilities $$\lambda_0,\lambda_1$$.

Denote with $$p_i(b)\equiv p_i^\mu(b)\equiv \langle \mu(b),\rho_i\rangle\equiv \mathrm{Tr}(\mu(b)\rho_i)$$ the probability of Bob observing the outcome $$b\in\{0,1\}$$ when the state he received is $$\rho_i$$. If Bob measures the outcome $$b$$, his best guess is that he received the $$\rho_i$$ with $$i$$ maximising $$\lambda_i p_i(b)$$. This follows from simple Bayesian considerations, fully analogous to the classical state discrimination scenario discussed in this other question.

Consequently, when Bob finds the outcome $$b$$, the probability of his guess being correct is $$p_{\rm correct}(b) = \frac{\max_i \lambda_i p_i(b)}{p(b)} = \frac{\max_i \lambda_i p_i(b)}{\sum_i \lambda_i p_i(b)}.$$ The overall success probability, estimated before knowing the measurement outcome, is therefore $$p_{\rm correct} = \sum_b p(b) p_{\rm correct}(b) = \sum_b \max_i \lambda_i p_i(b).\tag X$$

This is all nice and well. However, the success probability for this type of scenario is usually given (e.g. in Watrous' TQI, section 3.1) as the expression: $$p_{\rm correct}'=\sum_{i\in\{0,1\}} \lambda_i p_i(i).\tag Y$$ This expression is intuitively clear: if Bob receives $$\rho_i$$, which happens with probability $$\lambda_i$$, then he correctly guesses that the state was $$i$$ with probability $$p_i(i)$$.

Nonetheless, I wonder: are (X) and (Y) always equivalent? I suppose that if we assume that the best guess changes with the observed outcome (e.g. if Bob finds $$b=0$$ then his best guess is $$i=0$$, and if he finds $$b=1$$ his best guess is $$i=1$$), then (X) and (Y) are equivalent up to a relabeling of the POVM. But can we always assume this? Isn't it possible that there are scenarios in which, regardless of the observed outcome, Bob's best guess should always be the same?

Admittedly, this sounds like a weird scenario, but I can't tell whether it can be ruled out altogether (well except in the trivial case in which $$\rho_0=\rho_1$$). It amounts to asking whether $$\underbrace{\lambda_0 p_0(0)>\lambda_1 p_1(0)}_{\text{measuring 0 best guess is \rho_0}} \Longrightarrow \underbrace{\lambda_0 p_0(1) < \lambda_1 p_1(1)}_{\text{measuring 1 best guess is \rho_1}}.$$ Because $$p_i(0)+p_i(1)=0$$, this is true for $$\lambda_0=\lambda_1$$, but I'm not sure it holds for the general case.

• Ignoring all the context of the question and purely focusing on the implication with the probabilities, some quick numerics suggests that $\text{LHS}\implies \text{RHS}$ when $\lambda_0 \leq 1/2$. Moreover it would seem that for $\lambda_0 \geq 1/2$ we would have $\text{RHS} \implies \text{LHS}$. – Rammus Feb 24 at 20:20
• In fact here's the above comment analytically. If $\lambda p_0 > (1-\lambda) p_1$ then $-\lambda p_0 < -(1-\lambda) p_1$. Adding $\lambda$ to both sides we get $\lambda (1-p_0) < \lambda - (1-\lambda) p_1 \leq (1-\lambda) - (1-\lambda)p_1 = (1-\lambda) (1-p_1)$. Where on the last inequality we used $\lambda \leq 1/2$. The other implication should follow from a similar argument. Here, I've made some shorthand notation: $\lambda = \lambda_0, p_0 = p_0(0), p_1 = p_1(0)$. – Rammus Feb 24 at 20:35

Yes. Expression (X) is in principle more general, but it boils down to doing classical post-processing of the outcomes, and this can always be included in the POVM. So as long as you do optimize over the POVM, expression (Y) is completely general.

There are four possibilities:

1. $$\lambda_0 p_0(0)>\lambda_1 p_1(0)$$ and $$\lambda_1 p_1(1)>\lambda_0 p_0(1)$$. Boring case, where no post-processing is needed, expressions are equivalent.
2. $$\lambda_0 p_0(0)<\lambda_1 p_1(0)$$ and $$\lambda_1 p_1(1)<\lambda_0 p_0(1)$$. In this case you should always guess the opposite of your outcome. Just relabel your POVM elements, $$\mu(0)$$ becomes $$\mu(1)$$ and vice-versa.
3. $$\lambda_0 p_0(0)>\lambda_1 p_1(0)$$ and $$\lambda_1 p_1(1)<\lambda_0 p_0(1)$$. In this case you should always guess 0, regardless of your outcome, so you assign $$\mu(0) = I$$ and $$\mu(1) = 0$$.
4. $$\lambda_0 p_0(0)<\lambda_1 p_1(0)$$ and $$\lambda_1 p_1(1)>\lambda_0 p_0(1)$$. In this case you should always guess 1, regardless of your outcome, so you assign $$\mu(0) = 0$$ and $$\mu(1) = I$$.

Possibilities 3 and 4 can indeed occur, so the implication you wrote down is false. Take for example $$p_0(0) = p_1(1) = 3/4$$, $$\lambda_0 = 1-10^{-5}$$, and $$\lambda_1 = 10^{-5}$$. In this case you should always guess 1, regardless of your outcome (of course in reality you would just use a better POVM so that your measurement outcomes actually matter).

• but that's the thing, couldn't you still have options 3 or 4 for the optimal POVM? This would be a situation in which even with the optimal measurement your best guess is to always guess $\rho_0$ (or $\rho_1$). In such a case the probability of being correct would be $\lambda_0 p_0(0)+\lambda_0 p_0(1) = \lambda_0$, which might not be equal to $\sum_i \lambda_i p_i(i)$. After all, if $\lambda_0\approx 1$, such strategy would work pretty well – glS Feb 25 at 13:20
• no, because if this is the case then the optimal POVM will already tell you to always guess 0 (or 1), no relabelling necessary. – Mateus Araújo Feb 25 at 13:43
• I don't follow. I agree that no relabelling is necessary as you always guess the same, but isn't the expression $\sum_i\lambda_i p_i(i)$ invalid in this case? – glS Feb 25 at 14:27
• Why should it be invalid? If the POVM tells you to always guess 0 then $\sum_i\lambda_i p_i(i) = \lambda_0$, which is in fact the probability of success. – Mateus Araújo Feb 25 at 14:34
• because the probability of success is $\lambda_0 p_0(0)+\lambda_1 p_1(1)$ if the best guesses are $\rho_0$ and $\rho_1$ when the measurement outcome is $0$ and $1$, respectively. If the best guess is, say, $\rho_0$ regardless of measurement outcome, then wouldn't the success probability read $\lambda_0 p_0(0) + \lambda_0 p_0(1)=\lambda_0$?. – glS Feb 25 at 14:45