Near-optimal bounds on the bounded-round quantum communication complexity of disjointness

Mark Braverman, Ankit Garg, Young K.U.N. Ko, M. A.O. Jieming, Dave Touchette

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with r rounds, we prove a lower bound of Ω(n/r + r) on the communication required for computing disjointness of input size n, which is optimal up to logarithmic factors. The previous best lower bound was Ω(n/r 2 + r) due to Jain, Radhakrishnan and Sen [Proceedings of FOCS, 2003, pp. 220-229]. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any Boolean function f is at most 2 O (QIC(f)), where QIC(f) is the prior-free quantum information complexity of f (with error 1/3).

Original languageEnglish (US)
Pages (from-to)2277-2314
Number of pages38
JournalSIAM Journal on Computing
Volume47
Issue number6
DOIs
StatePublished - Jan 1 2018

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Disjointness
  • Quantum communication complexity
  • Quantum information complexity

Fingerprint Dive into the research topics of 'Near-optimal bounds on the bounded-round quantum communication complexity of disjointness'. Together they form a unique fingerprint.

  • Cite this