文章基本信息

标题：Strong Direct Product Theorems for Quantum Communication and Query Complexity
本地全文：下载
作者：Alexander A. Sherstov
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：A strong direct product theorem (SDPT) states that solving n instances of a problem requires (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.
关键词：Quantum communication complexity, quantum query complexity, strong direct product theorems, XOR Lemmas