New one shot quantum protocols with application to communication complexity

Abstract

In this paper we present the following quantum compression protocol: P : Let $ρ,σ$ be quantum states such that $S(ρ|| σ) = \text{Tr} (ρ\log ρ- ρ\log σ)$, the relative entropy between $ρ$ and $σ$, is finite. Alice gets to know the eigen-decomposition of $ρ$. Bob gets to know the eigen-decomposition of $σ$. Both Alice and Bob know $S(ρ|| σ)$ and an error parameter $ε$. Alice and Bob use shared entanglement and after communication of $\mathcal{O}((S(ρ|| σ)+1)/ε^4)$ bits from Alice to Bob, Bob ends up with a quantum state $\tildeρ$ such that $F(ρ, \tildeρ) \geq 1 - 5ε$, where $F(\cdot)$ represents fidelity. This result can be considered as a non-commutative generalization of a result due to Braverman and Rao [2011] where they considered the special case when $ρ$ and $σ$ are classical probability distributions (or commute with each other) and use shared randomness instead of shared entanglement. We use P to obtain an alternate proof of a direct-sum result for entanglement assisted quantum one-way communication complexity for all relations, which was first shown by Jain, Radhakrishnan and Sen [2005,2008]. We also present a variant of protocol P in which Bob has some side information about the state with Alice. We show that in such a case, the amount of communication can be further reduced, based on the side information that Bob has. Our second result provides a quantum analogue of the widely used classical correlated-sampling protocol. For example, Holenstein [2007] used the classical correlated-sampling protocol in his proof of a parallel-repetition theorem for two-player one-round games.

23 pages. Changed title, abstract and presentation of the paper