Name
Abstract | ||
|---|---|---|
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 Omega(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 Omega(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(N^{3/4}) that applies whenever k <= polylog(N). |
Year | DOI | Venue |
|---|---|---|
2020 | 10.4230/LIPIcs.TQC.2020.2 | TQC |
DocType | Volume | Citations |
Conference | 27 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mande Nikhil S. | 1 | 5 | 4.13 |
| Thaler Justin | 2 | 273 | 20.17 |
| Zhu Shuchen | 3 | 0 | 0.34 |