Visit Classiq’s Library for an implementation of Shor’s algorithm
‍

Anyone interested in learning quantum computing cannot avoid hearing about Shor’s Factoring Algorithm. It is one of the few textbook quantum algorithms, which means that it remains one of the rare examples of quantum computational advantage. In other words, the algorithm can compute something quantumly that is harder and slower to compute classically. In fact, this particular algorithm can compute something that is for all practical intents and purposes, as far as we know, impossible to do classically at any useful scale.

Among the aforementioned textbook algorithms, Shor’s Factoring Algorithm stands out from the crowd. There are two excellent reasons for this. First, it can factor numbers exponentially faster than any known classical algorithm. While all of the textbook quantum algorithms offer computational advantages, Shor’s Algorithm is one of the elite few with an exponential speedup, as well as one of the elite few with a practical application. Most importantly, its potential to factor numbers in reasonable timeframes directly threatens the world’s most popular cryptosystems.  

The significance of that cannot be overstated. RSA encryption, protecting financial transactions worldwide, works by multiplying two huge prime numbers. Prime numbers cannot be divided into integers other than themselves and the number one. Their products are so large, that there is no known way to efficiently factor them classically. Think of factoring as reverse multiplication, determining the prime numbers used, thus allowing unauthorized decryption of internet communications.

This blog article occasionally refers to the algorithm under discussion as Shor’s Factoring Algorithm, and not simply Shor’s Algorithm, because there is also a quantum error correction code bearing the name Shor, with the same namesake, which was discovered as a consequence of publishing the factoring algorithm. For this article, to avoid ambiguity up front, know that Shor’s Algorithm and Shor’s Factoring Algorithm refer to the same algorithm.

What is Shor's algorithm in quantum computing?             

Shor’s Factoring Algorithm put quantum computing on the proverbial map. By threatening animated version, national governments, whole industries, and the public at large were forced to take notice of this relatively new technology. Decades later, this algorithm remains the standard bearer of quantum algorithms.  Significant effort has been underway for a long time to protect global financial systems, national security, and all other uses of cryptography, for that matter. There is a clear and present geopolitical danger of anyone, especially a state actor, developing sufficient quantum computing power to employ Shor’s algorithm before quantum-safe cryptosystems can be universally deployed.

Almost as important, Shor’s algorithm has led to the present-day investment of billions of dollars into quantum technologies, including quantum computing. Three decades since the algorithm was discovered, the search continues for other practical applications for which exponential speedups can be realized. If at least one algorithm can achieve this, the thinking goes, there must be others. After all these years, the most likely candidates borrow from Shor’s algorithm.

To hear the full-length story of the discovery of Shor’s Factoring Algorithm, as told by Professor Peter Shor himself, watch here on Qiskit’s YouTube, or to hear a shorter, animated version of this story, watch here.

How does Shor's algorithm work?

Factoring numbers with Shor’s algorithm begins with selecting a random integer smaller than the number to be factored. The classically-calculated greatest common divisor (GCD) of these two numbers, the random number and the target number, is then used to determine whether the target number has already been factored accidentally. For smaller numbers, that’s a possibility. For larger numbers, a supercomputer could be needed. And for numbers that are believed to be cryptographically secure, a quantum computer will be needed.

The role of the quantum computer is to determine the period of the number to be factored. The calculation results determine whether a new random integer needs to be tested, or whether the sought-after factors have been discovered. Once the target integer has been factored, the role of Shor’s Algorithm is concluded

At a high level, this whole process might seem quite simple. And, at a high level, it is. However, explaining each step in detail can be broken down into a series of lectures. Implementing the algorithm can be done after completing a short tutorial, but fully understanding the algorithm can consume many hours of study. 

For a mathematical explanation of Shor’s Factoring Algorithm, check out here. Otherwise, that’s Shor’s Algorithm explained in a nutshell.

How is Shor's algorithm implemented?                                   

Shor’s Factoring Algorithm is not simple to implement. First of all, the algorithm has three major components: one using classical computation, one using quantum computation, and another using classical computation. Overall, the algorithm has six significant steps, as summarized above.

Adding to this complexity, however, the quantum component of Shor’s Factoring Algorithm has four subcomponents, each of which could have an entire article of explanation in their own rights. And while two of those quantum subcomponents are relatively straightforward to explain, the other two are incredibly important quantum subroutines. In fact, they are arguably the two most significant quantum subroutines.

One of the critical quantum subcomponents is called quantum phase estimation (QPE). The important takeaway here is that it performs the modular arithmetic needed to find the period of the number to be factored. In other words, this is where the factoring power of Shor’s algorithm comes from. 

The other key quantum subcomponent is called the inverse Quantum Fourier Transform (iQFT). Simply put, the iQFT takes the quantum result of the modular arithmetic that immediately precedes it and transforms it into classical information that can be retrieved from the quantum circuit through a process known as measurement.

All together, Shor’s Factoring Algorithm begins with a few classical steps. The quantum component then finds the period of the number to be factored. This is done through quantum modular arithmetic, the result of which is converted from quantum information to classical information so that it is useable. And, finally, there are another couple of classical steps. If the answer is not found, and the number consequently cannot be factored, the algorithm in its entirety is adjusted and repeated.

‍

How many qubits are needed for Shor's algorithm? 

A distinction first needs to be made between physical and logical qubits to answer this question. All present-day qubits are physical qubits. They are extremely “noisy,” which means they are error-prone. The results of quantum computation of any significance make it impossible to distinguish correct answers from incorrect ones. Every possible solution has the same probability of being right, which is the same as having no answers at all.

That’s where logical qubits come into play. Physical qubits need to be connected and structured in ways that they will collectively provide enough error correction to each other to be considered “fault-tolerant” collectively. At that point, these qubit collectives become known as “logical qubits,” or sometimes “perfect qubits.”

These logical qubits are abstractions. A quantum circuit today with five qubits represents five highly-noisy, error-prone physical qubits. Quantum algorithm designers of the near future will want those five qubits to represent logical, fault-tolerant, error-free qubits. The estimates vary as to how many physical qubits will be needed to represent one logical qubit, but a reasonable number to work with is 1,000. Most estimate that a quantum computer will need around 1,000 physical qubits to represent just one logical qubit.

To appreciate how challenging that is, the largest quantum computer today has only 127 physical qubits. And while IBM has a goal of unveiling a 1,000-qubit device by next year, that is still only 1,000 physical qubits. Much work remains to engineer the first logical qubit.

Estimates of the number of qubits Shor’s Factoring Algorithm needs vary considerably. First, care must be taken, as noted, to discern estimates for logical qubits and estimates for physical qubits. Depending on the researchers' objectives, the number of required qubits can be reduced, sacrificing time of execution and circuit depth. On the other hand, the number of qubits can be significantly expanded, reducing runtime and shedding circuit depth. The differences are that lower qubit counts will become available sooner, while the quickest runtimes will be the most advantageous. A selection of estimates follows.

In an August 1, 1996 paper titled, “Efficient networks for quantum factoring” by David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni, and John Preskill, the authors estimated that factoring a K-bit number would take K³ time and require 5K+1 logical qubits. Factoring a 2,048-bit number, referring to breaking RSA encryption, would therefore take 8.6 billion time and require 10,241 logical qubits, or roughly 10 million physical qubits. Unfortunately, it’s not clear how long 8.6 billion time would be, as different qubit technologies operate at different speeds.

Then in a February 21, 2003, paper titled, “Circuit for Shor’s algorithm using 2n+3 qubits” by St´ephane Beauregard, the authors estimated that factoring a K-bit number would require 2n+3 logical qubits. Factoring a 2,048-bit number would therefore require only 4,099 logical qubits, or roughly 4 million physical qubits. Again, zero logical qubits exist today. However, this paper nonetheless brought Shor’s Factoring Algorithm closer to implementation. 

Then in a May 2014 book titled, “Fast quantum modular exponentiation architecture for Shor's factoring algorithm” (pp0649-0682) by Archimedes Pavlidis and Dimitris Gizopoulos, the authors proposed a 9n+2 implementation, adding a significant number of qubits to reduce circuit depth. Breaking 2,048-bit RSA encryption would require 18,434 logical qubits or roughly 18 million physical qubits. One reason to minimize circuit depth is that qubits lose “coherence” over time. The longer it takes to execute a circuit, as determined, in part, by circuit depth, the more noise can seep into the system and the more errors can pop up in the results. Even today, one way to reduce errors is to minimize circuit depth.

Most recently, in an April 13, 2021 paper titled, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits” by Craig Gidney and Martin Eker, the authors estimate that breaking RSA encryption, specifically, would require roughly 20,000 logical qubits, or approximately 20 million physical qubits. The authors take one step further and quantify the runtime for their configuration as only eight hours. Compare that to the estimate for the world’s most powerful supercomputers to break RSA encryption, which is well beyond any human lifetime, and the power of Shor’s Factoring Algorithm becomes clear. For other estimates of how many qubits for Shor’s algorithm, check out the references for this paper.

Again, Shor’s algorithm runtime is inversely proportional to the number of logical qubits available. It also depends on the qubit technology in use, since different quantum computers execute operations at vastly different speeds. The fewer qubits needed, the longer the algorithm will take to run, but the sooner modern cryptosystems transition from obsolescent to obsolete. Conversely, the more qubits available, the faster modern cryptosystems will be cracked. But fortunately, those days are even further away.

How do you run Shor's algorithm?

You can’t. 

The largest number factored to date with Shor’s Algorithm is 21. And the smallest possible number to factor with the algorithm is 15. That is a very narrow range for two specific reasons. First, Shor’s Factoring Algorithm requires large numbers of qubits, as previously mentioned, and large numbers of qubits do not exist. Second, present-day qubits are “noisy,” which means they are remarkably error-prone. The circuit depth required by the algorithm produces results with so many errors that it is impossible to distinguish correct solutions from incorrect ones.

In other words, RSA and other potentially-vulnerable cryptosystems are safe. For now. NIST continues to work toward selecting a post-quantum standard, otherwise known as a “quantum-safe” standard, to hopefully be implemented widespread long before enough fault-tolerant qubits are available to realize this pending threat.

Despite the long timeframe involved and the work being done to mitigate the risk, Shor’s Factoring Algorithm remains as good a way to raise awareness about quantum computing today as it was when it was first discovered. Executives across all industries need to concern themselves with potential risks to sensitive communications and data, and this one is genuine. In the process, they’ll hopefully be introduced to the dozens of other potential use cases of quantum computing that might substantially benefit their respective enterprises someday.

Visit Classiq’s Library for an implementation of Shor’s algorithm‍