TY - GEN
T1 - Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness
AU - Braverman, Mark
AU - Garg, Ankit
AU - Ko, Young Kun
AU - Mao, Jieming
AU - Touchette, Dave
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/12/11
Y1 - 2015/12/11
N2 - 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).
AB - 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).
UR - http://www.scopus.com/inward/record.url?scp=84960358030&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84960358030&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2015.53
DO - 10.1109/FOCS.2015.53
M3 - Conference contribution
AN - SCOPUS:84960358030
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 773
EP - 791
BT - Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PB - IEEE Computer Society
T2 - 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
Y2 - 17 October 2015 through 20 October 2015
ER -