# Ensemble state identification from ensemble state distinction

I am trying to derive Fact 5. in paper 1:

Let $$\mathscr{E}=\{\sigma_1,.., \sigma_m\}$$ be an ensemble of quantum states in $$\mathbb{C}^n$$. If there is a POVM $$\mathscr{M}$$ for the state distinction problem with distinguishing power $$\delta$$* for $$\mathscr{E}$$, then there is a single register state identification procedure $$\mathscr{A}$$ for $$\mathscr{E}$$ that needs $$t=\mathscr{O}\big(\frac{\log m}{\delta^2}\big)$$ copies of the unknown $$\sigma\in\mathscr{E}$$.

*A POVM $$\mathscr{M}$$ has distinguishing power $$\delta$$ for the ensemble $$\mathscr{E}$$ if $$||\mathscr{M}(\sigma_i)-\mathscr{M}(\sigma_j)||_1 \leq \delta$$ for all $$1 \leq i < j \leq m$$.

There is a proof sketch in the paper but it seems fairly dense to me...

Basically, first we apply the measurement $$\mathscr{M}$$ on each of the $$t$$ copies of the unknown state $$\sigma$$ which could be any of the states in the given ensemble $$\mathscr{E}$$ to obtain the measurement statistics/data. Then, assuming that the unknown state is either of a pair of states $$\sigma_i,~ \sigma_j$$, where $$1 \leq i < j \leq m$$, we perform a maximum likelihood estimation procedure on the measurement data. And repeat this classical post-processing (on the data obtained by measuring the unknown state) $$m-1$$ times.

At each iterative step of maximum likelihood estimation over a pair of states, the probability of correctly identifying the state is said to be at least $$1-\frac{1}{4m}$$. The author says that one can obtain this probability via a standard Chernoff bound but I am unable to see how except that since $$t=\mathscr{O}\big(\frac{\log m}{\delta^2}\big)$$, it implies $$|t|\leq M\frac{\log m}{\delta^2}$$, for $$M>0$$. This would give

$$-t \geq -M\frac{\log m}{\delta^2} \implies 1-\frac{t\delta^2}{4} \geq 1-M \frac{\log m}{4}$$.

As $$\log m > \frac{1}{m}$$ for all $$m\geq 2$$ and $$M>0$$, we have

$$1-\frac{t\delta^2}{4} \geq 1-\frac{1}{4m}$$.

The left hand side above looks like an approximation for $$e^{-\frac{t\delta^2}{4}}$$ which might be seen as some kind of Chernoff bound...

The question is what is the event space when talking of a Chernoff bound.

Let $$1_{A}$$ denote the indicator random variable that takes value $$1$$ on event $$A$$ and $$0$$ otherwise. Let $$\mathcal{M}$$ be the POVM that works for the $$\delta$$-state distinction with $$\{ M_k\}_{k=1}^m$$ as its POVM elements. We apply $$\mathcal{M}$$ on $$t$$ independent copies of the unknown state (which can eithe be $$\sigma_i$$ or $$\sigma_j$$). This leads to $$t$$ iid random varibles, say $$X^{(l)}_1,..,X^{(l)}_t$$, for $$l$$ to be $$i$$ or $$j$$, where the distribution of any $$X^{(l)}$$ is $$\{Tr[M_k \sigma_l]\}_{k=1}^m$$. Now consider the indicator random variables $$1_{X^{(i)}_u \neq i}$$ for $$u=\{1, \ldots, t\}$$ (a similar construction holds for X^{(j)}). Maximum likelihood criteria just asserts that if the number of occurrences of $$i$$ in the measurement outcome is greater than the number of occurrences of $$j$$ the decide that the unknown state was $$\sigma_i$$ else $$\sigma_j$$. Thus the error probability is equivalent to finding the probability of the event that $$\Sigma_{u=1}^t 1_{X^{(i)}_u \neq i} > t/2$$. Now the ususal Chernoff bound for the sum of indicator random variables establishes the result. (A sketch: $$\mathbb{E}_{X^{(i)}} \left[ \frac{\Sigma_{u=1}^t 1_{X^{(i)}_u \neq i}}{t}\right]=1-Tr[M_i \sigma_i] (:=p_i, say)$$ and use $$Pr \left( \left| \Sigma_{u=1}^t 1_{X^{(i)}_u \neq i} - t p_i\right| > \delta/2 \right) \leq \textrm{const.}e^{-\frac{tp_i \delta^2}{8}}$$) and for $$t=\Omega \left( \frac{\log m}{\delta^2} \right)$$ the error probability turns out to be at most $$\textrm{const.} \frac{1}{8m}$$. A similar Chernoff bound holds for random variables $$X^{(j)}$$. Now a union bound gives the over all error probability of at most $$\textrm{const.} \frac{1}{4m}$$. This over all probability of correct detection is $$1-O(\frac{1}{4m})$$. The rest of argument is as in the paper.
• Just to add, for clarity: The error corresponds to the events when $\sigma$ was $\sigma_i$ but you said $\sigma_j$ and when it was $\sigma_j$ you said $\sigma_i$. Hence, a factor 2 from the union bound gives us $1/4m$. Mar 18 at 6:36
• Just a quick question about your proof sketch even though this may not affect the main argument: the way you've constructed the POVM seems like unambiguous discrimination, i.e. $tr(M_k \rho_i) = 0$ and hence each outcome $k$ uniquely corresponds to a particular state $\rho_k$? Can we always do this? As in decompose the given POVM this way? Mar 20 at 12:29
• So, one can always group the elements of a POVM into two outcomes: one that concludes the state is $\rho$ or not since we are distinguishing a pair of states each time (For details, see Definition 1 in Ref: link.springer.com/article/10.1007/s00220-009-0890-5). And then, I guess, we build the corresponding POVM for an ensemble as a union of these two outcome POVMs... Mar 23 at 6:51