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.
Leave a reply