For partial boolean functions, whose domain can be a subset of {0,1}^n, exponential separations are known between the number of queries a classical deterministic algorithm needs to compute a function and the number of queries a quantum algorithm needs. For a total boolean function f, whose domain is all of {0,1}^n, the situation is quite different: the quantum Q(f) and deterministic D(f) query complexities are always polynomially related, in fact D(f) = O(Q(f)^6). It was widely believed this relation was far from tight, as for 20 years the largest separation known between these two measures has been quadratic, witnessed by Grover's search algorithm. We exhibit a total boolean function with a 4th power separation between its quantum and deterministic query complexities. Interestingly, no new quantum algorithms are needed to achieve this separation---our quantum algorithm is based on Grover search and amplitude amplification.
This is joint work with Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Miklos Santha, and Juris Smotrovs.
