  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) =
\widetilde{O}\left(Q^7(f)\right)$. In this paper, we improve this result and
show that $R(f) = {O}\left(Q^3(f)\right)$ 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].
