NEAR-OPTIMAL BOUNDS ON THE BOUNDED-ROUND QUANTUM COMMUNICATION COMPLEXITY OF DISJOINTNESS

被引：4

作者：

Braverman, Mark ^{[1
]}

Garg, Ankit ^{[2
]}

Ko, Young Kun ^{[1
]}

Mao, Jieming ^{[1
]}

Touchette, Dave ^{[3
,4
,5
]}

机构：

[1] Princeton Univ, Dept Comp Sci, Princeton, NJ 08540 USA

[2] Microsoft Res New England, Cambridge, MA 02142 USA

[3] Univ Waterloo, Inst Quantum Comp, Waterloo, ON N2L 3G1, Canada

[4] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada

[5] Perimeter Inst Theoret Phys, Waterloo, ON N2L 2YS, Canada

来源：

SIAM JOURNAL ON COMPUTING | 2018年 / 47卷 / 06期

基金：

加拿大自然科学与工程研究理事会;

关键词：

disjointness; quantum communication complexity; quantum information complexity; CONDITIONAL MUTUAL INFORMATION; DIRECT-PRODUCT THEOREMS; ONE-WAY COMMUNICATION; EXPONENTIAL SEPARATION;

D O I：

10.1137/16M1061400

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 (Omega) over tilde (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 Omega(n/r(2) + r) due to Jain, Radhakrishnan and Sen [Proceedings of FOGS, 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).

引用

页码：2277 / 2314

页数：38