A Super-Grover Separation Between Randomized and Quantum Query Complexities

Shalev Ben-David

We construct a total Boolean function $f$ satisfying $R(f)=\tilde{\Omega }(Q(f{)}^{5/2})$, refuting the long-standing conjecture that $R(f)=O(Q(f{)}^2)$ for all total Boolean functions. Assumi…