Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR17-169 | 24th October 2017 22:29

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials

RSS-Feed




TR17-169
Authors: Mark Bun, Robin Kothari, Justin Thaler
Publication: 6th November 2017 15:04
Downloads: 74
Keywords: 


Abstract:

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. The approximate degree of $f$ is known to be a lower bound on the quantum query complexity of $f$ (Beals et al., FOCS 1998 and J. ACM 2001).

We resolve or nearly resolve the approximate degree and quantum query complexities of several basic functions. Specifically, we show the following:

*$k$-distinctness: For any constant $k$, the approximate degree and quantum query complexity of the $k$-distinctness function is $\Omega(n^{3/4-1/(2k)})$. This is nearly tight for large $k$, as Belovs (FOCS 2012) has shown that for any constant $k$, the approximate degree and quantum query complexity of $k$-distinctness is $O(n^{3/4-1/(2^{k+2}-4)})$.

*Image Size Testing: The approximate degree and quantum query complexity of testing the size of the image of a function $[n] \to [n]$ is $\tilde{\Omega}(n^{1/2})$. This proves a conjecture of Ambainis et al. (SODA 2016), and it implies tight lower bounds on the approximate degree and quantum query complexity of the following natural problems.

**$k$-junta testing: A tight $\tilde{\Omega}(k^{1/2})$ lower bound for $k$-junta testing, answering the main open question of Ambainis et al. (SODA 2016).

**Statistical Distance from Uniform: A tight $\tilde{\Omega}(n^{1/2})$ lower bound for approximating the statistical distance from uniform of a distribution, answering the main question left open by Bravyi et al.\ (STACS 2010 and IEEE Trans.\ Inf.\ Theory 2011).

**Shannon entropy: A tight $\tilde{\Omega}(n^{1/2})$ lower bound for approximating Shannon entropy up to a certain additive constant, answering a question of Li and Wu (2017).

*Surjectivity: The approximate degree of the Surjectivity function is $\tilde{\Omega}(n^{3/4})$. The best prior lower bound was $\Omega(n^{2/3})$. Our result matches an upper bound of $\tilde{O}(n^{3/4})$ due to Sherstov, which we reprove using different techniques. The quantum query complexity of this function is known to be $\Theta(n)$ (Beame and Machmouchi, Quantum Inf. Comput. 2012 and Sherstov, FOCS 2015).

Our upper bound for Surjectivity introduces new techniques for approximating Boolean functions by low-degree polynomials. Our lower bounds are proved by significantly refining techniques recently introduced by Bun and Thaler (FOCS 2017).



ISSN 1433-8092 | Imprint