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

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

2005-11-02

arxiv.org/abs/quant-ph/0511013v1

Physics

Quantum Physics

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.

Affiliated with

Also associated with

No associations

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

Comments { 0 }

Profile ID: LFWR-SCP-O-639980