Shor’s algorithm is easily the most iconic quantum algorithm. Multiplying two large prime numbers together is easy, but finding the two large prime factors of a larger number is really, really hard. It’s so hard, in fact, that much of our cryptography depends on factorization being essentially impossible as the numbers get larger. But in 1994, Peter Shor discovered an algorithm to factor these numbers in polynomial time. In other words, larger numbers make the problem manageably harder, not impossibly harder. If we had a sufficiently large enough fault-tolerant quantum computer, vulnerable data could be decrypted in reasonable timeframes.
It works somewhat like the 50/50 option on the show “Who Wants to be a Millionaire?” Contestants have a one-time option to remove 50% of their 4 choices, removing 2 incorrect answers and leaving 1 incorrect answer with the correct answer. Shor’s algorithm takes an equation with two unknown values, removes 50% of those two values by finding one, thus leaving only 50% of the two unknown values. And while guessing an unknown value gets increasingly harder as the target number gets larger, it’s far easier to guess one unknown value in an equation than two.