Forrelation is Extremally Hard

Uma Girish, Rocco Servedio

The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to $n$-bit…