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 ρ A B {\displaystyle \rho _{AB}} . Alice has access to system A {\displaystyle A} and Bob to system B {\displaystyle 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 ).
If P = ( p 1 , . . . , p n ) {\displaystyle P=(p_{1},...,p_{n})} is a classical finite probability distribution, its min-entropy can be defined as H m i n ( P ) = log ⁡ 1 P m a x , P m a x ≡ max i p i . {\displaystyle H_{\rm {min}}({\boldsymbol {P}})=\log {\frac {1}{P_{\rm {max}}}},\qquad P_{\rm {max}}\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 ( P ) = ∑ i p i log ⁡ ( 1 / p i ) {\displaystyle \textstyle 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 ) {\displaystyle \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 m i n ( P ) {\displaystyle H_{\rm {min}}({\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 {\displaystyle 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.
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 ρ {\displaystyle \rho } , to still define H m i n ( ρ ) {\displaystyle H_{\rm {min}}(\rho )} as log ⁡ ( 1 / P m a x ) {\displaystyle \log(1/P_{\rm {max}})} , but this time defining P m a x {\displaystyle P_{\rm {max}}} as the maximum possible probability that can be obtained measuring ρ {\displaystyle \rho } , maximizing over all possible projective measurements. Using this, one gets the operational definition that the min-entropy of ρ {\displaystyle \rho } equals the negative logarithm of the probability of successfully guessing the outcome of any measurement of ρ {\displaystyle \rho } .
Formally, this leads to the definition H m i n ( ρ ) = max Π log ⁡ 1 max i tr ⁡ ( Π i ρ ) = − max Π log ⁡ max i tr ⁡ ( Π i ρ ) , {\displaystyle H_{\rm {min}}(\rho )=\max _{\Pi }\log {\frac {1}{\max _{i}\operatorname {tr} (\Pi _{i}\rho )}}=-\max _{\Pi }\log \max _{i}\operatorname {tr} (\Pi _{i}\rho ),} where we are maximizing over the set of all projective measurements Π = ( Π i ) i {\displaystyle \Pi =(\Pi _{i})_{i}} , Π i {\displaystyle \Pi _{i}} represent the measurement outcomes in the POVM formalism, and tr ⁡ ( Π i ρ ) {\displaystyle \operatorname {tr} (\Pi _{i}\rho )} is therefore the probability of observing the i {\displaystyle i} -th outcome when the measurement is Π {\displaystyle \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 ≤ Π ≤ I {\displaystyle 0\leq \Pi \leq I} , and thus we can equivalently directly maximize over these to get H m i n ( ρ ) = − max 0 ≤ Π ≤ I log ⁡ tr ⁡ ( Π ρ ) . {\displaystyle H_{\rm {min}}(\rho )=-\max _{0\leq \Pi \leq I}\log \operatorname {tr} (\Pi \rho ).} In fact, this maximization can be performed explicitly and the maximum is obtained when Π {\displaystyle \Pi } is the projection onto (any of) the largest eigenvalue(s) of ρ {\displaystyle \rho } . We thus get yet another expression for the min-entropy as: H m i n ( ρ ) = − log ⁡ ‖ ρ ‖ o p , {\displaystyle H_{\rm {min}}(\rho )=-\log \|\rho \|_{\rm {op}},} remembering that the operator norm of a Hermitian positive semidefinite operator equals its largest eigenvalue.
Let ρ A B {\displaystyle \rho _{AB}} be a bipartite density operator on the space H A ⊗ H B {\displaystyle {\mathcal {H}}_{A}\otimes {\mathcal {H}}_{B}} . The min-entropy of A {\displaystyle A} conditioned on B {\displaystyle B} is defined to be H min ( A | B ) ρ ≡ − inf σ B D max ( ρ A B ‖ I A ⊗ σ B ) {\displaystyle H_{\min }(A|B)_{\rho }\equiv -\inf _{\sigma _{B}}D_{\max }(\rho _{AB}\|I_{A}\otimes \sigma _{B})} where the infimum ranges over all density operators σ B {\displaystyle \sigma _{B}} on the space H B {\displaystyle {\mathcal {H}}_{B}} . The measure D max {\displaystyle D_{\max }} is the maximum relative entropy defined as D max ( ρ ‖ σ ) = inf λ { λ : ρ ≤ 2 λ σ } {\displaystyle D_{\max }(\rho \|\sigma )=\inf _{\lambda }\{\lambda :\rho \leq 2^{\lambda }\sigma \}} The smooth min-entropy is defined in terms of the min-entropy. H min ϵ ( A | B ) ρ = sup ρ ′ H min ( A | B ) ρ ′ {\displaystyle H_{\min }^{\epsilon }(A|B)_{\rho }=\sup _{\rho '}H_{\min }(A|B)_{\rho '}} where the sup and inf range over density operators ρ A B ′ {\displaystyle \rho '_{AB}} which are ϵ {\displaystyle \epsilon } -close to ρ A B {\displaystyle \rho _{AB}} . This measure of ϵ {\displaystyle \epsilon } -close is defined in terms of the purified distance P ( ρ , σ ) = 1 − F ( ρ , σ ) 2 {\displaystyle P(\rho ,\sigma )={\sqrt {1-F(\rho ,\sigma )^{2}}}} where F ( ρ , σ ) {\displaystyle 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 ϵ → 0 lim n → ∞ 1 n H min ϵ ( A n | B n ) ρ ⊗ n . {\displaystyle S(A|B)_{\rho }=\lim _{\epsilon \to 0}\lim _{n\to \infty }{\frac {1}{n}}H_{\min }^{\epsilon }(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 ) ρ ≥ H min ϵ ( A | B C ) ρ . {\displaystyle H_{\min }^{\epsilon }(A|B)_{\rho }\geq H_{\min }^{\epsilon }(A|BC)_{\rho }~.}
Henceforth, we shall drop the subscript ρ {\displaystyle \rho } from the min-entropy when it is obvious from the context on what state it is evaluated.
Suppose an agent had access to a quantum system B {\displaystyle B} whose state ρ B x {\displaystyle \rho _{B}^{x}} depends on some classical variable X {\displaystyle X} . Furthermore, suppose that each of its elements x {\displaystyle x} is distributed according to some distribution P X ( x ) {\displaystyle P_{X}(x)} . This can be described by the following state over the system X B {\displaystyle XB} . ρ X B = ∑ x P X ( x ) | x ⟩ ⟨ x | ⊗ ρ B x , {\displaystyle \rho _{XB}=\sum _{x}P_{X}(x)|x\rangle \langle x|\otimes \rho _{B}^{x},} where { | x ⟩ } {\displaystyle \{|x\rangle \}} form an orthonormal basis. We would like to know what the agent can learn about the classical variable x {\displaystyle x} . Let p g ( X | B ) {\displaystyle p_{g}(X|B)} be the probability that the agent guesses X {\displaystyle X} when using an optimal measurement strategy p g ( X | B ) = ∑ x P X ( x ) tr ⁡ ( E x ρ B x ) , {\displaystyle p_{g}(X|B)=\sum _{x}P_{X}(x)\operatorname {tr} (E_{x}\rho _{B}^{x}),} where E x {\displaystyle 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 ) . {\displaystyle p_{g}(X|B)=2^{-H_{\min }(X|B)}~.}
If the state ρ X B {\displaystyle \rho _{XB}} is a product state i.e. ρ X B = σ X ⊗ τ B {\displaystyle \rho _{XB}=\sigma _{X}\otimes \tau _{B}} for some density operators σ X {\displaystyle \sigma _{X}} and τ B {\displaystyle \tau _{B}} , then there is no correlation between the systems X {\displaystyle X} and B {\displaystyle B} . In this case, it turns out that 2 − H min ( X | B ) = max x P X ( x ) . {\displaystyle 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 ) ≥ 2 − S ( A | B ) ρ . {\displaystyle p_{g}(X|B)\geq 2^{-S(A|B)_{\rho }}~.}
The maximally entangled state | ϕ + ⟩ {\displaystyle |\phi ^{+}\rangle } on a bipartite system H A ⊗ H B {\displaystyle {\mathcal {H}}_{A}\otimes {\mathcal {H}}_{B}} is defined as | ϕ + ⟩ A B = 1 d ∑ x A , x B | x A ⟩ | x B ⟩ {\displaystyle |\phi ^{+}\rangle _{AB}={\frac {1}{\sqrt {d}}}\sum _{x_{A},x_{B}}|x_{A}\rangle |x_{B}\rangle } where { | x A ⟩ } {\displaystyle \{|x_{A}\rangle \}} and { | x B ⟩ } {\displaystyle \{|x_{B}\rangle \}} form an orthonormal basis for the spaces A {\displaystyle A} and B {\displaystyle B} respectively. For a bipartite quantum state ρ A B {\displaystyle \rho _{AB}} , we define the maximum overlap with the maximally entangled state as q c ( A | B ) = d A max E F ( ( I A ⊗ E ) ρ A B , | ϕ + ⟩ ⟨ ϕ + | ) 2 {\displaystyle q_{c}(A|B)=d_{A}\max _{\mathcal {E}}F\left((I_{A}\otimes {\mathcal {E}})\rho _{AB},|\phi ^{+}\rangle \langle \phi ^{+}|\right)^{2}} where the maximum is over all CPTP operations E {\displaystyle {\mathcal {E}}} and d A {\displaystyle d_{A}} is the dimension of subsystem A {\displaystyle A} . This is a measure of how correlated the state ρ A B {\displaystyle \rho _{AB}} is. It can be shown that q c ( A | B ) = 2 − H min ( A | B ) {\displaystyle q_{c}(A|B)=2^{-H_{\min }(A|B)}} . If the information contained in A {\displaystyle A} is classical, this reduces to the expression above for the guessing probability.
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 ρ A B {\displaystyle \rho _{AB}} . From the definition of the min-entropy, we have H min ( A | B ) = − inf σ B inf λ { λ | ρ A B ≤ 2 λ ( I A ⊗ σ B ) } . {\displaystyle H_{\min }(A|B)=-\inf _{\sigma _{B}}\inf _{\lambda }\{\lambda |\rho _{AB}\leq 2^{\lambda }(I_{A}\otimes \sigma _{B})\}~.}
This can be re-written as − log ⁡ inf σ B Tr ⁡ ( σ B ) {\displaystyle -\log \inf _{\sigma _{B}}\operatorname {Tr} (\sigma _{B})} subject to the conditions σ B ≥ 0 , I A ⊗ σ B ≥ ρ A B . {\displaystyle {\begin{aligned}\sigma _{B}&\geq 0,\\I_{A}\otimes \sigma _{B}&\geq \rho _{AB}~.\end{aligned}}}
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: Tr ⁡ ( σ B ) subject to: I A ⊗ σ B ≥ ρ A B σ B ≥ 0 . {\displaystyle {\begin{cases}{\text{min:}}\operatorname {Tr} (\sigma _{B})\\{\text{subject to: }}I_{A}\otimes \sigma _{B}\geq \rho _{AB}\\\sigma _{B}\geq 0~.\end{cases}}}
This primal problem can also be fully specified by the matrices ( ρ A B , I B , Tr ∗ ) {\displaystyle (\rho _{AB},I_{B},\operatorname {Tr} ^{*})} where Tr ∗ {\displaystyle \operatorname {Tr} ^{*}} is the adjoint of the partial trace over A {\displaystyle A} . The action of Tr ∗ {\displaystyle \operatorname {Tr} ^{*}} on operators on B {\displaystyle B} can be written as Tr ∗ ⁡ ( X ) = I A ⊗ X . {\displaystyle \operatorname {Tr} ^{*}(X)=I_{A}\otimes X~.}
We can express the dual problem as a maximization over operators E A B {\displaystyle E_{AB}} on the space A B {\displaystyle AB} as { max: Tr ⁡ ( ρ A B E A B ) subject to: Tr A ⁡ ( E A B ) = I B E A B ≥ 0 . {\displaystyle {\begin{cases}{\text{max:}}\operatorname {Tr} (\rho _{AB}E_{AB})\\{\text{subject to: }}\operatorname {Tr} _{A}(E_{AB})=I_{B}\\E_{AB}\geq 0~.\end{cases}}}
Using the Choi–Jamiołkowski isomorphism, we can define the channel E {\displaystyle {\mathcal {E}}} such that d A I A ⊗ E † ( | ϕ + ⟩ ⟨ ϕ + | ) = E A B {\displaystyle d_{A}I_{A}\otimes {\mathcal {E}}^{\dagger }(|\phi ^{+}\rangle \langle \phi ^{+}|)=E_{AB}} where the bell state is defined over the space A A ′ {\displaystyle AA'} . This means that we can express the objective function of the dual problem as ⟨ ρ A B , E A B ⟩ = d A ⟨ ρ A B , I A ⊗ E † ( | ϕ + ⟩ ⟨ ϕ + | ) ⟩ = d A ⟨ I A ⊗ E ( ρ A B ) , | ϕ + ⟩ ⟨ ϕ + | ) ⟩ {\displaystyle {\begin{aligned}\langle \rho _{AB},E_{AB}\rangle &=d_{A}\langle \rho _{AB},I_{A}\otimes {\mathcal {E}}^{\dagger }(|\phi ^{+}\rangle \langle \phi ^{+}|)\rangle \\&=d_{A}\langle I_{A}\otimes {\mathcal {E}}(\rho _{AB}),|\phi ^{+}\rangle \langle \phi ^{+}|)\rangle \end{aligned}}} as desired.
Notice that in the event that the system A {\displaystyle A} is a partly classical state as above, then the quantity that we are after reduces to max P X ( x ) ⟨ x | E ( ρ B x ) | x ⟩ . {\displaystyle \max P_{X}(x)\langle x|{\mathcal {E}}(\rho _{B}^{x})|x\rangle ~.} We can interpret E {\displaystyle {\mathcal {E}}} as a guessing strategy and this then reduces to the interpretation given above where an adversary wants to find the string x {\displaystyle x} given access to quantum information via system B {\displaystyle B} .
von Neumann entropy
Generalized relative entropy
Max-entropy
