Trace distance of two classical-quantum state with hashing

Question

Let's say I have a classical-quantum(cq) state $\rho_{XE}$, where the classical part $(X)$ is orthogonal. It's trace distance from another uniform density operator is defined to be:

$$ \frac{1}{2}||\rho_{XE} - \rho_U \otimes \rho_E||_1. $$

Now I apply a hash function $f$ from $F$ distributed according to probability $p_f$ on the first register and get a new state: $$ \rho_{F(X)E}:= \sum_f p_f \; \rho_{f(X)E}. $$ Then I notice that its trace distance has the following upper bound:

$$ \frac{1}{2}||\rho_{F(X)E} - \rho_U \otimes \rho_E|| \le \epsilon . $$ Now, from this upper bound, what can I infer for the first trace distance, i.e. without the hash function? Would the following be true?

$$ \frac{1}{2}||\rho_{XE} - \rho_U \otimes \rho_E|| \le \epsilon. $$

Thanks!

Answer 1

No, this is not possible. The existence of such a hash function requires the (smooth) min-entropy of the initial state to be large enough but does not depend on its trace distance from a uniform state. For the simplest example possible let's forget about the side information $E$ and just focus on the $X$ system. The basic idea is that we can always pad $X$ with extra information such that the min-entropy stays constant but the distance from uniform grows.

Suppose $X$ is a random bit string of length $n$ such that the first bit $x_1$ is chosen uniformly at random and then $x_2, \dots, x_n$ are all $0$. Now the min-entropy is $- \log \max_{(x_1,\dots,x_n)} p(x_1,\dots, x_n) = 1$. Using, for example, Lemma 1 from [1] there is a hashing procedure such that we can extract 1 bit (i.e. $F(X)$ is a single bit) and $$ \frac12 \| F(X) - U_1\|_1 \leq 1/2 $$ where $U_k$ denotes a uniformly distributed random variable over $k$ bits. But now we can calculate $$ \begin{aligned} \frac12 \| X - U_n\|_1 &= \frac12\sum_{(x_1,\dots, x_n) \in \{0,1\}^n} |p(x_1,\dots,x_n) - 2^{-n}| \\ &= \frac12\left(2 |\frac12 - 2^{-n}| + 2(2^{n-1} - 1)|2^{-n}| \right) \\ &= 1 - 2^{1-n}. \end{aligned} $$ Thus as $n\rightarrow \infty$ we get $\frac12 \| X - U_n\|_1 \rightarrow 1$ but it can always be hashed down to a single bit that is distance $1/2$ away from uniform. By considering larger uniform sequences at the beginning of $X$ you should be able to make this distance grow even further, i.e. the hashed tends to perfectly uniform but the non-hashed is almost perfectly distinguishable.