The communication complexity of the Hamming distance problem
The communication complexity of the Hamming distance problem
复制标题
DOI：
10.1016/j.ipl.2006.01.014
复制
发表时间：
2006-08-31
影响因子：
0.5
通讯作者：
Zhu, Yufan
中科院分区：
文献类型：
--
作者：
Huang, Wei;Shi, Yaoyun;Zhu, Yufan
我们研究汉明距离问题的随机通信复杂度和量子通信复杂度，该问题是确定两个\(n\)位字符串之间的汉明距离是否不小于阈值\(d\)。我们在具有共享先验纠缠的一般交互模型中证明了\(\Omega(d)\)个量子比特的量子下界。我们还在具有公共随机硬币的受限同时消息传递模型中构建了一个\(O(d\log d)\)位的经典协议，改进了之前\(O(d^{2})\)位的协议[A.C.-C. 姚，《论量子指纹的能力》，载于：第35届美国计算机协会计算理论年会论文集，2003年，第77 - 81页]以及\(O(d\log n)\)位的协议[D. 加文斯基，J. 肯普，R. 德沃尔夫，《量子通信无法模拟公共硬币》，quant - ph/0411051，2004]。（c）2006年由爱思唯尔科学出版社出版
We investigate the randomized and quantum communication complexity of the HAMMING DISTANCE problem, which is to determine if the Hamming distance between two n-bit strings is no less than a threshold d. We prove a quantum lower bound of Omega (d) qubits in the general interactive model with shared prior entanglement. We also construct a classical protocol of O(d log d) bits in the restricted Simultaneous Message Passing model with public random coins, improving previous protocols of O(d(2)) bits [A.C.-C. Yao, On the power of quantum fingerprinting, in: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 77-81], and O(d log n) bits [D. Gavinsky, J. Kempe, R. de Wolf, Quantum communication cannot simulate a public coin, quant-ph/0411051, 2004]. (c) 2006 Published by Elsevier B.V.