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

## Author(s): Braverman, Mark; Garg, Ankit; Ko, Young K; Mao, Jieming; Touchette, Dave

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1bz4f
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorGarg, Ankit-
dc.contributor.authorKo, Young K-
dc.contributor.authorMao, Jieming-
dc.contributor.authorTouchette, Dave-
dc.date.accessioned2021-10-08T19:45:13Z-
dc.date.available2021-10-08T19:45:13Z-
dc.date.issued2018en_US
dc.identifier.citationBraverman, Mark, Ankit Garg, Young Kun Ko, Jieming Mao, and Dave Touchette. "Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness." SIAM Journal on Computing 47, no. 6 (2018): pp. 2277-2314. doi:10.1137/16M1061400en_US
dc.identifier.issn0097-5397-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1bz4f-
dc.description.abstractWe 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/r2 + 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 2O(QIC(f)), where QIC(f) is the prior-free quantum information complexity of f (with error 1/3).en_US
dc.format.extent2277 - 2314en_US
dc.language.isoen_USen_US
dc.relation.ispartofSIAM Journal on Computingen_US
dc.rightsAuthor's manuscripten_US
dc.titleNear-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointnessen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1137/16M1061400-
dc.identifier.eissn1095-7111-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat