New One Shot Quantum Protocols With Application to Communication Complexity

DOI10.1109/TIT.2016.2616125MaRDI QIDQ2976478zbMATH OpenOpenAlexFDO

Authors Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, Penghui Yao

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.1366

Mathematics Subject Classification ID

Quantum coherence, entanglement, quantum correlations (81P40) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Abstract: In this paper we present the following quantum compression protocol: P : Let $ho,sigma$ be quantum states such that $S(ho||sigma)=extTr(hologho-hologsigma)$, the relative entropy between $ho$ and $sigma$, is finite. Alice gets to know the eigen-decomposition of $ho$. Bob gets to know the eigen-decomposition of $sigma$. Both Alice and Bob know $S(ho||sigma)$ and an error parameter $epsilon$. Alice and Bob use shared entanglement and after communication of $mathcalO((S(ho||sigma)+1)/epsilo{n}^4)$ bits from Alice to Bob, Bob ends up with a quantum state $ildeho$ such that $F(ho,ildeho)geq1-5epsilon$, 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 $ho$ and $sigma$ 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.

Cited in

(5)

• A parallel repetition theorem for entangled projection games
• Experimental multipartner quantum communication complexity employing just one qubit
• Lifting query complexity to time-space complexity for two-way finite automata
• The Power of One Clean Qubit in Communication Complexity
• Area laws and tensor networks for maximally mixed ground states

This page was built for publication: New One Shot Quantum Protocols With Application to Communication Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976478)