The Operational Meaning of Min- and Max-Entropy

In this paper, we show that the conditional min-entropy $H_{min}(A vert B)$ of a bipartite state $rho_{A B}$ is directly related to the maximum achievable overlap with a maximally entangled state if only local actions on the $B$-part of $rho_{A B}$ are allowed. In the special case where $A$ is classical, this overlap corresponds to the probability of guessing $A$ given $B$. In a similar vein, we connect the conditional max-entropy $H_{max}(A vert B)$ to the maximum fidelity of $rho_{AB}$ with a product state that is completely mixed on $A$. In the case where $A$ is classical, this corresponds to the security of $A$ when used as a secret key in the presence of an - adversary holding $B$. Because min- and max-entropies are known to characterize information-processing tasks such as randomness extraction and state merging, our results establish a direct connection between these tasks and basic operational problems. For example, they imply that the (logarithm of the) probability of guessing $A$ given $B$ is a lower bound on the number of uniform secret bits that can be extracted from $A$ relative to an adversary holding $B$.