Min-entropy

Template:Short description 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 }_{AB}$. 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_{\mathrm{m}\mathrm{i}\mathrm{n}}(𝑷)=\log \frac{1}{P_{\mathrm{m}\mathrm{a}\mathrm{x}}},P_{\mathrm{m}\mathrm{a}\mathrm{x}}\equiv \underset{i}{\max }{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(𝑷)=\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_{\mathrm{m}\mathrm{i}\mathrm{n}}(𝑷)$.

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_{\mathrm{m}\mathrm{i}\mathrm{n}}(\rho )$ as $\log (1/P_{\mathrm{m}\mathrm{a}\mathrm{x}})$, but this time defining $P_{\mathrm{m}\mathrm{a}\mathrm{x}}$ 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_{\mathrm{m}\mathrm{i}\mathrm{n}}(\rho )=\underset{\mathrm{\Pi }}{\max }\log \frac{1}{\underset{i}{\max }\mathrm{tr}({\mathrm{\Pi }}_i\rho )}=-\underset{\mathrm{\Pi }}{\max }\log \underset{i}{\max }\mathrm{tr}({\mathrm{\Pi }}_i\rho ),$$where we are maximizing over the set of all projective measurements $\mathrm{\Pi }=({\mathrm{\Pi }}_i{)}_i$, ${\mathrm{\Pi }}_i$ represent the measurement outcomes in the POVM formalism, and $\mathrm{tr}({\mathrm{\Pi }}_i\rho )$ is therefore the probability of observing the $i$-th outcome when the measurement is $\mathrm{\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 \mathrm{\Pi }\le I$, and thus we can equivalently directly maximize over these to get $$H_{\mathrm{m}\mathrm{i}\mathrm{n}}(\rho )=-\underset{0\le \mathrm{\Pi }\le I}{\max }\log \mathrm{tr}(\mathrm{\Pi }\rho ).$$In fact, this maximization can be performed explicitly and the maximum is obtained when $\mathrm{\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_{\mathrm{m}\mathrm{i}\mathrm{n}}(\rho )=-\log \Vert \rho {\Vert }_{\mathrm{o}\mathrm{p}},$$remembering that the operator norm of a Hermitian positive semidefinite operator equals its largest eigenvalue.

Conditional entropies

Let ${\rho }_{AB}$ be a bipartite density operator on the space ${\mathscr{H}}_A\otimes {\mathscr{H}}_B$. The min-entropy of $A$ conditioned on $B$ is defined to be

$H_{\min }(A|B{)}_{\rho }\equiv -\underset{{\sigma }_B}{\inf }{D}_{\max }({\rho }_{AB}\Vert I_A\otimes {\sigma }_B)$

where the infimum ranges over all density operators ${\sigma }_B$ on the space ${\mathscr{H}}_B$. The measure $D_{\max }$ is the maximum relative entropy defined as

$D_{\max }(\rho \Vert \sigma )=\underset{\lambda }{\inf }\{\lambda :\rho \le 2^{\lambda }\sigma \}$

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

$H_{\min }^{ϵ}(A|B{)}_{\rho }=\underset{{\rho }^{\prime }}{\sup }{H}_{\min }(A|B{)}_{{\rho }^{\prime }}$

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

$P(\rho ,\sigma )=\sqrt{1-F(\rho ,\sigma {)}^2}$

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{)}_{\rho }=\underset{ϵ\to 0}{\lim }\underset{n\to \mathrm{\infty }}{\lim }\frac{1}{n}{H}_{\min }^{ϵ}(A^n|B^n{)}_{{\rho }^{\otimes 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_{\min }^{ϵ}(A|B{)}_{\rho }\ge H_{\min }^{ϵ}(A|BC{)}_{\rho }.$

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 }_B^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 }_{XB}=\sum _x{P}_X(x)|x⟩⟨x|\otimes {\rho }_B^x,$

where $\{|x⟩\}$ 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)\mathrm{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^{-H_{\min }(X|B)}.$

If the state ${\rho }_{XB}$ is a product state i.e. ${\rho }_{XB}={\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^{-H_{\min }(X|B)}=\underset{x}{\max }{P}_X(x).$

Since the conditional min-entropy is always smaller than the conditional Von Neumann entropy, it follows that

$p_g(X|B)\ge 2^{-S(A|B{)}_{\rho }}.$

Min-entropy as overlap with the maximally entangled state

The maximally entangled state $|{\varphi }^{+}⟩$ on a bipartite system ${\mathscr{H}}_A\otimes {\mathscr{H}}_B$ is defined as

$|{\varphi }^{+}{⟩}_{AB}=\frac{1}{\sqrt{d}}\sum _{x_A,x_B}|x_A⟩|x_B⟩$

where $\{|x_A⟩\}$ and $\{|x_B⟩\}$ form an orthonormal basis for the spaces $A$ and $B$ respectively. For a bipartite quantum state ${\rho }_{AB}$, we define the maximum overlap with the maximally entangled state as

$q_c(A|B)=d_A\underset{ℰ}{\max }F{((I_A\otimes ℰ){\rho }_{AB},|{\varphi }^{+}⟩⟨{\varphi }^{+}|)}^2$

where the maximum is over all CPTP operations $ℰ$ and $d_A$ is the dimension of subsystem $A$. This is a measure of how correlated the state ${\rho }_{AB}$ is. It can be shown that $q_c(A|B)=2^{-H_{\min }(A|B)}$. 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. Suppose we are given some bipartite density operator ${\rho }_{AB}$. From the definition of the min-entropy, we have

$H_{\min }(A|B)=-\underset{{\sigma }_B}{\inf }\underset{\lambda }{\inf }\{\lambda |{\rho }_{AB}\le 2^{\lambda }(I_A\otimes {\sigma }_B)\}.$

This can be re-written as

$-\log \underset{{\sigma }_B}{\inf }\mathrm{Tr}({\sigma }_B)$

subject to the conditions

${\sigma }_B\ge 0$

$I_A\otimes {\sigma }_B\ge {\rho }_{AB}.$

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{min:}\mathrm{Tr}({\sigma }_B)$

$\text{subject to: }{I}_A\otimes {\sigma }_B\ge {\rho }_{AB}$

${\sigma }_B\ge 0.$

This primal problem can also be fully specified by the matrices $({\rho }_{AB},I_B,{\mathrm{Tr}}^{*})$ where ${\mathrm{Tr}}^{*}$ is the adjoint of the partial trace over $A$. The action of ${\mathrm{Tr}}^{*}$ on operators on $B$ can be written as

${\mathrm{Tr}}^{*}(X)=I_A\otimes X.$

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

$\text{max:}\mathrm{Tr}({\rho }_{AB}{E}_{AB})$

$\text{subject to: }{\mathrm{Tr}}_A(E_{AB})=I_B$

$E_{AB}\ge 0.$

Using the Choi–Jamiołkowski isomorphism, we can define the channel $ℰ$ such that

$d_A{I}_A\otimes {ℰ}^{†}(|{\varphi }^{+}⟩⟨{\varphi }^{+}|)=E_{AB}$

where the bell state is defined over the space $A{A}^{\prime }$. This means that we can express the objective function of the dual problem as

$⟨{\rho }_{AB},E_{AB}⟩=d_A⟨{\rho }_{AB},I_A\otimes {ℰ}^{†}(|{\varphi }^{+}⟩⟨{\varphi }^{+}|)⟩$

$=d_A⟨I_A\otimes ℰ({\rho }_{AB}),|{\varphi }^{+}⟩⟨{\varphi }^{+}|)⟩$

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)⟨x|ℰ({\rho }_B^x)|x⟩.$

We can interpret $ℰ$ 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