Quantum versus randomized communication complexity, with efficient players

Uma Girish, Ran Raz, Avishay Tal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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 [8] and is obtained using a quantum protocol where all parties are efficient. More precisely, we give 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 [8]. 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 [10, 5]. 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 [15]. Our function f is based on a lift of the forrelation problem, using xor as a gadget.

Original languageEnglish (US)
Title of host publication12th Innovations in Theoretical Computer Science Conference, ITCS 2021
EditorsJames R. Lee
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771771
DOIs
StatePublished - Feb 1 2021
Event12th Innovations in Theoretical Computer Science Conference, ITCS 2021 - Virtual, Online
Duration: Jan 6 2021Jan 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume185
ISSN (Print)1868-8969

Conference

Conference12th Innovations in Theoretical Computer Science Conference, ITCS 2021
CityVirtual, Online
Period1/6/211/8/21

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Communication
  • Complexity
  • Exponential separation
  • Forrelation
  • Quantum
  • Randomized

Fingerprint

Dive into the research topics of 'Quantum versus randomized communication complexity, with efficient players'. Together they form a unique fingerprint.

Cite this