On quantum-classical equivalence for composed communication problems
On quantum-classical equivalence for composed communication problems
复制标题
DOI：
10.26421/qic10.5-6-5
复制
发表时间：
2009-06
期刊：
影响因子：
--
通讯作者：
Alexander A. Sherstov
中科院分区：
文献类型：
--
作者：
Alexander A. Sherstov
几位作者提出的通信复杂性的一个公开问题是证明对于每个布尔函数f，计算f（x AND y）的任务具有多项式相关的经典和量子有界错误复杂性。我们解决这个问题的一个变体。对于每一个f，我们证明了计算的任务，在输入x和y，数量f（x和y）和f（x或y）多项式相关的经典和量子有界误差复杂性。我们进一步证明了量子有界错误复杂度与经典确定性复杂度和f的块敏感性是多项式相关的。这个结果与先前的纠缠无关。
An open problem in communication complexity proposed by several authors is to prove that for every Boolean function f, the task of computing f(x AND y) has polynomially related classical and quantum bounded-error complexities. We solve a variant of this question. For every f, we prove that the task of computing, on input x and y, both of the quantities f(x AND y) and f(x OR y) has polynomially related classical and quantum bounded-error complexities. We further show that the quantum bounded-error complexity is polynomially related to the classical deterministic complexity and the block sensitivity of f. This result holds regardless of prior entanglement.