The Forrelation problem, introduced by Aaronson and Ambainis (2015), serves as one of the cleanest demonstrations of an exponential separation between quantum and classical query complexity. Given oracle access to two Boolean functions \( f, g : \{0,1\}^n \to \{-1,1\} \), one must estimate their correlation \[ \Phi(f,g) = \frac{1}{2^{3n/2}} \sum_{x,y} f(x)(-1)^{x\cdot y}g(y). \] Let the Walsh–Hadamard transform be normalized as \[ \widehat f(y) := 2^{-n/2}\sum_x f(x)(-1)^{x\cdot y}. \] Then \[ \Phi(f,g) = 2^{-n}\sum_y \widehat f(y)\,g(y) \] \[ = \mathbb{E}_{y\sim\mathrm{Unif}}\big[\widehat f(y)\,g(y)\big]. \] The problem captures a fundamental contrast: a quantum computer can estimate \(\Phi(f,g)\) with one query, whereas classical randomized algorithms require exponentially many in the standard constant-gap regime (on the order of \(2^{n/2}\), up to polylog factors).
This note extends the framework by introducing a spectral criterion for hardness: a quantitative relation between Fourier flatness, resilience, and classical query complexity. It is useful to keep two “endpoints” in mind: (i) the Aaronson–Ambainis random-oracle regime, which attains the \(\widetilde\Omega(2^{n/2})\) classical scale; and (ii) the extremal bent frontier (maximal \(|\Phi|=1\)), where the best-known classical lower bound is \(\widetilde\Omega(2^{n/4})\) (Girish–Servedio, 2025). We then propose a smooth spectrum viewpoint that organizes intermediate structure between these extremes.
In their foundational paper, Aaronson and Ambainis formulated the Forrelation problem to exhibit an optimal quantum-classical separation. The task is to distinguish whether \(\Phi(f,g) \geq \tau\) or \(|\Phi(f,g)| \leq \tau/2\), given a promise that one holds. They showed that a quantum computer can solve this with \(O(1)\) queries, while any classical algorithm requires \(\widetilde\Omega(2^{n/2})\) queries (equivalently \(\widetilde\Omega(\sqrt{N})\) where \(N=2^n\)).
Their analysis treats \(f\) and \(g\) as unstructured oracles, essentially random Boolean functions (with the YES case drawn from a “forrelated” distribution). Under the NO distribution, Fourier spectra behave like noise and \(\Phi(f,g)\) concentrates near \(0\); under the YES distribution, \(\Phi(f,g)\) is a constant bounded away from \(0\), yet still hard to detect by classical sampling. Quantum interference exploits the global structure of the Hadamard transform in a single step. This randomness-based regime represents one extreme of the spectrum, a coarse-grained demonstration that exponential advantage exists, without specifying the spectral structure that makes it hardest.
In contrast, Girish and Servedio identify a structured extremal case. They focus on the extremal promise \(\Phi(f,g) \in \{+1,-1\}\), and show that such maximally forrelated (and anti-forrelated) pairs arise from bent functions—Boolean functions with perfectly flat Fourier spectra. They prove that distinguishing \(\Phi(f,g)=1\) from \(\Phi(f,g)=-1\) requires \(\widetilde\Omega(2^{n/4})\) classical queries, while quantum algorithms still need only \(O(1)\).
Thus, Aaronson’s random-oracle regime and the bent-function extremal regime represent two endpoints: the former achieves the largest known classical hardness scale for a one-query quantum algorithm (\(\widetilde\Omega(2^{n/2})\)), while the latter isolates an explicit algebraic frontier where \(|\Phi|\) is maximized but the best-known classical lower bound is \(\widetilde\Omega(2^{n/4})\). (Whether the extremal bound can be improved to \(\widetilde\Omega(2^{n/2})\) remains an open question.)
Two equivalent characterizations of bent functions are central in the literature:
These two definitions are mathematically equivalent; the quadratic form guarantees constant-magnitude Walsh coefficients, while any flat-spectrum Boolean function corresponds, up to affine transformation, to such a quadratic polynomial.
We now propose a spectral criterion for hardness that aims to organize intermediate cases between random and bent extremes. Let \(f,g:\{0,1\}^n\to\{-1,1\}\) be Boolean functions with Fourier transforms \(\widehat f, \widehat g\).
The key point is that a single fixed baseline exponent cannot simultaneously match both endpoints: the Aaronson–Ambainis constant-gap regime exhibits \(\widetilde\Omega(2^{n/2})\) classical hardness at a constant forrelation level, whereas the extremal \(\tau=1\) promise currently has a \(\widetilde\Omega(2^{n/4})\) bound. The role of \(\eta\) (flatness) and \(\kappa\) (low-degree suppression) is to quantify how close one is to the “spectrally ideal” case; the role of \(a(\tau)\) is to reflect which endpoint regime the promise level is actually probing.
To make the “spectrum” picture concrete, we can define a smooth baseline exponent \(a(\tau)\) that interpolates between the two anchor points: \[ \big(\tau_0, a(\tau_0)\big)= \] \[ \Big(\frac{2}{\pi},\frac{1}{2}\Big) \quad \text{(AA-style forrelated scale)}, \] \[ \big(\tau_1, a(\tau_1)\big)= \] \[ \big(1,\frac{1}{4}\big) \quad \text{(extremal bent frontier)}. \] With only two knots, the natural cubic spline degenerates to a straight line. A simple “one-segment spline” with curvature is the cubic Hermite choice with zero slope at both endpoints.
Plugging \(a_{\mathrm{spline}}(\tau)\) into Conjecture 1 yields a compact “spectrum hypothesis”: for promise levels near \(\tau\approx 2/\pi\), one expects the AA-scale exponent \(\approx 1/2\); as \(\tau\to 1\), the baseline exponent smoothly relaxes toward \(1/4\), consistent with the known extremal lower bound. This spline is not a proof technique; it is a concise way to encode how the underlying hardness scale might vary with the promised correlation level while remaining pinned to the two established endpoints.
Beyond bent functions, recent works have explored related function classes in Forrelation and similar problems:
This broader context suggests that Forrelation hardness is governed by spectral flatness and low-degree suppression, the same properties that drive pseudorandomness and cryptographic resistance.
The Forrelation problem provides a unifying stage for examining how spectral properties of Boolean functions translate into computational hardness. Aaronson and Ambainis revealed the existence of exponential quantum advantage in a random-oracle regime at the \(\widetilde\Omega(2^{n/2})\) scale; Girish and Servedio located an explicit extremal bent frontier where \(|\Phi|\) is maximized and proved a \(\widetilde\Omega(2^{n/4})\) lower bound. The spectral viewpoint in this note reframes these results as endpoints of a continuous story: flat Fourier spectra and low-degree suppression are “hardness-enabling resources,” while the promised correlation scale \(\tau\) controls which baseline exponent is plausible. Conjecture 1 packages this viewpoint into a single heuristic inequality, and Proposition 2 supplies a concrete spline baseline \(a_{\mathrm{spline}}(\tau)\) that interpolates between the two established endpoint exponents \(1/2\) and \(1/4\). A natural next step is to test (numerically, or within restricted function families) whether the \((\eta,\kappa)\) parameters correlate with classical query hardness in the way suggested here, and to understand how much of the remaining gap is due to promise design versus proof technique.