TransWikia.com

Trace distance of two classical-quantum state with hashing

Quantum Computing Asked on May 23, 2021

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!

One Answer

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 &= frac12sum_{(x_1,dots, x_n) in {0,1}^n} |p(x_1,dots,x_n) - 2^{-n}| &= frac12left(2 |frac12 - 2^{-n}| + 2(2^{n-1} - 1)|2^{-n}| right) &= 1 - 2^{1-n}. end{aligned} $$ Thus as $nrightarrow 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.

Correct answer by Rammus on May 23, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP