Anshu, AnuragJain, RahulMukhopadhyay, PriyankaShayeghi, AlaYao, Penghui2024-02-072016-12A. Anshu, R. Jain, P. Mukhopadhyay, A. Shayeghi and P. Yao, "New One Shot Quantum Protocols With Application to Communication Complexity," in IEEE Transactions on Information Theory, vol. 62, no. 12, pp. 7566-7577, Dec. 2016, doi: 10.1109/TIT.2016.2616125.0018-94481557-9654https://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37377731In this paper we present the following quantum compression protocol: P : Let ρ,σ be quantum states such that S(ρ||σ)=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 ((S(ρ||σ)+1)/ϵ4) bits from Alice to Bob, Bob ends up with a quantum state ρ̃ such that F(ρ,ρ̃ )≥1−5ϵ, where F(⋅) 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.en-USLibrary and Information SciencesComputer Science ApplicationsInformation SystemsConference Paper2024-02-0710.1109/tit.2016.2616125