TY - JOUR

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

N1 - Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 2009

Y1 - 2009

N2 - We consider the following problem of bounded-error quantum state identification: Given either state a0 or state a1, 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 the following direct product theorem: If we are 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. 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. Combined with an earlier separation in the other direction due to Bar-Yossef, Jayram, and Kerenidis, this shows that the quantum simultaneous message passing (SMP) model is incomparable with the classical shared-randomness SMP model. 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 of a situation where entanglement buys much more than quantum communication.

AB - We consider the following problem of bounded-error quantum state identification: Given either state a0 or state a1, 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 the following direct product theorem: If we are 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. 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. Combined with an earlier separation in the other direction due to Bar-Yossef, Jayram, and Kerenidis, this shows that the quantum simultaneous message passing (SMP) model is incomparable with the classical shared-randomness SMP model. 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 of a situation where entanglement buys much more than quantum communication.

KW - Communication complexity

KW - Duality

KW - Entanglement

KW - Exponential separations

KW - Quantum communication

KW - Semidefinite programs

KW - State identification

UR - http://www.scopus.com/inward/record.url?scp=67650118855&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67650118855&partnerID=8YFLogxK

U2 - 10.1137/060665798

DO - 10.1137/060665798

M3 - Article

AN - SCOPUS:67650118855

VL - 39

SP - 1

EP - 24

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 1

ER -