ECCC-Report TR15-081https://eccc.weizmann.ac.il/report/2015/081Comments and Revisions published for TR15-081en-usTue, 12 May 2015 19:30:01 +0300
Paper TR15-081
| Near-optimal bounds on bounded-round quantum communication complexity of disjointness |
Ankit Garg,
Mark Braverman,
Jieming Mao,
Young Kun Ko,
Dave Touchette
https://eccc.weizmann.ac.il/report/2015/081We 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$).Tue, 12 May 2015 19:30:01 +0300https://eccc.weizmann.ac.il/report/2015/081