New One Shot Quantum Protocols With Application to Communication Complexity

• Published in: IEEE transactions on information theory 2016-12, Vol.62 (12), p.7566-7577
• Main Authors: Anshu, Anurag, Jain, Rahul, Mukhopadhyay, Priyanka, Shayeghi, Ala, Penghui Yao
• Format: Article
• Language: English
• Subjects: Complexity theory; compression protocols; correlated sampling; direct sum results; Eigenvalues; Entropy; Protocol; Protocols; quantum communication complexity; Quantum computing; Quantum entanglement; Quantum information theory; Quantum physics; Registers; Sampling
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2016.2616125

In this paper, we present the following quantum compression protocol `P': Let ρ,σ be quantum states, such that S (ρ∥σ) def = Tr(ρ log ρ - ρ log σ), the relative entropy between ρ and σ, is finite. Alice gets to know the eigendecomposition of ρ. Bob gets to know the eigendecomposition of σ. Both Alice and Bob know S(ρ∥σ) and an error parameter ε. Alice and Bob use shared entanglement and after communication of O((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 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? 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 et al.. We also present a variant of protocol? 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 analog of the widely used classical correlated-sampling protocol. For example, Holenstein used the classical correlated-sampling protocol in his proof of a parallel-repetition theorem for two-player one-round games.