11
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Jun 16, 2012 at 18:13
  • $\begingroup$ @TsuyoshiIto: Indeed, but I was guessing that this problem has been well studied and that there might be a canned result. $\endgroup$
    – Joe Fitzsimons
    Commented Jun 16, 2012 at 21:53
  • 1
    $\begingroup$ 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).] $\endgroup$
    – Adam Smith
    Commented Jun 17, 2012 at 1:21
  • 1
    $\begingroup$ @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. $\endgroup$
    – Joe Fitzsimons
    Commented Jun 17, 2012 at 6:50

1 Answer 1

Reset to default
10
$\begingroup$

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 by Eldar, Megretski and Verghese or these lecture notes 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 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Joe Fitzsimons
    Commented Jun 17, 2012 at 18:01
  • $\begingroup$ 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. $\endgroup$
    – Joe Fitzsimons
    Commented Jun 18, 2012 at 10:26
  • $\begingroup$ 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$. $\endgroup$
    – Joe Fitzsimons
    Commented Jun 18, 2012 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.