2026-07-22T15:59:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12061 2024-03-06T10:49:11Z ddc:004 open_access

Improved Approximate Degree Bounds for k-Distinctness Mande, Nikhil S. Thaler, Justin Zhu, Shuchen Quantum Query Complexity Approximate Degree Dual Polynomials k-distinctness 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 Ω̃(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 Ω̃(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 Õ(N^{3/4}) that applies whenever k ≤ polylog(N). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil S. Mande and Justin Thaler and Shuchen Zhu 2020 Is Part Of LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2020.2 urn:nbn:de:0030-drops-120613 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.2 eng https://creativecommons.org/licenses/by/3.0/legalcode