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 ).

Definition for classical distributions

If $P=(p_1,...,p_n)$ is a classical finite probability distribution, its min-entropy can be defined as $H_(\boldsymbol P) = \log\frac, \qquad P_\equiv \max_i p_i.$One way to justify the name of the quantity is to compare it with the more standard definition of entropy, which reads $H(\boldsymbol P)=\sum_i p_i\log(1/p_i)$, and can thus be written concisely as the expectation value of $\log (1/p_i)$ over the distribution. If instead of taking the expectation value of this quantity we take its minimum value, we get precisely the above definition of $H_(\boldsymbol P)$.

From an operational perspective, the min-entropy equals the negative logarithm of the probability of successfully guessing the outcome of a random draw from $P$.
This is because it is optimal to guess the element with the largest probability and the chance of success equals the probability of that element.

Definition for quantum states

A natural way to generalize "min-entropy" from classical to quantum states is to leverage the simple observation that quantum states define classical probability distributions when measured in some basis. There is however the added difficulty that a single quantum state can result in infinitely many possible probability distributions, depending on how it is measured. A natural path is then, given a quantum state $\rho$, to still define $H_(\rho)$ as $\log(1/P_)$, but this time defining $P_$ as the maximum possible probability that can be obtained measuring $\rho$, maximizing over all possible projective measurements.
Using this, one gets the operational definition that the min-entropy of $\rho$ equals the negative logarithm of the probability of successfully guessing the outcome of any measurement of $\rho$.

Formally, this leads to the definition
$H_(\rho) = \max_\Pi \log \frac = - \max_\Pi \log \max_i \operatorname(\Pi_i \rho),$
where we are maximizing over the set of all projective measurements $\Pi=(\Pi_i)_i$, $\Pi_i$ represent the measurement outcomes in the POVM formalism, and $\operatorname(\Pi_i \rho)$ is therefore the probability of observing the $i$-th outcome when the measurement is $\Pi$.

A more concise method to write the double maximization is to observe that any element of any POVM is a Hermitian operator such that $0\le \Pi\le I$, and thus we can equivalently directly maximize over these to get $H_(\rho) = - \max_ \log \operatorname(\Pi \rho).$In fact, this maximization can be performed explicitly and the maximum is obtained when $\Pi$ is the projection onto (any of) the largest eigenvalue(s) of $\rho$. We thus get yet another expression for the min-entropy as: $H_(\rho) = -\log \, \rho\, _,$remembering that the operator norm of a Hermitian positive semidefinite operator equals its largest eigenvalue.

Conditional entropies

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_ \frac H_^ (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) \operatorname(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)~.$

Since the conditional min-entropy is always smaller than the conditional Von Neumann entropy, it follows that
$p_g(X, B) \geq 2^~.$

Min-entropy as overlap with the 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_\lambda \~.$

This can be re-written as

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

subject to the conditions

$\begin \sigma_B &\geq 0, \\ I_A \otimes \sigma_B &\geq \rho_~. \end$

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

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

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

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

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

$\begin \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 \end$
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