文章基本信息
- 标题：Improved Approximate Degree Bounds for k-Distinctness
- 本地全文：下载
- 作者：Nikhil S. Mande ; Justin Thaler ; Shuchen Zhu 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：158
- 页码：2:1-2:22
- DOI：10.4230/LIPIcs.TQC.2020.2
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the best known lower bound for k⥠2 is ΩÌf(N^{2/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 ΩÌf(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Ìf(N^{3/4}) that applies whenever k ⤠polylog(N).
- 关键词：Quantum Query Complexity; Approximate Degree; Dual Polynomials; k-distinctness
