Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness

Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette

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

9 Scopus citations

Abstract

We prove a near optimal round-communication trade off for the two-party quantum communication complexity of disjointness. For protocols with r rounds, we prove a lower bound of Ω(n/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/r2) due to Jain, Radha krishnan and Sen. 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 2O(QIC(f)), where QIC(f) is the prior-free quantum information complexity of f (with error 1/3).

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PublisherIEEE Computer Society
Pages773-791
Number of pages19
ISBN (Electronic)9781467381918
DOIs
StatePublished - Dec 11 2015
Event56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States
Duration: Oct 17 2015Oct 20 2015

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2015-December
ISSN (Print)0272-5428

Other

Other56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
CountryUnited States
CityBerkeley
Period10/17/1510/20/15

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Garg, A., Ko, Y. K., Mao, J., & Touchette, D. (2015). Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness. In Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 (pp. 773-791). [7354427] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2015-December). IEEE Computer Society. https://doi.org/10.1109/FOCS.2015.53