Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2008-07-08
Computer Science
Distributed, Parallel, and Cluster Computing
Full version (version 1), 31 pages, 4 figures
Scientific paper
We show optimal Direct Sum result for the one-way entanglement-assisted quantum communication complexity for any relation f subset of X x Y x Z. We show: Q^{1,pub}(f^m) = Omega(m Q^{1,pub}(f)), where Q^{1,pub}(f), represents the one-way entanglement-assisted quantum communication complexity of f with error at most 1/3 and f^m represents m-copies of f. Similarly for the one-way public-coin classical communication complexity we show: R^{1,pub}(f^m) = Omega(m R^{1,pub}(f)), where R^{1,pub}(f), represents the one-way public-coin classical communication complexity of f with error at most 1/3. We show similar optimal Direct Sum results for the Simultaneous Message Passing quantum and classical models. For two-way protocols we present optimal Privacy Trade-off results leading to a Weak Direct Sum result for such protocols. We show our Direct Sum and Privacy Trade-off results via message compression arguments which also imply a new round elimination lemma in quantum communication. This allows us to extend 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 and Predecessor Search to the quantum setting. In a separate result we show that Newman's 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 black-box reduction of prior entanglement that subsumes Newman's technique. We prove that such a black-box reduction is impossible for quantum protocols. In the final result in the theme of message compression, we provide an upper bound on the problem of Exact Remote State Preparation.
Jain Rahul
Radhakrishnan Jaikumar
Sen Pranab
No associations
LandOfFree
Optimal Direct Sum and Privacy Trade-off Results for Quantum and Classical Communication Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Optimal Direct Sum and Privacy Trade-off Results for Quantum and Classical Communication Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Direct Sum and Privacy Trade-off Results for Quantum and Classical Communication Complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-268982