Min-entropy

The min-entropy, in information theory, is the smallest of the Rényi family of entropies, corresponding to the most conservative way of measuring the unpredictability of a set of outcomes, as the negative logarithm of the probability of the "most likely" outcome. The various Rényi entropies are all equal for a uniform distribution, but measure the unpredictability of a nonuniform distribution in different ways. The min-entropy is never greater than the ordinary or Shannon entropy (which measures the average unpredictability of the outcomes) and that in turn is never greater than the Hartley or max-entropy, defined as the logarithm of the "number" of outcomes with nonzero probability.
As with the classical Shannon entropy and its quantum generalization, the von Neumann entropy, one can define a conditional version of min-entropy. The conditional quantum min-entropy is a one-shot, or conservative, analog of conditional quantum entropy.
To interpret a conditional information measure, suppose Alice and Bob were to share a bipartite quantum state formula_1. Alice has access to system formula_2 and Bob to system formula_3. The conditional entropy measures the average uncertainty Bob has about Alice's state upon sampling from his own system. The min-entropy can be interpreted as the distance of a state from a maximally entangled state.
This concept is useful in quantum cryptography, in the context of privacy amplification (See for example ).
Definitions.
Definition: Let formula_1 be a bipartite density operator on the space formula_5. The min-entropy of formula_2 conditioned on formula_3 is defined to be
where the infimum ranges over all density operators formula_9 on the space formula_10. The measure formula_11 is the maximum relative entropy defined as
The smooth min-entropy is defined in terms of the min-entropy.
where the sup and inf range over density operators formula_14 which are formula_15-close to formula_16. This measure of formula_15-close is defined in terms of the purified distance
where formula_19 is the fidelity measure.
These quantities can be seen as generalizations of the von Neumann entropy. Indeed, the von Neumann entropy can be expressed as
This is called the fully quantum asymptotic equipartition theorem.
The smoothed entropies share many interesting properties with the von Neumann entropy. For example, the smooth min-entropy satisfy a data-processing inequality: 
Operational interpretation of smoothed min-entropy.
Henceforth, we shall drop the subscript formula_22 from the min-entropy when it is obvious from the context on what state it is evaluated.
Min-entropy as uncertainty about classical information.
Suppose an agent had access to a quantum system formula_3 whose state formula_24 depends on some classical variable formula_25. Furthermore, suppose that each of its elements formula_26 is distributed according to some distribution formula_27. This can be described by the following state over the system formula_28.
where formula_30 form an orthonormal basis. We would like to know what the agent can learn about the classical variable formula_26. Let formula_32 be the probability that the agent guesses formula_25 when using an optimal measurement strategy
where formula_35 is the POVM that maximizes this expression. It can be shown that this optimum can be expressed in terms of the min-entropy as
If the state formula_37 is a product state i.e. formula_38 for some density operators formula_39 and formula_40, then there is no correlation between the systems formula_25 and formula_3. In this case, it turns out that formula_43
Min-entropy as distance from maximally entangled state.
The maximally entangled state formula_44 on a bipartite system formula_5 is defined as
where formula_47 and formula_48 form an orthonormal basis for the spaces formula_2 and formula_3 respectively.
For a bipartite quantum state formula_1, we define the maximum overlap with the maximally entangled state as
where the maximum is over all CPTP operations formula_53 and formula_54 is the dimension of subsystem formula_2. This is a measure of how correlated the state formula_1 is. It can be shown that formula_57. If the information contained in formula_2 is classical, this reduces to the expression above for the guessing probability.
Proof of operational characterization of min-entropy.
The proof is from a paper by König, Schaffner, Renner in 2008. It involves the machinery of semidefinite programs. Suppose we are given some bipartite density operator formula_1. From the definition of the min-entropy, we have
This can be re-written as
subject to the conditions
We notice that the infimum is taken over compact sets and hence can be replaced by a minimum. This can then be expressed succinctly as a semidefinite program. Consider the primal problem
This primal problem can also be fully specified by the matrices formula_67 where formula_68 is the adjoint of the partial trace over formula_2. The action of formula_68 on operators on formula_3 can be written as
We can express the dual problem as a maximization over operators formula_73 on the space formula_74 as
Using the Choi–Jamiołkowski isomorphism, we can define the channel formula_53 such that
where the bell state is defined over the space formula_80. This means that we can express the objective function of the dual problem as
as desired.
Notice that in the event that the system formula_2 is a partly classical state as above, then the quantity that we are after reduces to
We can interpret formula_53 as a guessing strategy and this then reduces to the interpretation given above where an adversary wants to find the string formula_26 given access to quantum information via system formula_3.