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

Author(s): Braverman, Mark; Garg, A; Ko, YK; Mao, J; Touchette, D

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1r38r
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorGarg, A-
dc.contributor.authorKo, YK-
dc.contributor.authorMao, J-
dc.contributor.authorTouchette, D-
dc.date.accessioned2018-07-20T15:11:03Z-
dc.date.available2018-07-20T15:11:03Z-
dc.date.issued2015-12-17en_US
dc.identifier.citationBraverman, M, Garg, A, Ko, YK, Mao, J, Touchette, D. (2015). Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness. 2015-December (773 - 791. doi:10.1109/FOCS.2015.53en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1r38r-
dc.description.abstractWe 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).en_US
dc.format.extent773 - 791en_US
dc.language.isoen_USen_US
dc.relation.ispartofProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCSen_US
dc.rightsAuthor's manuscripten_US
dc.titleNear-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointnessen_US
dc.typeConference Articleen_US
dc.identifier.doidoi:10.1109/FOCS.2015.53-
dc.date.eissued2015en_US
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat
Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness.pdf331.88 kBAdobe PDF