## 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 Ω(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/r ^{2} + 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 2 ^{O} (QIC(f)), where QIC(f) is the prior-free quantum information complexity of f (with error 1/3).

Original language | English (US) |
---|---|

Pages (from-to) | 2277-2314 |

Number of pages | 38 |

Journal | SIAM Journal on Computing |

Volume | 47 |

Issue number | 6 |

DOIs | |

State | Published - 2018 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics

## Keywords

- Disjointness
- Quantum communication complexity
- Quantum information complexity