<p>As you mention, it is possible to determine the optimal average success probability numerically, which can be done efficiently via semidefinite programming (see e.g. <a href="http://arxiv.org/abs/quant-ph/0205178">this paper</a> by Eldar, Megretski and Verghese or <a href="http://www.cs.uwaterloo.ca/~watrous/quant-info/lecture-notes/20.pdf">these lecture notes</a> by John Watrous), but no closed form expression is known.</p>

<p>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 <a href="http://arxiv.org/abs/0711.2012">lower bounded</a> by $\frac{1}{N^2} \sum_{i&gt;j} F(\rho_i,\rho_j)$, and <a href="http://arxiv.org/abs/quant-ph/0004088">upper bounded</a> by $\frac{2}{N} \sum_{i&gt;j} F(\rho_i,\rho_j)^{1/2}$.</p>

<p>There is also another <a href="http://arxiv.org/abs/0707.3970">lower bound</a> known in terms of trace distance: $\frac{1}{2}(1 - \frac{1}{N(N-1)} \sum_{i&gt;j} tr|\rho_i-\rho_j|)$, which reduces to the exact Helstrom bound in the case $N=2$. See <a href="http://arxiv.org/abs/0812.2378">this paper</a> 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.</p>

CC BY-SA 3.0
2012-06-17T18:01:07.043Z
Awesome, thanks Ashley. The lower bound on error probability in terms of trace distance is pretty much exactly what I was looking for. Actually, my backup plan had I failed to get a good answer here was going to be to email you, since I know you've worked on this stuff.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-18T10:26:48.187Z
Are there any limits that work well in the limit of the probability of error being close to 1? The trace distance one seems to max out at 1/2. I'm trying the fidelity one at the moment, but I don't think I can actually calculate the fidelity in the problem I'm working on, and the bounds you give seem very sensitive to additive errors.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-18T11:05:10.747Z
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
CC BY-SA 3.0
2012-06-17T17:31:39.967Z
2012-06-17T17:31:39.967Z
Ashley Montanaro
<p>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$?</p>

<p>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$. </p>

<p>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.</p>

<p>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.</p>

<p>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. </p>

CC BY-SA 3.0
2012-06-16T18:13:42.637Z
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
CC BY-SA 3.0
2012-06-16T21:53:40.600Z
@TsuyoshiIto: Indeed, but I was guessing that this problem has been well studied and that there might be a canned result.
Joe Fitzsimons
CC BY-SA 3.0
2012-06-17T01:21:08.893Z
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
CC BY-SA 3.0
2012-06-17T06:50:33.450Z
@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
<quantum-computing><it.information-theory><quantum-information><st.statistics>
Distinguishing between $N$ quantum states
Joe Fitzsimons
# Distinguishing between $N$ quantum states

(Asked by: username_0 on 2012-06-16)

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.

**Tags:** quantum-computing, it.information-theory, quantum-information, st.statistics
> **Comments:**
> **username_1**: 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.  
> **username_0**: @TsuyoshiIto: Indeed, but I was guessing that this problem has been well studied and that there might be a canned result.  
> **username_2**: 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).]  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_3 on 2012-06-17. Score: 10 | Accepted answer

As you mention, it is possible to determine the optimal average success probability numerically, which can be done efficiently via semidefinite programming (see e.g. [this paper](http://arxiv.org/abs/quant-ph/0205178) by Eldar, Megretski and Verghese or [these lecture notes](http://www.cs.uwaterloo.ca/~watrous/quant-info/lecture-notes/20.pdf) by John Watrous), but no closed form expression is known.

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](http://arxiv.org/abs/0711.2012) by $\frac{1}{N^2} \sum\_{i>j} F(\rho\_i,\rho\_j)$, and [upper bounded](http://arxiv.org/abs/quant-ph/0004088) by $\frac{2}{N} \sum\_{i>j} F(\rho\_i,\rho\_j)^{1/2}$.

There is also another [lower bound](http://arxiv.org/abs/0707.3970) 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](http://arxiv.org/abs/0812.2378) 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.

> **Comments:**
> **username_0**: Awesome, thanks Ashley. The lower bound on error probability in terms of trace distance is pretty much exactly what I was looking for. Actually, my backup plan had I failed to get a good answer here was going to be to email you, since I know you've worked on this stuff.  
> **username_0**: Are there any limits that work well in the limit of the probability of error being close to 1? The trace distance one seems to max out at 1/2. I'm trying the fidelity one at the moment, but I don't think I can actually calculate the fidelity in the problem I'm working on, and the bounds you give seem very sensitive to additive errors.  
> **username_0**: 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$.  

---

