Jain, R. ; Radhakrishnan, J. ; Sen, P. (2005) Prior entanglement, message compression and privacy in quantum communication Proceedings  IEEE Conference on Computational Complexity . pp. 285296. ISSN 10930159

PDF
 Author Version
162kB 
Official URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumb...
Related URL: http://dx.doi.org/10.1109/CCC.2005.24
Abstract
Consider a twoparty quantum communication protocol for computing some function f : {0, 1}^{n} × {0, 1}^{n} → Z. We show that the first message of P can be compressed to 0(k) classical bits using prior entanglement if it carries at most k bits of information about the sender's input. This implies a general direct sum result for oneround and simultaneous quantum protocols. It also implies a new round elimination lemma in quantum communication, which allows us to extend recent classical lower bounds on the cell probe complexity of some data structure problems, e.g. approximate nearest neighbor searching on the Hamming cube {0, 1}^{n}, to the quantum setting. We then show an optimal tradeoff between the privacy losses of Alice and Bob in computing f in terms of the oneround quantum communication complexity of f with prior entanglement. This tradeoff is independent of the number of rounds of communication. The above message compression and privacy tradeoff results use a lot of qubits of prior entanglement, leading one to wonder how much prior entanglement is really required by a quantum protocol. We show that Newman's [1991] technique of reducing the number of public coins in a classical protocol cannot be lifted to the quantum setting. We do this by defining a general notion of blackbox reduction of prior entanglement that subsumes Newman's technique. Intuitively, a blackbox reduction does not change the unitary transforms of Alice and Bob; it only decreases the amount of entanglement of the prior entangled state. We prove that such a blackbox reduction is impossible for quantum protocols by exhibiting a particular oneround quantum protocol for the equality function where the blackbox technique fails to reduce the amount of prior entanglement by more than a constant factor.
Item Type:  Article 

Source:  Copyright of this article belongs to IEEE. 
ID Code:  89501 
Deposited On:  27 Apr 2012 13:40 
Last Modified:  19 May 2016 04:02 
Repository Staff Only: item control page