Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity

Physics – Quantum Physics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

20 pages, no figures

Scientific paper

We consider the problem of bounded-error quantum state identification: given either state \alpha_0 or state \alpha_1, we are required to output `0', `1' or `?' ("don't know"), such that conditioned on outputting `0' or `1', our guess is correct with high probability. The goal is to maximize the probability of not outputting `?'. We prove a direct product theorem: if we're given two such problems, with optimal probabilities a and b, respectively, and the states in the first problem are pure, then the optimal probability for the joint bounded-error state identification problem is O(ab). Our proof is based on semidefinite programming duality and may be of wider interest. Using this result, we present two exponential separations in the simultaneous message passing model of communication complexity. Both are shown in the strongest possible sense. First, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared randomness, but needs Omega(n^{1/3}) communication if the parties don't share randomness, even if communication is quantum. This shows the optimality of Yao's recent exponential simulation of shared-randomness protocols by quantum protocols without shared randomness. Second, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared entanglement, but needs Omega((n/log n)^{1/3}) communication if the parties share randomness but no entanglement, even if communication is quantum. This is the first example in communication complexity of a situation where entanglement buys you much more than quantum communication does.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Bounded-Error Quantum State Identification and Exponential Separations in 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 Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-639980

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.