Score:5

Quantum computationally indistinguishable

ky flag

We say two states $\sigma, \rho$ are computationally indistinguishable, if for efficient quantum algorithm $\mathbf{A}$, $|P(\mathbf{A}(\rho)=1)-P(\mathbf{A}(\sigma)=1)|$ is negligible. I want to show if the trace distance between above states are negligible then they are computationally indistinguishable.

In the classical case, it is known that the statistical indistinguishability implies computational indistinguishability. Now trace distance : $D(ρ, σ) = max_{Em} D(p_m, q_m)$ , where $p_m=tr(E_m\rho),q_m=tr(E_m\sigma)$ which is Theorem 9.1 of Nielsen-Chuang's book. I could then apply measurement probabilities are computationally indistinguishable but cannot proceed after that.

Any help will be appreciated

Score:0
us flag

Wikipedia states it clearly that trace distance gives an upper bound on the probability of distinguishing two states.

For a proof, you can use Stinespring's dilation theorem to represent $\mathbf{A}$ as a unitary $U_A$ followed by tracing out another system and then measuring. But we can then just treat the trace-then-measure as some larger POVM $A_m$ on the larger system. Thus, $\mathbf{A}$ can be seen as a unitary operation followed by the POVM $A_m$. Since unitarities preserve trace distance:

$$ D(\rho,\sigma) =D(U_A\rho U_A^\dagger,U_A\sigma U_A^\dagger)= \sup_{E_m}D(p_m',q_m') \geq D(\text{tr}(A_m(U_A\rho U_A^\dagger)),\text{tr}(A_m(U_A\sigma U_A^\dagger)))$$

where I'm using $p'_m = \text{tr}(E_m(U_A\rho U^\dagger))$.

Suppose $A_1$ is the operator for the measurement outcome of "1"; we can then conclude that $P(\mathbf{A}(\rho)=1) = \text{tr}(A_1(U_A\rho U_A^\dagger))$, and the same for $\sigma$. The result follows (some details are missing, but should be straightforward).

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.