Since quantum algorithms are inherently random, these three problems qualify:

1. Solve the Deutsch-Jozsa problem in constant time.
2. Search an unstructured database in O(sqrt(n)) time.
3. Factorize integers in polynomial time.

Moreover, randomized algorithms are occasionally useful in a classical computer, since they give good expected performance even for some classes of degenerate inputs.