As Shor looked for applications for his quantum period-finding algorithm, he rediscovered a previously known but obscure mathematical theorem: For every number, there exists a periodic function whose periods are related to the numberâs prime factors. So if thereâs a number you want to factor, you can compute the corresponding function and then solve the problem using period finding â âexactly what quantum computers are so good at,â Regev said.
On a classical computer, this would be an agonizingly slow way to factor a large number â slower even than trying every possible factor. But Shorâs method speeds up the process exponentially, making period finding an ideal way to construct a fast quantum factoring algorithm.
Shorâs algorithm was one of a few key early results that transformed quantum computing from an obscure subfield of theoretical computer science to the juggernaut it is today. But putting the algorithm into practice is a daunting task, because quantum computers are notoriously susceptible to errors: In addition to the qubits required to perform their computations, they need many others doing extra work to keep them from failing. A recent paper by EkerĂ„ and the Google researcher Craig Gidney estimates that using Shorâs algorithm to factor a security-standard 2,048-bit number (about 600 digits long) would require a quantum computer with 20 million qubits. Todayâs state-of-the-art machines have at most a few hundred.