Improved Approximate Degree Bounds For k-distinctness
Improved Approximate Degree Bounds For k-distinctness
复制标题
DOI：
10.4230/lipics.tqc.2020.2
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Nikhil S. Mande;J. Thaler;Shuchen Zhu
中科院分区：
文献类型：
--
作者：
Nikhil S. Mande;J. Thaler;Shuchen Zhu
一个被广泛认为是量子查询复杂度中最重要的问题之一的公开问题是解决输入大小为N的k-独特性函数的量子查询复杂度。虽然k=2的情况（也称为元素区分度）是很好理解的，但对于所有常数k>2，已知的上限和下限之间存在多项式间隙。具体地，最公知的上限是O（N^{（3/4）-1/（2^{k+2}-4）}）（Belovs，FOCS 2012），而k >= 2的最公知的下限是Omega（N^{2/3} + N^{（3/4）-1/（2k）}）（Aaronson and Shi，J. ACM 2004; Bun，Kothari和Thaler，STOC 2018）。对于任意常数k >= 4，我们将下界改进为Omega（N^{（3/4）-1/（4k）}）。例如，这产生了第一个证明，即4-区别性严格比元素区别性更难。我们的下界更一般地适用于近似度。作为第二个结果，我们给出了一个简单的构造近似多项式的次数为O（N^{3/4}），适用于任何时候k <= polylog（N）。
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).