  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 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 dscribing interactions between nearest-neighbor
variables. We show that the graph-based forrelation problem can be solved on a
classical computer in time $O(n^2)$ 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 Recurisve QAOA with two entangling layers and
225 qubits on a laptop computer.
