Since quantum algorithms are inherently random, these three problems qualify:
Solve the Deutsch-Jozsa problem in constant time.
Search an unstructured database in O(sqrt(n)) time.
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.
Since quantum algorithms are inherently random, these three problems qualify:
Solve the Deutsch-Jozsa problem in constant time.
Search an unstructured database in O(sqrt(n)) time.
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.