  We consider a special form of state discrimination in which after the
measurement we are given additional information that may help us identify the
state. This task plays a central role in the analysis of quantum cryptographic
protocols in the noisy-storage model, where the identity of the state
corresponds to a certain bit string, and the additional information is
typically a choice of encoding that is initially unknown to the cheating party.
We first provide simple optimality conditions for measurements for any such
problem, and show upper and lower bounds on the success probability. For a
certain class of problems, we furthermore provide tight bounds on how useful
post-measurement information can be. In particular, we show that for this class
finding the optimal measurement for the task of state discrimination with
post-measurement information does in fact reduce to solving a different problem
of state discrimination without such information. However, we show that for the
corresponding classical state discrimination problems with post-measurement
information such a reduction is impossible, by relating the success probability
to the violation of Bell inequalities. This suggests the usefulness of
post-measurement information as another feature that distinguishes the
classical from a quantum world.
