文章基本信息

标题：Improved Approximate Degree Bounds For k -distinctness
本地全文：下载
作者：Nikhil Mande ; Justin Thaler ; Shuchen Zhu 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-41
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs of size N. While the case of k = 2 (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants k > 2. Specifically, the best known upper bound is O N(3/4)−1/(2k 2−4) (Belovs, FOCS 2012), while the best known lower bound for k ≥ 2 is Ω˜ N2/3 N(3/4)−1/(2k) (Aaronson and Shi, J. ACM 2004; Bun, Kothari, and Thaler, STOC 2018). For any constant k ≥ 4, we improve the lower bound to Ω˜ N(3/4)−1/(4k) . This yields, for example, the first proof that 4-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree. As a secondary result, we give a simple construction of an approximating polynomial of degree O˜(N3/4 ) that applies whenever k ≤ polylog(N).