  Error probability is a popular and well-studied optimization criterion in
discriminating non-orthogonal quantum states. It captures the threat from an
adversary who can only query the actual state once. However, when the adversary
is able to use a brute-force strategy to query the state, discrimination
measurement with minimum error probability does not necessarily minimize the
number of queries to get the actual state. In light of this, we take Massey's
guesswork as the underlying optimization criterion and study the problem of
minimum guesswork discrimination. We show that this problem can be reduced to a
semidefinite programming problem. Necessary and sufficient conditions when a
measurement achieves minimum guesswork are presented. We also reveal the
relation between minimum guesswork and minimum error probability. We show that
the two criteria generally disagree with each other, except for the special
case with two states. Both upper and lower information-theoretic bounds on
minimum guesswork are given. For geometrically uniform quantum states, we
provide sufficient conditions when a measurement achieves minimum guesswork.
Moreover, we give the necessary and sufficient condition under which making no
measurement at all would be the optimal strategy.
