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 _{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_{\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({\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_{\rm {min}}({\boldsymbol {P}})$ .

Definition for quantum states

A natural way to define a "min-entropy" for quantum states is to leverage the simple observation that quantum states result in 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 {min}}(\rho )$ as $\log(1/P_{\rm {max}})$ , but this time defining $P_{\rm {max}}$ as the maximum possible probability that can be obtained measuring $\rho$ , maximizing over all possible projective measurements.

Formally, this would provide the definition

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 $\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\leq \Pi \leq I$ , and thus we can equivalently directly maximize over these to get

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 $\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_{\rm {min}}(\rho )=-\log \|\rho \|_{\rm {op}},

remembering that the operator norm of a Hermitian positive semidefinite operator equals its largest eigenvale.

Conditional entropies

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

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 $\sigma _{B}$ on the space ${\mathcal {H}}_{B}$ . The measure $D_{\max }$ is the maximum relative entropy defined as

{\displaystyle D_{\max }(\rho \|\sigma )=\inf _{\lambda }\{\lambda

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

H_{\min }^{\epsilon }(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 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 }=\lim _{\epsilon \rightarrow 0}\lim _{n\rightarrow \infty }{\frac {1}{n}}H_{\min }^{\epsilon }(A^{n}|B^{n})_{\rho ^{\otimes n}}~.

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_{\min }^{\epsilon }(A|B)_{\rho }\geq H_{\min }^{\epsilon }(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\rangle \langle x|\otimes \rho _{B}^{x},

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 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^{-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)}=\max _{x}P_{X}(x)~.$

Min-entropy as overlap with the maximally entangled state

The maximally entangled state $|\phi ^{+}\rangle$ on a bipartite system ${\mathcal {H}}_{A}\otimes {\mathcal {H}}_{B}$ is defined as

|\phi ^{+}\rangle _{AB}={\frac {1}{\sqrt {d}}}\sum _{x_{A},x_{B}}|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 as

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 ${\mathcal {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.^[5] It involves the machinery of semidefinite programs.^[6] Suppose we are given some bipartite density operator $\rho _{AB}$ . From the definition of the min-entropy, we have

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 _{\sigma _{B}}\operatorname {Tr} (\sigma _{B})

subject to the conditions

\sigma _{B}\geq 0

I_{A}\otimes \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

{\text{min:}}\operatorname {Tr} (\sigma _{B})

{\text{subject to: }}I_{A}\otimes \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}\otimes X~.

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

{\text{max:}}\operatorname {Tr} (\rho _{AB}E_{AB})

{\text{subject to: }}\operatorname {Tr} _{A}(E_{AB})=I_{B}

E_{AB}\geq 0~.

Using the Choi–Jamiołkowski isomorphism, we can define the channel ${\mathcal {E}}$ such that

d_{A}I_{A}\otimes {\mathcal {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}\otimes {\mathcal {E}}^{\dagger }(|\phi ^{+}\rangle \langle \phi ^{+}|)\rangle

=d_{A}\langle I_{A}\otimes {\mathcal {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 to

\max P_{X}(x)\langle x|{\mathcal {E}}(\rho _{B}^{x})|x\rangle ~.

We can interpret ${\mathcal {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$ .

References

↑ Vazirani, Umesh; Vidick, Thomas (29 September 2014). "Fully Device-Independent Quantum Key Distribution". Physical Review Letters. 113 (14): 140501. arXiv:1210.1810. Bibcode:2014PhRvL.113n0501V. doi:10.1103/physrevlett.113.140501. ISSN 0031-9007. PMID 25325625. S2CID 119299119.
↑ König, Robert; Renner, Renato; 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. arXiv:0807.1338. doi:10.1109/tit.2009.2025545. ISSN 0018-9448. S2CID 17160454.
↑ Tomamichel, Marco; Colbeck, Roger; Renner, Renato (2009). "A Fully Quantum Asymptotic Equipartition Property". IEEE Transactions on Information Theory. Institute of Electrical and Electronics Engineers (IEEE). 55 (12): 5840–5847. arXiv:0811.1221. doi:10.1109/tit.2009.2032797. ISSN 0018-9448. S2CID 12062282.
↑ Renato Renner, "Security of Quantum Key Distribution", Ph.D. Thesis, Diss. ETH No. 16242 arXiv:quant-ph/0512258
↑ König, Robert; Renner, Renato; 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. arXiv:0807.1338. doi:10.1109/tit.2009.2025545. ISSN 0018-9448. S2CID 17160454.
↑ John Watrous, Theory of quantum information, Fall 2011, course notes, https://cs.uwaterloo.ca/~watrous/CS766/LectureNotes/07.pdf

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Vazirani, Umesh; Vidick, Thomas (29 September 2014). "Fully Device-Independent Quantum Key Distribution". Physical Review Letters. 113 (14): 140501. arXiv:1210.1810. Bibcode:2014PhRvL.113n0501V. doi:10.1103/physrevlett.113.140501. ISSN 0031-9007. PMID 25325625. S2CID 119299119.

[2] König, Robert; Renner, Renato; 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. arXiv:0807.1338. doi:10.1109/tit.2009.2025545. ISSN 0018-9448. S2CID 17160454.

[3] Tomamichel, Marco; Colbeck, Roger; Renner, Renato (2009). "A Fully Quantum Asymptotic Equipartition Property". IEEE Transactions on Information Theory. Institute of Electrical and Electronics Engineers (IEEE). 55 (12): 5840–5847. arXiv:0811.1221. doi:10.1109/tit.2009.2032797. ISSN 0018-9448. S2CID 12062282.

[4] Renato Renner, "Security of Quantum Key Distribution", Ph.D. Thesis, Diss. ETH No. 16242 arXiv:quant-ph/0512258

[5] König, Robert; Renner, Renato; 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. arXiv:0807.1338. doi:10.1109/tit.2009.2025545. ISSN 0018-9448. S2CID 17160454.

[6] John Watrous, Theory of quantum information, Fall 2011, course notes, https://cs.uwaterloo.ca/~watrous/CS766/LectureNotes/07.pdf

[1]

[2]

[3]

[4]

[5]

[6]