Ensemble state identification from ensemble state distinction

Question

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.

Answer 1

Your idea is essentially correct. I will just expand it a bit:

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.