TY - GEN
T1 - Bounded-error quantum state identification and exponential separations in communication complexity
AU - Gavinsky, Dmitry
AU - Kempe, Julia
AU - Regev, Oded
AU - De Wolf, Ronald
PY - 2006
Y1 - 2006
N2 - We consider the problem of bounded-error quantum state identification: given either state α0 or state α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. 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 Ω(n1/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 Ω((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 where entanglement buys you much more than quantum communication does.
AB - We consider the problem of bounded-error quantum state identification: given either state α0 or state α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. 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 Ω(n1/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 Ω((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 where entanglement buys you much more than quantum communication does.
KW - Communication complexity
KW - Entanglement
KW - Quantum computing
KW - Randomness
KW - State identification
UR - http://www.scopus.com/inward/record.url?scp=33748093058&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748093058&partnerID=8YFLogxK
U2 - 10.1145/1132516.1132602
DO - 10.1145/1132516.1132602
M3 - Conference contribution
AN - SCOPUS:33748093058
SN - 1595931341
SN - 9781595931344
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 594
EP - 603
BT - STOC'06
PB - Association for Computing Machinery
T2 - 38th Annual ACM Symposium on Theory of Computing, STOC'06
Y2 - 21 May 2006 through 23 May 2006
ER -