Forrelation: A problem that optimally separates quantum from classical computing

We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs Ω(N/log N) queries (improving an Ω(N¹/⁴) lower bound of Aaronson). Conversely, we show that this 1 versus Ω( N) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N¹−1/2^t)-query randomized algorithm. Thus, resolving an open question of Buhrman et al. [SIAM J. Comput., 37 (2008), pp. 1387–1400] from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal t versus Ω(N¹−1/2^t) separation for all t. As a bonus, we show that this generalization is BQP-complete. This yields what is arguably the simplest BQP-complete problem yet known and gives a second sense in which Forrelation “captures the maximum power of quantum computation.”