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

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.

• How is $H_{\infty}(X|E)$ defined? Jul 5, 2021 at 6:35
• The definition is found in this paper: arxiv.org/pdf/0807.1338.pdf . In page 2, equation 3. I am not writing it in the comment because it involves a lot of latex and not sure how that would work out in the comment. Jul 5, 2021 at 18:35
• @QuestionEverything You could edit your question to include it? Jul 6, 2021 at 7:38
• Thanks guys, I've updated the question. Jul 6, 2021 at 19:46

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|$$.