Superlinear advantage for exact quantum algorithms

A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). A key question is, how big is the advantage of exact quantum algorithms over their classical counterparts: deterministic algorithms? We present the first example of a total Boolean function f(x1, . . . ,xN) for which exact quantum algorithms have superlinear advantage over deterministic algorithms. Any deterministic algorithm that computes our function must use N queries but an exact quantum algorithm can compute it with O(N^0.8675...) queries. A modification of our function gives a similar result for communication complexity: there is a function f which can be computed by an exact quantum protocol that communicates O(N^0.8675... logN) quantum bits but requires Ù(N) bits of communication for classical protocols.