# Why is state discrimination possible to infidelity $\delta$ using $n=\Theta(1/\delta)$ states?

In (Haah et al. 2015), in the first section, the authors study the asymptotic behaviours of fidelity and trace distance between $$\rho^{\otimes n}$$ and $$\sigma^{\otimes n}$$ for some given pair of states $$\rho,\sigma$$. More precisely, given $$F(\rho,\sigma)\equiv \|\sqrt\rho\sqrt\sigma\|_1$$ and $$T(\rho,\sigma)\equiv \frac12\|\rho-\sigma\|_1$$, defining $$T_n\equiv T(\rho^{\otimes n},\sigma^{\otimes n})$$, observing that $$F(\rho^{\otimes n},\sigma^{\otimes n})=F(\rho,\sigma)^n$$, and using the well-known relation $$1-F \le T \le \sqrt{1-F^2},$$ we can write the asymptotic behaviour of $$T_n$$ as bounded by $$F$$ (assuming $$F$$ is sufficiently small) as follows: $$\frac12 F^{2n} \le 1-T_n \le F^n.$$ From this they infer that:

This means that $$\ln(1/F)$$ or infidelity gives nearly sharp bounds on the rate at which $$T_n$$ converges to $$1$$; the actual rate is between $$\ln(1/F)$$ and $$2\ln(1/F)$$. In particular, for fixed [state dimension] $$d$$, the state discrimination is possible to infidelity $$\delta$$ using $$n=\Theta(1/\delta)$$ copies.

I'm trying to understand more precisely what is meant by this, and how the conclusion is reached. I think the first part refers to what we get taking the log of the above relation: $$2n \log F -\log2\le \log(1-T_n) \le n \log F \\ \sim 2\log F \le \frac{\log(1-T_n)}{n} \le \log F.$$ This looks close enough to the "rate of convergence of $$T_n$$ to $$1$$ is $$O(\ln(1/F))$$", but I'm unsure about how this "rate" is defined, precisely.

The next step might follow immediately from understanding of this, but the additional unclear point about the above sentence is: what does "state discrimination is possible to infidelity $$\delta$$ with $$n$$ copies" mean exactly? Are they referring to a bound of the form: the probability that the infidelity is larger than $$\delta$$ is smaller than some constant error threshold using $$n\sim 1/\delta$$ input states? How is this connected with the previous statement about the trace distance $$T_n$$?

The statement

state discrimination is possible to infidelity 𝛿 with 𝑛 copies

is probably related to minimum error state discrimination. The minimum probability of error (while discriminating between states $$\rho$$ and $$\sigma$$) can be shown to be

$$P_{e}^{min}=\frac{1}{2}\big(1-\frac{1}{2}||\rho-\sigma||_{tr}\big)=\frac{1}{2}\big(1-T(\rho, \sigma)\big)$$,

assuming a uniform prior on $$\{\rho, \sigma\}$$.

For n-copies of the unknown state, the corresponding expression can be obtained by replacing $$\rho$$ by $$\rho^{\otimes n}$$ and $$\sigma$$ by $$\sigma^{\otimes n}$$. So, we'd get

$$P_{n,e}^{min}=\frac{1}{2}\big(1-T_n\big)$$, as per your notation. Now, infidelity $$\delta = 1-F$$, but $$1-F^n \leq T_n$$. So,

$$1-(1-\delta)^n \leq T_n = 1-2P_{n,e}^{min}$$.

Using the approximation $$(1-\delta)^n \approx 1-n\delta$$, the inequality above becomes

$$n\delta \leq 1-2P_{n,e}^{min} \equiv P_{n,e}^{min} \leq \frac12(1-n\delta)$$.