# Distinguishing between $N$ quantum states

Given a quantum state $\rho_A$ chosen uniformly at random from a set of $N$ mixed states $\rho_1 ... \rho_N$, what is the maximum average probability of correctly identifying $A$?

This problem can be turned into a two state distinguishability problem by considering the problem of distinguishing $\rho_A$ from $\rho_{B} = \frac{1}{N-1}\sum_{i\neq A}\rho_i$.

I know for two quantum states the problem has a nice solution in terms of the trace distance between the states when you minimize the maximum probability of error rather than the minimizing the average probability of error, and I was hoping that there might be something similar for this case. It is of course possible to write the probability in terms of an optimization over POVMs, but I am hoping for something where the optimization has already been performed.

I know there is a huge literature on the distinguishability of quantum states, and I've been reading through a lot of papers over the last few days trying to find the answer to this question, but I'm having trouble finding the answer to this particular variation of the problem. I'm hoping someone who knows that literature better can save me some time.

Strictly speaking, I don't need the exact probability, a good upper bound would do. However, the difference between any one state and the maximally mixed state is quite small, so the bound would have to be useful in that limit.

• Because the probability of correct answer is the maximum value of a semidefinite program, it is often useful to consider the dual to get an upper bound. – Tsuyoshi Ito Jun 16 '12 at 18:13
• @TsuyoshiIto: Indeed, but I was guessing that this problem has been well studied and that there might be a canned result. – Joe Fitzsimons Jun 16 '12 at 21:53
• Do you know if the analogous questions for classical probability distributions has a nice answer? The "trace distance" result you mention is a generalization of the use of "statistical distance" (a.k.a. "total variation distance") for classical distributions. [In the classical case, the natural strategy is to pick the distribution most likely to have generated a particular output. You can write down a closed form for its success probability, though I don't know if it can be expressed in terms of a simple quantity (such as the average distance between the distributions).] – Adam Smith Jun 17 '12 at 1:21
• @AdamSmith: It seems classically you can just weight each distribution by its probability of occurring and then pick the one most likely to give the result you observe. – Joe Fitzsimons Jun 17 '12 at 6:50

However, there are several known upper and lower bounds on the probability of error (i.e. 1 minus the average success probability). In terms of pairwise fidelities, the probability of error in your setting is known to be lower bounded by $\frac{1}{N^2} \sum_{i>j} F(\rho_i,\rho_j)$, and upper bounded by $\frac{2}{N} \sum_{i>j} F(\rho_i,\rho_j)^{1/2}$.
There is also another lower bound known in terms of trace distance: $\frac{1}{2}(1 - \frac{1}{N(N-1)} \sum_{i>j} tr|\rho_i-\rho_j|)$, which reduces to the exact Helstrom bound in the case $N=2$. See this paper for a comparison of all of these, and some other bounds too. Note that all of these bounds hold in the average-case setting where there is a prior probability distribution on the states.
• Actually, the fidelity lower bound also seems to max out at 1/2. I'm hoping for something stronger, since I want to prove the probability of error is something like $1-\epsilon$ for very small $\epsilon$. – Joe Fitzsimons Jun 18 '12 at 11:05