Yes. Grover's algorithm searches a disordered database in time sublinear in the number of elements, and provides a quadratic speedup over any possible classical

Yes. Grover's algorithm searches a disordered database in time sublinear in the number of elements, and provides a quadratic speedup over any possible classical algorithm. There are similar results for finding collisions etc. There is no proof, however, that quantum computers offer an exponential advantage on decision problems without some additional assumption, although this is widely believed to be the case, due in part to the exponential improvement of Shor's factoring algorithm compared to the best -known- classical algorithms.