Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-081 | 12th May 2015 17:55

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

RSS-Feed

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 \tilde{\Omega}(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 \Omega(n/r^2) due to Jain, Radhakrishnan 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 2^{O(QIC(f))}, where QIC(f) is the prior-free quantum information complexity of f (with error 1/3).



ISSN 1433-8092 | Imprint