  We study the forrelation problem: given a pair of $n$-bit Boolean functions
$f$ and $g$, estimate the correlation between $f$ and the Fourier transform of
$g$. This problem is known to provide the largest possible quantum speedup in
terms of its query complexity and achieves the landmark oracle separation
between the complexity class BQP and the Polynomial Hierarchy. Our first result
is a classical algorithm for the forrelation problem which has runtime
$O(n2^{n/2})$. This is a nearly quadratic improvement over the best previously
known algorithm. Secondly, we show that quantum query algorithm that makes $t$
queries to an $n$-bit oracle can be simulated by classical query algorithm
making only $O(2^{n(1-1/2t)})$ queries. This fixes a gap in the literature
arising from a recently discovered critical error in a previous proof; it
matches recently established lower bounds (up to $poly(n,t))$ factors) and thus
characterizes the maximal separation in query complexity between quantum and
classical algorithms. Finally, we introduce a graph-based forrelation problem
where $n$ binary variables live at vertices of some fixed graph and the
functions $f,g$ are products of terms describing interactions between
nearest-neighbor variables. We show that the graph-based forrelation problem
can be solved on a classical computer in time $O(n)$ for any bipartite graph,
any planar graph, or, more generally, any graph which can be partitioned into
two subgraphs of constant treewidth. The graph-based forrelation is simply
related to the variational energy achieved by the Quantum Approximate
Optimization Algorithm (QAOA) with two entangling layers and Ising-type cost
functions. By exploiting the connection between QAOA and the graph-based
forrelation we were able to simulate the recently proposed Recursive QAOA with
two entangling layers and $225$ qubits on a laptop computer.
