Shor's algorithm

Suppose you want to break a big number back into the two primes that were multiplied to make it. For a number with hundreds of digits, the best classical methods we know would take longer than the age of the universe, and the whole security of RSA encryption rests on that difficulty. Shor's algorithm is a quantum recipe that does this dramatically faster. Its clever move is to not attack factoring head-on. Instead, it turns the question into a different one: pick a number and repeatedly raise it to higher powers, modulo the number you want to factor, and that sequence eventually repeats with some period. If you can find that period, a bit of ordinary arithmetic hands you the factors.

Finding the period is where the quantum part earns its keep. The algorithm prepares a register holding many inputs at once and applies the quantum Fourier transform, which is built so that the amplitudes of wrong answers cancel out while amplitudes that reveal the period reinforce each other. When you measure, you are very likely to read out a value that points to the period. It is not that the machine 'tries every power and checks them all in parallel' — nothing useful would survive measurement if it did. The speedup comes from arranging interference so the periodic structure of the problem becomes loud and everything else goes quiet. For this specific, highly structured task, that gives an exponential advantage over every classical method we currently know.