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



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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.