Posted

Uma Girish, Rocco Servedio (Aug 05 2025).
Abstract: The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to nn-bit Boolean functions ff and gg, the goal is to estimate the Forrelation function forr(f,g)\mathrm{forr}(f,g), which measures the correlation between gg and the Fourier transform of ff. In this work we provide a new linear algebraic perspective on the Forrelation problem, as opposed to prior analytic approaches. We establish a connection between the Forrelation problem and bent Boolean functions and through this connection, analyze an extremal version of the Forrelation problem where the goal is to distinguish between extremal instances of Forrelation, namely (f,g)(f,g) with forr(f,g)=1\mathrm{forr}(f,g)=1 and forr(f,g)=1\mathrm{forr}(f,g)=-1. We show that this problem can be solved with one quantum query and success probability one, yet requires Ω~(2n/4)\tilde{\Omega}\left(2^{n/4}\right) classical randomized queries, even for algorithms with a one-third failure probability, highlighting the remarkable power of one exact quantum query. We also study a restricted variant of this problem where the inputs f,gf,g are computable by small classical circuits and show classical hardness under cryptographic assumptions.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!