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 $\rho_$. Alice has access to system $A$ and Bob to system $B$. 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 $\rho_$ be a bipartite density operator on the space $\mathcal_A \otimes \mathcal_B$. The min-entropy of $A$ conditioned on $B$ is defined to be

:::$H_(A, B)_ \equiv -\inf_D_(\rho_\, I_A \otimes \sigma_B)$

where the infimum ranges over all density operators $\sigma_B$ on the space $\mathcal_B$. The measure $D_$ is the maximum relative entropy defined as

:::$D_(\rho\, \sigma) = \inf_\$

The smooth min-entropy is defined in terms of the min-entropy.

:::$H_^(A, B)_ = \sup_ H_(A, B)_$

where the sup and inf range over density operators $\rho'_$ which are $\epsilon$-close to $\rho_$. This measure of $\epsilon$-close is defined in terms of the purified distance

:::$P(\rho,\sigma) = \sqrt$

where $F(\rho,\sigma)$ 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

:::$S(A, B)_ = \lim_\lim_\fracH_^(A^n, B^n)_~.$
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:
:::$H_^(A, B)_ \geq H_^(A, BC)_~.$

Operational interpretation of smoothed min-entropy

Henceforth, we shall drop the subscript $\rho$ 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 $B$ whose state $\rho_^x$ depends on some classical variable $X$. Furthermore, suppose that each of its elements $x$ is distributed according to some distribution $P_X(x)$. This can be described by the following state over the system $XB$.

:::$\rho_ = \sum_x P_X (x) , x\rangle\langle x, \otimes \rho_^x ,$

where $\$ form an orthonormal basis. We would like to know what the agent can learn about the classical variable $x$. Let $p_g(X, B)$ be the probability that the agent guesses $X$ when using an optimal measurement strategy

:::$p_g(X, B) = \sum_x P_X(x)tr(E_x \rho_B^x) ,$

where $E_x$ is the POVM that maximizes this expression. It can be shown that this optimum can be expressed in terms of the min-entropy as

:::$p_g(X, B) = 2^~.$

If the state $\rho_$ is a product state i.e. $\rho_ = \sigma_X \otimes \tau_B$ for some density operators $\sigma_X$ and $\tau_B$, then there is no correlation between the systems $X$ and $B$. In this case, it turns out that $2^ = \max_x P_X(x)~.$

Min-entropy as distance from maximally entangled state

The maximally entangled state $, \phi^+\rangle$ on a bipartite system $\mathcal_A \otimes \mathcal_B$ is defined as

:::$, \phi^+\rangle_ = \frac \sum_ , x_A\rangle , x_B\rangle$

where $\$ and $\$ form an orthonormal basis for the spaces $A$ and $B$ respectively.
For a bipartite quantum state $\rho_$, we define the maximum overlap with the maximally entangled state as

:::$q_(A, B) = d_A \max_ F\left((I_A \otimes \mathcal) \rho_, , \phi^+\rangle\langle \phi^, \right)^2$

where the maximum is over all CPTP operations $\mathcal$ and $d_A$ is the dimension of subsystem $A$. This is a measure of how correlated the state $\rho_$ is. It can be shown that $q_c(A, B) = 2^$. If the information contained in $A$ 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.John Watrous, Theory of quantum information, Fall 2011, course notes, https://cs.uwaterloo.ca/~watrous/CS766/LectureNotes/07.pdf Suppose we are given some bipartite density operator $\rho_$. From the definition of the min-entropy, we have

:::$H_(A, B) = - \inf_ \inf_ \~.$

This can be re-written as

:::$-\log \inf_ \operatorname(\sigma_B)$

subject to the conditions

:::$\sigma_B \geq 0$
:::$I_A \otimes \sigma_B \geq \rho_~.$

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

:::$\text\operatorname (\sigma_B)$
:::$\text I_A \otimes \sigma_B \geq \rho_$
::::::::$\sigma_B \geq 0~.$

This primal problem can also be fully specified by the matrices $(\rho_,I_B,\operatorname^*)$ where $\operatorname^*$ is the adjoint of the partial trace over $A$. The action of $\operatorname^*$ on operators on $B$ can be written as

:::$\operatorname^*(X) = I_A \otimes X~.$

We can express the dual problem as a maximization over operators $E_$ on the space $AB$ as

:::$\text\operatorname(\rho_E_)$
:::$\text \operatorname_A(E_) = I_B$
::::::::$E_ \geq 0~.$

Using the Choi–Jamiołkowski isomorphism, we can define the channel $\mathcal$ such that
:::$d_A I_A \otimes \mathcal^(, \phi^\rangle\langle\phi^, ) = E_$
where the bell state is defined over the space $AA'$. This means that we can express the objective function of the dual problem as

:::$\langle \rho_, E_ \rangle = d_A \langle \rho_, I_A \otimes \mathcal^ (, \phi^+\rangle\langle \phi^+, ) \rangle$
::::::::$= d_A \langle I_A \otimes \mathcal(\rho_), , \phi^+\rangle\langle \phi^+, ) \rangle$
as desired.

Notice that in the event that the system $A$ is a partly classical state as above, then the quantity that we are after reduces to
:::$\max P_X(x) \langle x , \mathcal(\rho_B^x), x \rangle~.$
We can interpret $\mathcal$ as a guessing strategy and this then reduces to the interpretation given above where an adversary wants to find the string $x$ given access to quantum information via system $B$.

See also

* von Neumann entropy
* Generalized relative entropy
* max-entropy

References

{{reflist

Quantum mechanical entropy