# Relating min-entropy with conditional entropy

Suppose we have a classical quantum state $$\sum_x |x\rangle \langle x|\otimes \rho_x$$, one can define the smooth-min entropy $$H_\min(A|B)_\rho$$ as the best probability of guessing outcome $$x$$ given $$\rho_x$$. How does this quantity relate to $$H(A|B)_\rho$$ the standard conditional entropy? If not, how does it relate to the mutual information $$I(A:B)_\rho$$?

The conditional min-entropy $$\text{H}_{\text{min}}(A | B)_{\rho}$$ can be defined for an arbitrary state $$\rho$$ of a pair of registers $$(A,B)$$ as $$- \inf_{\sigma} \,\text{D}_{\text{max}}(\rho \| \mathbb{1}\otimes \sigma),$$ where the infimum is over all states $$\sigma$$ of $$B$$ and $$\text{D}_{\text{max}}$$ is the quantum relative max-entropy: $$\text{D}_{\text{max}}(P\|Q) = \inf\{\lambda\in\mathbb{R}: P\leq 2^{\lambda} Q\}.$$ In contrast, the ordinary conditional entropy $$\text{H}(A | B)_{\rho}$$ can be expressed as $$- \inf_{\sigma}\, \text{D}(\rho \| \mathbb{1}\otimes \sigma),$$ where here $$\text{D}$$ refers to the ordinary quantum relative entropy. (This expression for the conditional entropy simplifies to something more familiar once you know that the infimum is always achieved by $$\sigma = \operatorname{Tr}_{A}(\rho)$$, which is not necessarily true for the formula for the conditional min-entropy.)
It happens to be the case that for a classical-quantum state $$\rho = \sum_x p(x) \,|x\rangle \langle x | \otimes \rho_x$$ that the conditional min-entropy $$\text{H}_{\text{min}}(A | B)_{\rho}$$ is equal to the negative logarithm of the optimal guessing probability.
It is always the case that $$\text{H}_{\text{min}}(A | B)_{\rho} \leq \text{H}(A | B)_{\rho},$$ for every state $$\rho$$ and not just classical-quantum states. This follows from the fact that $$\text{D}(\rho \| Q) \leq \text{D}_{\text{max}}(\rho \| Q)$$ for every density operator $$\rho$$ and every positive semidefinite operator $$Q$$. This inequality follows from the observation that $$\rho \leq 2^{\lambda} Q$$ implies \begin{align} \text{D}(\rho \| Q) & = \operatorname{Tr}(\rho \log(\rho)) - \operatorname{Tr}(\rho \log(Q))\\ & \leq \operatorname{Tr}(\rho\log(\rho)) - \operatorname{Tr}(\rho\log(2^{-\lambda}\rho))\\ & = \lambda, \end{align} where the inequality makes use of the operator monotonicity of the logarithm function: if $$Q \geq 2^{-\lambda}\rho$$, then $$\log(Q) \geq \log(2^{-\lambda}\rho)$$.