Abstract
It is known since the work of [AA14] that for any permutation symmetric function f, the quantum query complexity is at most polynomially smaller than the classical randomized query complexity, more precisely that R(f) = O(Q⁷(f)). In this paper, we improve this result and show that R(f) = O(Q³(f)) for a more general class of symmetric functions. Our proof is constructive and relies largely on the quantum hardness of distinguishing a random permutation from a random function with small range from Zhandry [Zha15].