  We consider the problem of designing an optimal quantum detector to minimize
the probability of a detection error when distinguishing between a collection
of quantum states, represented by a set of density operators. We show that the
design of the optimal detector can be formulated as a semidefinite programming
problem. Based on this formulation, we derive a set of necessary and sufficient
conditions for an optimal quantum measurement. We then show that the optimal
measurement can be found by solving a standard (convex) semidefinite program
followed by the solution of a set of linear equations or, at worst, a standard
linear programming problem. By exploiting the many well-known algorithms for
solving semidefinite programs, which are guaranteed to converge to the global
optimum, the optimal measurement can be computed very efficiently in polynomial
time.
  Using the semidefinite programming formulation, we also show that the rank of
each optimal measurement operator is no larger than the rank of the
corresponding density operator. In particular, if the quantum state ensemble is
a pure-state ensemble consisting of (not necessarily independent) rank-one
density operators, then we show that the optimal measurement is a pure-state
measurement consisting of rank-one measurement operators.
