Classical algorithms for Forrelation

Understand

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.