The one-way communication complexity of the Boolean Hidden Matching Problem
The one-way communication complexity of the Boolean Hidden Matching Problem
复制标题
布尔隐藏匹配问题的单向通信复杂度
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
R. Raz
中科院分区：
文献类型：
--
作者：
Iordanis Kerenidis;R. Raz
我们给出了布尔隐藏匹配问题[BJK04]的随机单向通信复杂度(p，n)的一个紧下界。由于该问题存在O(Logn)个量子比特的量子单向通信复杂性协议，我们得到了部分函数的量子单向通信复杂性与经典单向通信复杂性的指数分离。Gavinsky，Kempe，De Wolf[GKdW06]也独立得到了类似的结果。我们的下界是通过傅里叶分析，利用Kahn Kalai和Linial[KKL88]的傅立叶分量不等式得到的。
We give a tight lower bound of ( p n) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(logn) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. A similar result was independently obtained by Gavinsky, Kempe, de Wolf [GKdW06]. Our lower bound is obtained by Fourier analysis, using the Fourier coecients inequality of Kahn Kalai and Linial [KKL88].