Two interesting speedups
Grover’s quantum database search algorithm finds an item in an unsorted list of n items in O(¦n) steps; classical algorithms require O(n).
Shor’s quantum algorithm finds the prime factors of an n-digit number in time O(n3); the best known classical factoring algorithms require at least time O(2n 1/3 log(n)2/3).