Theory of Computing
-------------------
Title     : The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Authors   : Mark Bun, Robin Kothari, and Justin Thaler
Volume    : 16
Number    : 10
Pages     : 1-71
URL       : https://theoryofcomputing.org/articles/v016a010

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 find tight or nearly tight bounds on 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 of a distribution from uniform, 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 (STOC 2018), 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).