Min-entropy

If $P=(p\_1,...,p\_n)$ is a classical finite probability distribution, its min-entropy can be defined as{{cite journal|last1=König|first1=Robert|last2=Renner|first2=Renato|author-link2=Renato Renner|last3=Schaffner|first3=Christian|year=2009|title=The Operational Meaning of Min- and Max-Entropy|journal=IEEE Transactions on Information Theory|publisher=Institute of Electrical and Electronics Engineers (IEEE)|volume=55|issue=9|pages=4337–4347|arxiv=0807.1338|doi=10.1109/tit.2009.2025545|issn=0018-9448|s2cid=17160454}} $$H\_\{\backslash rm\; min\}(\backslash boldsymbol\; P)\; =\; \backslash log\backslash frac\{1\}\{P\_\{\backslash 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(\backslash boldsymbol\; P)=\backslash sum\_i\; p\_i\backslash log(1/p\_i)$, and can thus be written concisely as the expectation value of $\backslash 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\_\{\backslash rm\; min\}(\backslash 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.

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 $\backslash rho$, to still define $H\_\{\backslash rm\; min\}(\backslash rho)$ as $\backslash log(1/P\_\{\backslash rm\; max\})$, but this time defining $P\_\{\backslash rm\; max\}$ as the maximum possible probability that can be obtained measuring $\backslash rho$, maximizing over all possible projective measurements.

Using this, one gets the operational definition that the min-entropy of $\backslash rho$ equals the negative logarithm of the probability of successfully guessing the outcome of any measurement of $\backslash rho$.

Formally, this leads to the definition

$$H\_\{\backslash rm\; min\}(\backslash rho)\; =\; \backslash max\_\backslash Pi\; \backslash log\; \backslash frac\{1\}\{\backslash max\_i\; \backslash operatorname\{tr\}(\backslash Pi\_i\; \backslash rho)\}$$

= - \max_\Pi \log \max_i \operatorname{tr}(\Pi_i \rho),

where we are maximizing over the set of all projective measurements $\backslash Pi=(\backslash Pi\_i)\_i$, $\backslash Pi\_i$ represent the measurement outcomes in the POVM formalism, and $\backslash operatorname\{tr\}(\backslash Pi\_i\; \backslash rho)$ is therefore the probability of observing the $i$-th outcome when the measurement is $\backslash 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\backslash le\; \backslash Pi\backslash le\; I$, and thus we can equivalently directly maximize over these to get $$H\_\{\backslash rm\; min\}(\backslash rho)\; =\; -$$

\max_{0\le \Pi\le I} \log \operatorname{tr}(\Pi \rho).In fact, this maximization can be performed explicitly and the maximum is obtained when $\backslash Pi$ is the projection onto (any of) the largest eigenvalue(s) of $\backslash rho$. We thus get yet another expression for the min-entropy as: $$H\_\{\backslash rm\; min\}(\backslash rho)\; =\; -\backslash log\; \backslash |\backslash rho\backslash |\_\{\backslash rm\; op\},$$remembering that the operator norm of a Hermitian positive semidefinite operator equals its largest eigenvalue.

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

$$H\_\{\backslash min\}(A|B)\_\{\backslash rho\}\; \backslash equiv\; -\backslash inf\_\{\backslash sigma\_B\}D\_\{\backslash max\}(\backslash rho\_\{AB\}\backslash |I\_A\; \backslash otimes\; \backslash sigma\_B)$$

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

$$D\_\{\backslash max\}(\backslash rho\backslash |\backslash sigma)\; =\; \backslash inf\_\{\backslash lambda\}\backslash \{\backslash lambda:\backslash rho\; \backslash leq\; 2^\{\backslash lambda\}\backslash sigma\backslash \}$$

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

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

where the sup and inf range over density operators $\backslash rho\text{'}\_\{AB\}$ which are $\backslash epsilon$-close to $\backslash rho\_\{AB\}$

. This measure of $\backslash epsilon$-close is defined in terms of the purified distance

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

where $F(\backslash rho,\backslash 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)\_\{\backslash rho\}\; =\; \backslash lim\_\{\backslash epsilon\; \backslash to\; 0\}\backslash lim\_\{n\; \backslash to\; \backslash infty\}\; \backslash frac\{1\}\{n\}\; H\_\{\backslash min\}^\{\backslash epsilon\}\; (A^n|B^n)\_\{\backslash rho^\{\backslash otimes\; n\}\}~.$$

This is called the fully quantum asymptotic equipartition theorem.{{cite journal | last1=Tomamichel | first1=Marco | last2=Colbeck | first2=Roger | last3=Renner | first3=Renato | title=A Fully Quantum Asymptotic Equipartition Property | journal=IEEE Transactions on Information Theory | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=55 | issue=12 | year=2009 | issn=0018-9448 | doi=10.1109/tit.2009.2032797 | pages=5840–5847| arxiv=0811.1221 | s2cid=12062282 }}

The smoothed entropies share many interesting properties with the von Neumann entropy. For example, the smooth min-entropy satisfy a data-processing inequality:Renato Renner, "Security of Quantum Key Distribution", Ph.D. Thesis, Diss. ETH No. 16242 {{arxiv| quant-ph/0512258}}

$$H\_\{\backslash min\}^\{\backslash epsilon\}(A|B)\_\{\backslash rho\}\; \backslash geq\; H\_\{\backslash min\}^\{\backslash epsilon\}(A|BC)\_\{\backslash rho\}~.$$

Henceforth, we shall drop the subscript $\backslash 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$ whose state $\backslash 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$.

$$\backslash rho\_\{XB\}\; =\; \backslash sum\_x\; P\_X\; (x)\; |x\backslash rangle\backslash langle\; x|\; \backslash otimes\; \backslash rho\_\{B\}^x\; ,$$

where $\backslash \{|x\backslash rangle\backslash \}$ 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)\; =\; \backslash sum\_x\; P\_X(x)\; \backslash operatorname\{tr\}(E\_x\; \backslash rho\_B^x)\; ,$$

where $E\_x$ is the POVM that maximizes this expression. It can be shown{{cite journal|last1=König|first1=Robert|last2=Renner|first2=Renato|author-link2=Renato Renner|last3=Schaffner|first3=Christian|year=2009|title=The Operational Meaning of Min- and Max-Entropy|journal=IEEE Transactions on Information Theory|publisher=Institute of Electrical and Electronics Engineers (IEEE)|volume=55|issue=9|pages=4337–4347|arxiv=0807.1338|doi=10.1109/tit.2009.2025545|issn=0018-9448|s2cid=17160454}} that this optimum can be expressed in terms of the min-entropy as

$$p\_g(X|B)\; =\; 2^\{-H\_\{\backslash min\}(X|B)\}~.$$

If the state $\backslash rho\_\{XB\}$ is a product state i.e. $\backslash rho\_\{XB\}\; =\; \backslash sigma\_X\; \backslash otimes\; \backslash tau\_B$ for some density operators $\backslash sigma\_X$ and $\backslash tau\_B$, then there is no correlation between the systems $X$ and $B$. In this case, it turns out that $2^\{-H\_\{\backslash min\}(X|B)\}\; =\; \backslash 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)\; \backslash geq\; 2^\{-S(A|B)\_\{\backslash rho\}\}~.$$

The maximally entangled state $|\backslash phi^+\backslash rangle$ on a bipartite system $\backslash mathcal\{H\}\_A\; \backslash otimes\; \backslash mathcal\{H\}\_B$ is defined as

$$|\backslash phi^+\backslash rangle\_\{AB\}\; =\; \backslash frac\{1\}\{\backslash sqrt\{d\}\}\; \backslash sum\_\{x\_A,x\_B\}\; |x\_A\backslash rangle\; |x\_B\backslash rangle$$

where $\backslash \{|x\_A\backslash rangle\backslash \}$ and $\backslash \{|x\_B\backslash rangle\backslash \}$ form an orthonormal basis for the spaces $A$ and $B$ respectively.

For a bipartite quantum state $\backslash rho\_\{AB\}$, we define the maximum overlap with the maximally entangled state as

$$q\_\{c\}(A|B)\; =\; d\_A\; \backslash max\_\{\backslash mathcal\{E\}\}\; F\backslash left((I\_A\; \backslash otimes\; \backslash mathcal\{E\})\; \backslash rho\_\{AB\},\; |\backslash phi^+\backslash rangle\backslash langle\; \backslash phi^\{+\}|\backslash right)^2$$

where the maximum is over all CPTP operations $\backslash mathcal\{E\}$ and $d\_A$ is the dimension of subsystem $A$. This is a measure of how correlated the state $\backslash rho\_\{AB\}$ is. It can be shown that $q\_c(A|B)\; =\; 2^\{-H\_\{\backslash min\}(A|B)\}$. If the information contained in $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.{{cite journal|last1=König|first1=Robert|last2=Renner|first2=Renato|author-link2=Renato Renner|last3=Schaffner|first3=Christian|year=2009|title=The Operational Meaning of Min- and Max-Entropy|journal=IEEE Transactions on Information Theory|publisher=Institute of Electrical and Electronics Engineers (IEEE)|volume=55|issue=9|pages=4337–4347|arxiv=0807.1338|doi=10.1109/tit.2009.2025545|issn=0018-9448|s2cid=17160454}} 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 $\backslash rho\_\{AB\}$. From the definition of the min-entropy, we have

$$H\_\{\backslash min\}(A|B)\; =\; -\; \backslash inf\_\{\backslash sigma\_B\}\; \backslash inf\_\backslash lambda\; \backslash \{\; \backslash lambda\; |\; \backslash rho\_\{AB\}\; \backslash leq\; 2^\{\backslash lambda\}(I\_A\; \backslash otimes\; \backslash sigma\_B)\backslash \}~.$$

This can be re-written as

$$-\backslash log\; \backslash inf\_\{\backslash sigma\_B\}\; \backslash operatorname\{Tr\}(\backslash sigma\_B)$$

subject to the conditions

$$\backslash begin\{align\}$$

\sigma_B &\geq 0, \\

I_A \otimes \sigma_B &\geq \rho_{AB}~.

\end{align}

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

$$\backslash 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 $(\backslash rho\_\{AB\},I\_B,\backslash operatorname\{Tr\}^*)$ where $\backslash operatorname\{Tr\}^*$ is the adjoint of the partial trace over $A$. The action of $\backslash operatorname\{Tr\}^*$ on operators on $B$ can be written as

$$\backslash operatorname\{Tr\}^*(X)\; =\; I\_A\; \backslash otimes\; X~.$$

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

$$\backslash 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 $\backslash mathcal\{E\}$ such that

$$d\_A\; I\_A\; \backslash otimes\; \backslash mathcal\{E\}^\{\backslash dagger\}(|\backslash phi^\{+\}\backslash rangle\backslash langle\backslash phi^\{+\}|)\; =\; E\_\{AB\}$$

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

$$\backslash begin\{align\}$$

\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{align}

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

$$\backslash max\; P\_X(x)\; \backslash langle\; x\; |\; \backslash mathcal\{E\}(\backslash rho\_B^x)|x\; \backslash rangle~.$$

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

• von Neumann entropy
• Generalized relative entropy
• max-entropy

{{reflist}}

Category:Quantum mechanical entropy