论文标题
提高了k-distristness的近似程度界限
Improved Approximate Degree Bounds For k-distinctness
论文作者
论文摘要
一个被广泛认为是量子查询复杂性最重要的开放问题是解决k-distinctness在尺寸N的输入上的量子查询复杂性。尽管K = 2的情况（也称为元素独特性）是充分理解的，但在所有已知的上限和下限之间存在多项式差距，用于所有常数和下限，所有常数k> 2> 2> 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）。 对于任何常数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).
