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 ( n 3 4 − 1 (2 k ) ) . 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 ] [ n ] is ( 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 ( 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 ( 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 ( 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 ( n 3 4 ) . The best prior lower bound was ( n 2 3 ) . Our result matches an upper bound of O ( n 3 4 ) due to Sherstov, which we reprove using different techniques. The quantum query complexity of this function is known to be ( n ) (Beame and Machmouchi, Quantum Inf. Comput. 2012 and Sherstov, FOCS 2015).