Prove that for a cq-state $\rho_{XE}$, $H_\infty(X|E) \ge H_\infty(X) - \log|E|$

Question

Given a classical-quantum(cq) state $\rho_{XE}$, where the $X$ register is classical, I want to prove the following:

$$ \begin{align} H_\infty(X|E) \ge H_\infty(X) - \log|E|,\tag{1} \end{align} $$ i.e., the conditional min-entropy of $X$, having access to the quantum register $E$ is at least the min-entropy of $X$ minus the log of dimension of the quantum register $E$.

The term $H_\infty(X|E)$ is defined as the following:

$$ H_\infty(X|E) := \underset{\sigma_E}{\sup} \max\{\lambda \in \mathbb{R} : 2^{-\lambda} \mathbb{I} \otimes \sigma_E - \rho_{XE} \ge 0\} $$

It is my understanding that, $X$ is a classical register and in this case the min-entropy is defined as:

$$H_\infty(X) = -\log \underset{x}\max p_x,$$ for the classical probability distribution $\{p_x\}_x$ of the random variable $X$. From this, we can easily see that,

$$ H_\infty(X) \le H(X) \le \log|X|. $$ I also know that, $$ H(X|E) \le H(X), $$ because conditioning can not increase entropy. Here is what I tried, $$ \begin{align*} H_\infty(X|E) &\le H(X|E) \\ &= H(XE) - H(E) \\ &= H(X) + \sum_x p_x H(\rho_x) - H(E) \\ &\ge H(X) + \sum_x p_x H(\rho_x) - \log |E|, \end{align*} $$ and you see the obvious problem with my reasoning. What is the correct approach to prove equation (1)? Thanks in advance.

Answer 1

Let $\rho_{XE} = \sum_x p(x) |x\rangle \langle x| \otimes \rho_E(x)$ where $p(x)$ is a probability distribution and for each $x$, $\rho_E(x)$ is a quantum state on the system $E$. Let $\|X\|_1 = \mathrm{tr}[(X^* X)^{1/2}]$ and let $\|X\|_{\infty} = \max_i \sigma_i(X)$ where $\sigma_i(X)$ are the singular values of $X$. Note that if $X$ is a positive-semidefinite matrix then $\|X\|_1 = \mathrm{tr}[X]$ and $\|X\|_{\infty} = \lambda_{\max}$ where $\lambda_{\max}$ is the largest eigenvalue of $X$.

We use the form of the min-entropy given by $$ H_{\min}(X|E) = - \log p_{guess}(X|E) $$ where $$ p_{guess}(X|E) = \max_{\text{POVMs } M_x}\sum_x p(x) \mathrm{tr}[M_x \rho_E(x)] $$ is the maximum probability that an agent holding the system $E$ could guess the value of the register $X$ by measuring $E$.

In order to obtain the lower bound on $H_{\min}$ we look for an upper bound on $p_{guess}$. Therefore, $$ \begin{aligned} \max_{\text{POVMs } M_x}\sum_x p(x) \mathrm{tr}[M_x \rho_E(x)] &\leq p_{\max} \max_{\text{POVMs } M_x}\sum_x \mathrm{tr}[M_x \rho_E(x)] \\ &\leq p_{\max} \max_{\text{POVMs } M_x}\sum_x \|M_x\|_1 \|\rho_E(x)\|_{\infty} \\ &\leq p_{\max} \max_{\text{POVMs } M_x}\sum_x\|M_x\|_1 \\ &= p_{\max} \max_{\text{POVMs } M_x}\sum_x \mathrm{tr}[M_x] \\ &= p_{\max} \max_{\text{POVMs } M_x} \mathrm{tr}[I_E] \\ &= p_{\max} |E|. \end{aligned} $$ On the third line we trivially upper bounded each probability by $p_{\max} = \max p(x)$ (noting each term in the sum is nonnegative); on the second line we used Hölder's inequality for the Hilbert-Schmidt inner product $\langle A, B\rangle = \mathrm{tr}[A^* B]$; on the third line we noted that the largest eigenvalue of $\rho_E(X)$ is never larger than $1$ as it is a quantum state; on the fourth line we noted $M_x\geq 0$ and so $\|M_x\|_1 = \mathrm{tr}[M_x]$; on the fifth line we used the fact that $\sum_x M_x = I_E$ and on the final line we noted that $\mathrm{tr}[I_E] = |E|$.

Plugging this upper bound into the definition of the min-entropy you get the desired lower bound.