To refer to this page use:
|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).|
|Electronic Publication Date:||2015|
|Citation:||Braverman, 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.53|
|Pages:||773 - 791|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.