TY - JOUR
T1 - Quantum versus Randomized Communication Complexity, with Efficient Players
AU - Girish, Uma
AU - Raz, Ran
AU - Tal, Avishay
N1 - Funding Information:
The first two authors are supported by the Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award, by the National Science Foundation Grants No. CCF-1714779 and 2007462. The third author is partially supported by a Motwani Postdoctoral Fellowship and by NSF Grant CCF-1763311.
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Nature Switzerland AG.
PY - 2022/12
Y1 - 2022/12
N2 - We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs.Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, wegive an explicit partial Boolean function f over inputs of length N, such that:(1)f can be computed by a simultaneous-message quantum protocol with communication complexity polylog(N)(where at the beginning of the protocol Alice and Bob also have polylog(N) entangled EPR pairs).(2)Any classical randomized protocol for f, with any number of rounds, has communication complexity at least Ω ~ (N1 / 4).(3)All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog(N) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of Ω (N1 / 2) in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.
AB - We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs.Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, wegive an explicit partial Boolean function f over inputs of length N, such that:(1)f can be computed by a simultaneous-message quantum protocol with communication complexity polylog(N)(where at the beginning of the protocol Alice and Bob also have polylog(N) entangled EPR pairs).(2)Any classical randomized protocol for f, with any number of rounds, has communication complexity at least Ω ~ (N1 / 4).(3)All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog(N) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of Ω (N1 / 2) in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.
KW - 68Q11
KW - 68Q12
KW - Communication Complexity
KW - ExponentialSeparation
KW - Quantum
KW - Randomized
UR - http://www.scopus.com/inward/record.url?scp=85140748300&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85140748300&partnerID=8YFLogxK
U2 - 10.1007/s00037-022-00232-7
DO - 10.1007/s00037-022-00232-7
M3 - Article
AN - SCOPUS:85140748300
SN - 1016-3328
VL - 31
JO - Computational Complexity
JF - Computational Complexity
IS - 2
M1 - 17
ER -