The Operational Meaning of Min- and Max-Entropy

By Robert T. König, Renato Renner, Christian Schaffner. IEEE Transactions on Information Theory, 2008

629 citations recorded by the source corpus.

In this paper, we show that the conditional min-entropy H min(A |B) of a bipartite state rhoAB is directly related to the maximum achievable overlap with a maximally entangled state if only local actions on the B-part of rhoAB 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 |B) to the maximum fidelity of rhoAB 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/0ad95f065f57fe26c0b8a9e6ee41c1a4c932cff1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

Citations in the corpus

Quantum randomness certified by the uncertainty principle (2014, background): “In this case, the amount of true random bits that can be extracted from the random variable Z, if one requires uniformity and independence from the environment system E, is given by the conditional min-entropy Hmin(Z|E) [1].”
From Classical to Quantum Shannon Theory (2011, background): “Rather than developing this theory in full, we point to several excellent references on the subject (Renner, 2005; Datta, 2009; Datta and Renner, 2009; Koenig et al., 2009; Tomamichel, 2016).”
Min- and Max-Relative Entropies and a New Entanglement Monotone (2008, background): “This operational interpretation, was first provided in [ 23 ] though in a somewhat different formalism.”
Performance and structure of single-mode bosonic codes (2017, background): “From yet another information theory perspective ([41], Theorem 2), the optimal FE yields the equality dFE = 2−Hmin(B|A)NS , (A6)”
Entropic uncertainty relations—a survey (2009, methodology): “…information Θ The conditional min-entropy thereby has a very intuitive interpretation as H ∞ ( X j | K Θ) = − log P guess ( X j | K Θ) , where P guess ( X j | K Θ) is the average probability that the cheating party can guess X j given K and Θ , maximized over all strategies (K¨onig et al. , 2008).”
Random numbers certified by Bell’s theorem (2009, neutral): “[21] R.”
The Quantum Reverse Shannon Theorem Based on One-Shot Information Theory (2009, background): “For a more detailed discussion of the smooth entropy formalism we refer to [12, 17, 18, 38, 39].”
An intuitive proof of the data processing inequality (2011, background): “It has become apparent in recent works [18–21] that smooth min-entropy is a relevant quantity for measuring quantum information.”
A Fully Quantum Asymptotic Equipartition Property (2008, background): “Bounds on the convergence derived from this argument will depend on the convergence of the individual terms and thus in general on the Hilbert space dimensions of and (see [3]). where and are the identity operators on and , respectively.”