  Aaronson and Ambainis (SICOMP `18) showed that any partial function on $N$
bits that can be computed with an advantage $\delta$ over a random guess by
making $q$ quantum queries, can also be computed classically with an advantage
$\delta/2$ by a randomized decision tree making
${O}_q(N^{1-\frac{1}{2q}}\delta^{-2})$ queries. Moreover, they conjectured the
$k$-Forrelation problem -- a partial function that can be computed with $q =
\lceil k/2 \rceil$ quantum queries -- to be a suitable candidate for exhibiting
such an extremal separation.
  We prove their conjecture by showing a tight lower bound of
$\widetilde{\Omega}(N^{1-1/k})$ for the randomized query complexity of
$k$-Forrelation, where the advantage $\delta = 2^{-O(k)}$. By standard
amplification arguments, this gives an explicit partial function that exhibits
an $O_\epsilon(1)$ vs $\Omega(N^{1-\epsilon})$ separation between bounded-error
quantum and randomized query complexities, where $\epsilon>0$ can be made
arbitrarily small. Our proof also gives the same bound for the closely related
but non-explicit $k$-Rorrelation function introduced by Tal (FOCS `20).
  Our techniques rely on classical Gaussian tools, in particular, Gaussian
interpolation and Gaussian integration by parts, and in fact, give a more
general statement. We show that to prove lower bounds for $k$-Forrelation
against a family of functions, it suffices to bound the $\ell_1$-weight of the
Fourier coefficients between levels $k$ and $(k-1)k$. We also prove new
interpolation and integration by parts identities that might be of independent
interest in the context of rounding high-dimensional Gaussian vectors.
