5 years ago

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

Mark Bun, Justin Thaler, Robin Kothari

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. Approximate degree is known to be a lower bound on quantum query complexity. We resolve or nearly resolve the approximate degree and quantum query complexities of the following basic functions:

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

$\bullet$ 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 the following lower bounds:

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

$-$ Statistical Distance from Uniform: A tight $\tilde{\Omega}(n^{1/2})$ lower bound, 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, answering a question of Li and Wu (2017).

$\bullet$ 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, QIC 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).

Publisher URL: http://arxiv.org/abs/1710.09079

DOI: arXiv:1710.09079v2

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

Researcher displays publicly available abstracts and doesnâ€™t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.