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.


1 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.

  • $\begingroup$ 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$. $\endgroup$ Commented Mar 18, 2023 at 6:36
  • $\begingroup$ 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? $\endgroup$ Commented Mar 20, 2023 at 12:29
  • $\begingroup$ 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... $\endgroup$ Commented Mar 23, 2023 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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