Name
Title | ||
|---|---|---|
Near-optimal bounds on bounded-round quantum communication complexity of disjointness. |
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). |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/FOCS.2015.53 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
prior-free quantum information complexity,Boolean function,generalized discrepancy method,logarithmic factors,protocols,two-party quantum communication complexity,near optimal round-communication,disjointness,bounded-round quantum communication complexity,near-optimal bounds | Quantum complexity theory,Discrete mathematics,Combinatorics,Quantum information science,Mathematics,Bounded function | Journal |
Volume | ISSN | Citations |
22 | 0272-5428 | 7 |
PageRank | References | Authors |
0.47 | 36 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Braverman | 1 | 810 | 61.60 |
| Ankit Garg | 2 | 125 | 16.19 |
| Young Kun-Ko | 3 | 40 | 4.24 |
| Jieming Mao | 4 | 54 | 9.19 |
| Dave Touchette | 5 | 31 | 3.42 |