# Why can the max-relative entropy be written as $D_{\max}(\rho \parallel \sigma) = \inf \{ \lambda : \rho \leq 2^\lambda \sigma \}$?

The quantum conditional min-entropy is defined as

$$H_{\min}(A|B) = - \inf\limits_{\sigma_B} D_{\max} \left( \rho_{AB} \parallel I_A \otimes \sigma_B \right),$$ where $$D_{\max}(\rho \parallel I_A \otimes \sigma_B) = \inf \{ \lambda : \rho \leq 2^\lambda I_A \otimes \sigma_B \}.$$ Why is the max-relative entropy given by $$D_{\max}(\rho \parallel I_A \otimes \sigma_B) = \inf \{ \lambda : \rho \leq 2^\lambda I_A \otimes \sigma_B \}$$? I have not seen a proof of this.

To clarify, I am not sure whether $$D_{\max}(\rho \parallel I_A \otimes \sigma_B) = \inf \{ \lambda : \rho \leq 2^\lambda I_A \otimes \sigma_B \}$$ is a definition, or the definition is instead $$D_{\max} (\rho \parallel \sigma) = \max\limits_{\sigma_B} D(\rho \parallel \sigma)$$, and one then shows that $$\max\limits_{\sigma_B} D(\rho \parallel \sigma) = \inf \{ \lambda: \rho \leq 2^\lambda \sigma \}$$.

If the definition of max-relative entropy is $$\inf \{ \lambda : \rho \leq 2^\lambda \sigma_B \}$$, then how does this notion relates to the more general notion of relative entropy?

Consider the standard definition of (classical) relative entropy between two probability distribution $$P,Q$$: $$D(P\|Q)=\sum_i P_i \log\left(\frac{P_i}{Q_i}\right).$$ You can read this as the expectation value of the quantity $$\log(P_i/Q_i)$$, over the distribution $$P$$. Suppose instead of taking the average you take the maximum value of this quantity, defining $$D_{\rm max}(P\|Q) = \max_i \log\left(\frac{P_i}{Q_i}\right).$$ There is another equivalent way to write this: note that $$\max_i c_i$$ is equal to the smallest $$\lambda$$ such that $$c_i\le \lambda$$ for all $$i$$. In other words, you could rewrite $$D_{\rm max}$$ as $$D_{\rm max}(P\|Q) = \inf\{\lambda\in\mathbb{R}:\,\,\log(P_i/Q_i)\le\lambda,\,\,\forall i\} \\ = \inf\{\lambda\in\mathbb{R}: \,\, P\le 2^\lambda Q\} = \log\inf\{\eta\ge0:\,\,P\le \eta Q\}.$$ Note that in the last two expressions we're writing $$P\le 2^\lambda Q$$, where $$P,Q$$ are vectors here, to indicate $$P_i\le 2^\lambda Q_i$$ for all $$i$$.
In the quantum case you can write the relative entropy as $$D(\rho\|\sigma)=\operatorname{tr}(\rho\log\rho)-\operatorname{tr}(\rho\log\sigma) = \sum_{i,j} p_i |\langle p_i|q_j\rangle|^2 \log\left(\frac{p_i}{q_j}\right),$$ as also discussed here. A little trickier than the classical expression, but it's still an expectation value of $$\log(p_i/q_j)$$, though now wrt to a joint probability distribution depending on both $$\rho,\sigma$$, which doesn't reduce to the classical case unless $$[\rho,\sigma]=0$$.
Now, I'm actually not sure whether there is a way to go from this to the expression for $$D_{\rm max}$$ as cleanly as the above argument for classical states. However, observe that $$\inf \{\lambda\in\mathbb{R}:\,\,\rho\le 2^\lambda \sigma\}$$ is the smallest real $$\lambda$$ such that $$\rho\le 2^\lambda \sigma$$, which means the smallest $$\lambda$$ such that $$2^\lambda\sigma-\rho\ge0$$. An equivalent condition is that, for all positive semidefinite operators $$Z\ge0$$, we have $$\langle Z,\rho\rangle\le 2^\lambda \langle Z,\sigma\rangle,$$ where we're using the trace inner product: $$\langle Z,A\rangle\equiv \operatorname{tr}(Z^\dagger A)$$. Therefore $$\inf \{\lambda\in\mathbb{R}:\,\,\rho\le 2^\lambda \sigma\} = \log\inf \{\eta\ge0:\,\,\frac{\langle Z,\rho\rangle}{\langle Z,\sigma\rangle}\le \eta, \,\,\forall Z\ge0\} \\ = \log\sup_{Z\ge0} \frac{\langle Z,\rho\rangle}{\langle Z,\sigma\rangle} = \sup_{Z\ge0}\log \frac{\langle Z,\rho\rangle}{\langle Z,\sigma\rangle}.$$ While we didn't get to this directly from converting averages to max in the expression for $$D(\rho\|\sigma)$$, this is clearly quite similar to what we have for $$D_{\rm max}(P\|Q)$$ classically, except that we're replacing the max over outcomes to its quantum counterpart: a max over the log-ratio of the possible probabilities measuring the two states in a common basis. See the second lecture of Watrous' QIT notes for more information.