  The query model offers a concrete setting where quantum algorithms are
provably superior to randomized algorithms. Beautiful results by
Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean
functions that can be computed by quantum algorithms making much fewer queries
compared to their randomized analogs. To date, separations of $O(1)$ vs.
$\sqrt{N}$ between quantum and randomized query complexities remain the
state-of-the-art (where $N$ is the input length), leaving open the question of
whether $O(1)$ vs. $N^{1/2+\Omega(1)}$ separations are possible? We answer this
question in the affirmative. Our separating problem is a variant of the
Aaronson-Ambainis $k$-fold Forrelation problem. We show that our variant:
  (1) Can be solved by a quantum algorithm making $2^{O(k)}$ queries to the
inputs.
  (2) Requires at least $\tilde{\Omega}(N^{2(k-1)/(3k-1)})$ queries for any
randomized algorithm.
  For any constant $\varepsilon>0$, this gives a $O(1)$ vs.
$N^{2/3-\varepsilon}$ separation between the quantum and randomized query
complexities of partial Boolean functions. Our proof is Fourier analytical and
uses new bounds on the Fourier spectrum of classical decision trees, which
could be of independent interest. Looking forward, we conjecture that the
Fourier bounds could be further improved in a precise manner, and show that
such conjectured bounds imply optimal $O(1)$ vs. $N^{1-\varepsilon}$
separations between the quantum and randomized query complexities of partial
Boolean functions.
