# How to discriminate between $N$ states drawn from one of two ensembles?

Consider the following quantum discrimination problem:

Suppose, there are two sets of states, $$P = \{ \rho_i \}$$ and $$Q = \{\sigma_i\}$$. Both Alice and Bob know which states are in each set. We can further assume that, the sets don't have any state in common, i.e, $$P\cap Q = \emptyset$$.

Alice chooses $$N$$ states from one of the sets, and gives all of them to Bob (she is allowed to choose one state multiple number of times). Bob doesn't know which set Alice chose, but he is promised that all of the states that he is given belong to the same set (although, all the states might not be the same). Given that, Bob has complete knowledge of the sets $$P$$ and $$Q$$, and that he is allowed to perform any generalized measurement on the $$N$$ states, what is the maximum probability of Bob guessing the correct set? What is the optimal (measurement) strategy that Bob should use ?

Aside:
One might need to make some further assumptions to answer this question. Suppose, one may assume that Alice chooses sets $$P$$ and $$Q$$ with probabilities $$p$$ and $$q$$, and, that she chooses the state $$\rho_i$$ given that she chose $$P$$ with probability $$p(i|P)$$, etc. I am not sure if the question can be answered if one assumes that Alice doesn't follow an underlying probability distribution.

Special Case:
If $$P$$ and $$Q$$ each have only one element $$\rho$$ and $$\sigma$$, and Alice is equally likely to chose either set, then the maximum guessing probability is known from the Helstrom Bound of standard Quantum State Discrimination as - $$p_{\rm max} = \frac{1}{2} + \frac{1}{2}||\rho^{\otimes N} - \sigma^{\otimes N}||_1$$ where, $$||A||_1$$ is the trace-norm of $$A$$.

Generalization:
What would be the answer if $$P\cap Q \neq \emptyset$$ ?

Edit:
As pointed out below, assuming the ensembles are $$\{ (p_i, \rho_i) \}, \{ (q_i, \sigma_i) \}$$, then the samples that Bob gets would be from the states $$\rho[\mathbf{p}] = \sum_i p_i\rho_i, \quad \sigma[\mathbf{q}] = \sum_i q_i\rho_i$$ ($$\mathbf{p} = [p_1 \; p_2\; \ldots], \mathbf{q} = [q_1 \; q_2\; \ldots]$$). And, if the sets are chosen with equal probability, then - $$p_{\rm max}(\mathbf{p}, \mathbf{q}) = \frac{1}{2} + \frac{1}{2}||\rho[\mathbf{p}]^{\otimes N} - \sigma[\mathbf{q}]^{\otimes N}||_1$$

How could we approach the problem if Alice can change her probability distribution on the fly ?

Cross-posted on physics.SE

• I don't think whether the sets intersect is that crucial to the answer. You could have them not intersect but contain arbitrarily close states and you'd get analogous answers you would if they had element in common. Also, in the case of a single extraction, the "discrimination between ensembles" problem should be equivalent to discriminating between two states, each one being the average of the states in each ensemble. Feel like there should be a similar redaction in this case (though you have to consider extractions of $N$ states from each ensemble)
– glS
Aug 4 at 8:25

Unless I'm mistaken, your special case is also the solution to the generalization, up to the fact that you have to redefine $$\rho$$ and $$\sigma$$.

Forget about $$Q$$ for now. If Alice gives Bob one copy of a state unknown to him from $$P$$, then the density matrix he gets is: $$\rho=\underset{\rho_i\in P}{\mathbb{E}}\left[\rho_i\right]=\sum_{i=1}^{|P|}p_i\rho_i$$ where $$p_i$$ is the probability of picking $$\rho_i$$.

Now, Alice draws and gives Bob $$N-1$$ other states like this one. The density matrix that Bob will deal with is simply $$\rho^{\otimes N}$$. However, this assumes that the samples are i.i.d. If they are only independent, it's still easy: you still have to consider the tensor product of the different density matrices. If they're not independent however, I'm not sure much can be said. For instance, if Alice draws one state at random and then gives Bob $$N$$ copies of this state, then the density matrix is: $$\underset{\rho_i\in P}{\mathbb{E}}\left[\rho_i^{\otimes N}\right]=\sum_{i=1}^{|P|}p_i\rho_i^{\otimes N}\neq\rho^{\otimes N}$$

However, I think it can be shown using quantum information theory that $$\rho$$ is the worst case for Bob if he knows the probability for each state to be selected: it's basically the density matrix corresponding to $$N$$ states drawn from $$P$$ with a given law for each sample. If Bob additionally doesn't know the law, he will just set $$p_i=\frac{1}{|P|}$$.

All in all, if the samples are drawn independentely, then Bob's probability of winning is $$\frac12+\frac12T\left(\rho^{\otimes N},\sigma^{\otimes N}\right)$$ where $$T$$ is the trace distance and $$\sigma$$ is defined the same way as $$\rho$$ using $$Q$$. If the samples are not drawn independently, then this quantity should upper-bound the real probability of winning, though that would have to be proven formally.

Note that nowhere did we use $$P\cap Q=\varnothing$$. This however assumes that Alice chooses between $$P$$ and $$Q$$ with the same probability.

• Hmm... makes sense. How could we approach the problem if Alice can change the distributions $\mathbf{p}, \mathbf{q}$ on the fly ? Average over all $(\mathbf{p}, \mathbf{q})$ ? What would be the optimal measurement strategy in that case ? Aug 5 at 16:04
• @SowmitraDas You mean unbeknownst to Bob? Well in that case you'd have to average over all possible distributions yes, but this will probably be equivalent to a simple uniform distribution Aug 6 at 13:44