DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2020.2

Improved Approximate Degree Bounds for k-Distinctness

Authors: Nikhil S. Mande, Justin Thaler, and Shuchen Zhu

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

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 Ω̃(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 Õ(N^{3/4}) that applies whenever k ≤ polylog(N).

Cite as

Nikhil S. Mande, Justin Thaler, and Shuchen Zhu. Improved Approximate Degree Bounds for k-Distinctness. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mande_et_al:LIPIcs.TQC.2020.2,
  author =	{Mande, Nikhil S. and Thaler, Justin and Zhu, Shuchen},
  title =	{{Improved Approximate Degree Bounds for k-Distinctness}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{2:1--2:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.2},
  URN =		{urn:nbn:de:0030-drops-120613},
  doi =		{10.4230/LIPIcs.TQC.2020.2},
  annote =	{Keywords: Quantum Query Complexity, Approximate Degree, Dual Polynomials, k-distinctness}
}

Search Results

Documents authored by Zhu, Shuchen

Improved Approximate Degree Bounds for k-Distinctness

Abstract

Cite as

Thanks for your feedback!

Could not send message