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.



Your Answer

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