A Super-Grover Separation Between Randomized and Quantum Query Complexities
Shalev Ben-David · arXiv (Cornell University) · 2015
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. Assuming a conjecture of Aaronson and Ambainis about optimal quantum speedups for partial functions, we improve this to $R(f)=\\tilde{\\Omega}(Q(f)^3)$. Our construction is motivated by the G\\"o\\"os-Pitassi-Watson function but does not use it.