Min-entropy explained

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 ^[1]).

Definition for classical distributions

If

P = (p _{1,...,p} _{n)} is a classical finite probability distribution, its min-entropy can be defined as^[2] $$H\_(\backslash boldsymbol\; P)\; =\; \backslash log\backslash frac,\backslash qquad\; P\_\backslash equiv\; \backslash 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 _{ilog(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 _{\rm} (\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 _{\rm} (\rho) as log ( 1 /P _{\rm} ) , but this time defining P _{\rm} 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\_(\backslash rho)\; =\; \backslash max\_\backslash Pi\; \backslash log\; \backslash frac=\; -\; \backslash max\_\backslash Pi\; \backslash log\; \backslash max\_i\; \backslash operatorname(\backslash Pi\_i\; \backslash 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{tr}(\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\_(\backslash rho)\; =\; -\backslash max\_\; \backslash log\; \backslash operatorname(\backslash Pi\; \backslash 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\_(\backslash rho)\; =\; -\backslash log\; \backslash |\backslash rho\backslash |\_,$$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 l{H} _{A} ⊗ l{H} _{B} . The min-entropy of A conditioned on B is defined to beH _{min} (A|B) _{\rho} \equiv -inf _{\sigma _{B}} D _{max} (\rho _{AB} \|I _{A} ⊗ \sigma _{B)}

where the infimum ranges over all density operators

\sigma _{B} on the space l{H} _{B} . The measure D _{max} is the maximum relative entropy defined asD _{max} (\rho\|\sigma) = inf _{λ} \{ λ :\rho \leq 2 ^{λ} \sigma\}

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

H ^{\epsilon} _{min} (A|B) _{\rho} = \sup _{\rho'} H _{min} (A|B) _{\rho'}

where the sup and inf range over density operators

\rho' _{AB} which are \epsilon -close to \rho _{AB} . This measure of \epsilon -close is defined in terms of the purified distanceP(\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} = \lim _{\epsilon →} \lim _{n → infty} (1)/(n) H ^{\epsilon} _{min} (A ^{n|B} ^{n)} ^{\rho ^{⊗}} ~. This is called the fully quantum asymptotic equipartition theorem.^[3] The smoothed entropies share many interesting properties with the von Neumann entropy. For example, the smooth min-entropy satisfy a data-processing inequality:^[4] H ^{\epsilon} _{min} (A|B) _{\rho} \geq H ^{\epsilon} _{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 ^{x} _{B} 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\rangle\langle x| ⊗ \rho ^{x} _{B} ,

where

\{|x\rangle\} 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 strategyp _{g(X|B)} = \sum _{x} P _{X(x)} \operatorname{tr}(E _{x} \rho ^{x)} _{B} ,

where

E _{x} is the POVM that maximizes this expression. It can be shown^[5] that this optimum can be expressed in terms of the min-entropy asp _{g(X|B)} = 2 ^{- H _{min} (X|B)} ~.

If the state

\rho _{XB} is a product state i.e. \rho _{XB} = \sigma _{X} ⊗ \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)} = 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 ^{- S(A|B) _{\rho}} ~.

Min-entropy as overlap with the maximally entangled state

The maximally entangled state

|\phi ^{+\rangle} on a bipartite system l{H} _{A} ⊗ l{H} _{B} is defined as|\phi ^{+ \rangle} _{AB} = (1)/(\sqrt{d) } \sum_ |x_A\rangle |x_B\rangle

where

\{|x _{A\rangle\}} and \{|x _{B\rangle\}} 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 asq _{c} (A|B) = d _{A} max _{l{E} } F\left((I_A \otimes \mathcal) \rho_, |\phi^+\rangle\langle \phi^|\right)^2

where the maximum is over all CPTP operations

l{E} 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.^[6] It involves the machinery of semidefinite programs.^[7] Suppose we are given some bipartite density operator

\rho _{AB} . From the definition of the min-entropy, we haveH _{min} (A|B) = - inf _{\sigma _{B}} inf _{λ} \{ λ | \rho _{AB} \leq 2 ^{λ} (I _{A} ⊗ \sigma _{B)\}~.}

This can be re-written as

-log inf _{\sigma _{B}} \operatorname{Tr}(\sigma _{B)}

subject to the conditions

\sigma _{B} \geq 0 I _{A} ⊗ \sigma _{B} \geq \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

min: \operatorname{Tr} (\sigma _{B)} subjectto: I _{A} ⊗ \sigma _{B} \geq \rho _{AB} \sigma _{B} \geq 0 ~.

This primal problem can also be fully specified by the matrices

(\rho _{AB} ,I ^{*)} _{B,\operatorname{Tr}} where \operatorname{Tr} ^{*} is the adjoint of the partial trace over A . The action of \operatorname{Tr} ^{*} on operators on B can be written as\operatorname{Tr} ^{*(X)} = I _{A} ⊗ X~.

We can express the dual problem as a maximization over operators

E _{AB} on the space AB asmax: \operatorname{Tr}(\rho _{AB} E _{AB} ) subjectto: \operatorname{Tr} _{A(E} _{AB} ) = I _{B} E _{AB} \geq 0 ~.

Using the Choi–Jamiołkowski isomorphism, we can define the channel

l{E} such thatd _{A} I _{A} ⊗ l{E} ^{\dagger} (|\phi ^{+} \rangle\langle\phi ^{+} |) = E _{AB} 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 _{AB} , E _{AB} \rangle = d _{A} \langle \rho _{AB} , I _{A} ⊗ l{E} ^{\dagger} (|\phi ^{+\rangle\langle} \phi ^{+|)} \rangle = d _{A} \langle I _{A} ⊗ l{E}(\rho _{AB} ), |\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 tomax P _{X(x)} \langle x | l{E}(\rho ^{x)|x} _{B} \rangle~. We can interpret l{E} 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

Notes and References

1. Vazirani . Umesh . Vidick . Thomas . Fully Device-Independent Quantum Key Distribution . Physical Review Letters . 113 . 14 . 29 September 2014 . 0031-9007 . 10.1103/physrevlett.113.140501 . 140501. 1210.1810 . 25325625. 2014PhRvL.113n0501V . 119299119 .
2. König. Robert. Renner. Renato. Renato Renner. Schaffner. Christian. 2009. The Operational Meaning of Min- and Max-Entropy. IEEE Transactions on Information Theory. Institute of Electrical and Electronics Engineers (IEEE). 55. 9. 4337–4347. 0807.1338. 10.1109/tit.2009.2025545. 0018-9448. 17160454.
3. Tomamichel . Marco . Colbeck . Roger . Renner . Renato . A Fully Quantum Asymptotic Equipartition Property . IEEE Transactions on Information Theory . Institute of Electrical and Electronics Engineers (IEEE) . 55 . 12 . 2009 . 0018-9448 . 10.1109/tit.2009.2032797 . 5840–5847. 0811.1221 . 12062282 .
4. Renato Renner, "Security of Quantum Key Distribution", Ph.D. Thesis, Diss. ETH No. 16242
5. König. Robert. Renner. Renato. Renato Renner. Schaffner. Christian. 2009. The Operational Meaning of Min- and Max-Entropy. IEEE Transactions on Information Theory. Institute of Electrical and Electronics Engineers (IEEE). 55. 9. 4337–4347. 0807.1338. 10.1109/tit.2009.2025545. 0018-9448. 17160454.
6. König. Robert. Renner. Renato. Renato Renner. Schaffner. Christian. 2009. The Operational Meaning of Min- and Max-Entropy. IEEE Transactions on Information Theory. Institute of Electrical and Electronics Engineers (IEEE). 55. 9. 4337–4347. 0807.1338. 10.1109/tit.2009.2025545. 0018-9448. 17160454.
7. John Watrous, Theory of quantum information, Fall 2011, course notes, https://cs.uwaterloo.ca/~watrous/CS766/LectureNotes/07.pdf