Strong direct product theorems for quantum communication and query complexity
Strong direct product theorems for quantum communication and query complexity
复制标题
DOI：
10.1145/1993636.1993643
复制
发表时间：
2010-11
期刊：
影响因子：
--
通讯作者：
Alexander A. Sherstov
中科院分区：
文献类型：
--
作者：
Alexander A. Sherstov
强大的直接产品理论（SDPT）指出，解决问题的n实例需要欧米茄（n）乘以单个实例的资源，即使达到成功概率2-ω（n），我们证明了量子通信的复杂性。每当通过广义差异方法证明单个实例的通信下限时，我们就会证明，每当查询较低限制的量子单个实例是通过多项式方法证明的，这是该模型中的两个主要技术之一。
A strong direct product theorem (SDPT) states that solving n instances of a problem requires Omega(n) times the resources for a single instance, even to achieve success probability 2-Ω(n). We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by the generalized discrepancy method, the strongest technique in that model. We prove that quantum query complexity obeys an SDPT whenever the query lower bound for a single instance is proved by the polynomial method, one of the two main techniques in that model. In both models, we prove the corresponding XOR lemmas and threshold direct product theorems.