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(x(1),..., x(N)) 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... log N) quantum bits but requires Omega(N) bits of communication for classical protocols.