Shor's algorithm is a polynomial-time quantum computer algorithm for integer factorization.
Informally, it solves the following problem: Given an integer  N , find its prime factors.
It was discovered in 1994 by the American mathematician Peter Shor.
On a quantum computer, to factor an integer  N , Shor's algorithm runs in polynomial time (the time taken is polynomial in  \log N , the size of the integer given as input).See also pseudo-polynomial time.
Specifically, it takes quantum gates of order  O \!
\left((\log N)^{2} (\log \log N) (\log \log \log N) \right)  using fast multiplication, thus demonstrating that the integer-factorization problem can be efficiently solved on a quantum computer and is consequently in the complexity class BQP.
This is almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time:  O \!
\left(e^{1.9 (\log N)^{1/3} (\log \log N)^{2/3}} \right) .
The efficiency of Shor's algorithm is due to the efficiency of the quantum Fourier transform, and modular exponentiation by repeated squarings.
If a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor's algorithm could be used to break public-key cryptography schemes, such as
The RSA scheme
The Finite Field Diffie-Hellman key exchange
The Elliptic Curve Diffie-Hellman key exchange
RSA is based on the assumption that factoring large integers is computationally intractable.
As far as is known, this assumption is valid for classical (non-quantum) computers; no classical algorithm is known that can factor integers in polynomial time.
However, Shor's algorithm shows that factoring integers is efficient on an ideal quantum computer, so it may be feasible to defeat RSA by constructing a large quantum computer.
It was also a powerful motivator for the design and construction of quantum computers, and for the study of new quantum-computer algorithms.
It has also facilitated research on new cryptosystems that are secure from quantum computers, collectively called post-quantum cryptography.
In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored  15  into  3 \times 5 , using an NMR implementation of a quantum computer with  7  qubits.
After IBM's implementation, two independent groups implemented Shor's algorithm using photonic qubits, emphasizing that multi-qubit entanglement was observed when running the Shor's algorithm circuits.
In 2012, the factorization of  15  was performed with solid-state qubits.
Also, in 2012, the factorization of  21  was achieved, setting the record for the largest integer factored with Shor's algorithm.
In 2019 an attempt was made to factor the number 35 using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors.
Though larger numbers have been factored by quantum computers using other algorithms, these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms.
Procedure
The problem that we are trying to solve is, given a composite number  N , to find a non-trivial divisor of  N  (a divisor strictly between  1  and  N ).
Before attempting to find such a divisor, one can use relatively quick primality-testing algorithms to verify that  N  is indeed composite.
We need  N  to be odd (otherwise  2  is a divisor) and not to be any power of a prime (otherwise that prime is a divisor), so we need to check that there are no integer roots  \sqrt[k]{N}  for  2 \leq k \leq {\log_{3}}(N) .
Hence we may assume that  N  is the product of two coprime integers greater than  2 .
It follows from the Chinese remainder theorem that there are at least four distinct square roots of  1  modulo  N  (since there are two roots for each modular equation).
The aim of the algorithm is to find a square root  b  of  1  modulo  N  that is different from  1  and  - 1 , because then
b^2 - 1 = (b+1)(b-1) = mN
for a non-zero integer  m  that gives us the non-trivial divisors  \gcd(N, b+1)  and  \gcd(N, b-1)  of  N .
This idea is similar to other factoring algorithms, such as the quadratic sieve.
In turn, finding such a  b  is reduced to finding an element  a  of even period with a certain additional property (as explained below, it is required that the condition of Step 6 of the classical part does not hold).
The quantum algorithm is used for finding the period of randomly chosen elements  a , as this is a difficult problem on a classical computer.
Shor's algorithm consists of two parts:
A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding.
A quantum algorithm to solve the order-finding problem.
Classical part
For example: Given  N = 15 ,  a = 7 , and  r = 4, we have  \gcd(7^{2} \pm 1,15) = \gcd(49 \pm 1,15) , where  \gcd(48,15) = 3  and  \gcd(50, 15) = 5 .
For  N  that is a product of two distinct primes,  p  and  q , the value of  \varphi(N)  is just  N - p - q + 1 , which for  N = 15  is  8 , and  r  divides  8 .
Quantum part: period-finding subroutine
450px|thumb|center|Quantum subroutine in Shor's algorithm The quantum circuits used for this algorithm are custom designed for each choice of  N  and each choice of the random  a  used in  f(x) = a^{x} \bmod N .
Given  N , find  Q = 2^{q}  such that  N^{2} \leq Q < 2 N^{2} , which implies that  \dfrac{Q}{r} > N .
The input and output qubit registers need to hold superpositions of values from  0  to  Q - 1 , and so have  q  qubits each.
Using what might appear to be twice as many qubits as necessary guarantees that there are at least  N  different values of  x  that produce the same  f(x) , even as the period  r  approaches  \dfrac{N}{2} .
Proceed as follows: Explanation of the algorithm
The algorithm is composed of two parts.
The first part of the algorithm turns the factoring problem into the problem of finding the period of a function and may be implemented classically.
The second part finds the period using the quantum Fourier transform and is responsible for the quantum speedup.
Obtaining factors from period
The integers less than  N  and coprime with  N  form the multiplicative group of integers modulo  N , which is a finite abelian group  G .
The size of this group is given by  \varphi(N) .
By the end of step 3, we have an integer  a  in this group.
As the group is finite,  a  must have a finite order  r , which is the smallest positive integer such that
a^{r} \equiv 1 \bmod N.
Therefore,  N  divides  a^{r} - 1  (also written  N \mid a^{r} - 1 ).
Suppose that we are able to obtain  r  and that it is even.
(If  r  is odd, then by step 5, we have to restart the algorithm with a different random number a) Now  b \equiv a^{r / 2} \bmod N  is a square root of  1  modulo  N  that is different from  1 .
This is because  r  is the order of  a  modulo  N , so  a^{r / 2} \not\equiv 1 \bmod N , or else the order of  a  in this group would be  \dfrac{r}{2} .
If  a^{r / 2} \equiv - 1 \bmod N , then by step 6, we have to restart the algorithm with a different random number  a .
Eventually, we must hit an  a  of order  r  in  G  such that  b \equiv a^{r / 2} \not\equiv \pm 1 \bmod N .
This is because such a  b  is a square root of  1  modulo  N  other than  1  and  - 1 , whose existence is guaranteed by the Chinese remainder theorem, as  N  is not a prime power.
We claim that  d = \gcd(b - 1,N)  is a proper factor of  N , i.e.,  d \neq 1,N .
In fact, if  d = N , then  N  divides  b - 1 , so that  b \equiv 1 \bmod N , which goes against the construction of  b .
If, on the other hand,  d = \gcd(b - 1,N) = 1 , then by Bézout's identity, there are integers  u,v  such that
(b - 1) u + N v = 1.
Multiplying both sides by  b + 1 , we obtain
(b^{2} - 1) u + N (b + 1) v = b + 1.
As  N  divides  b^{2} - 1 \equiv a^{r} - 1 \bmod N , we find that  N  divides  b + 1 , so that  b \equiv - 1 \bmod N , again contradicting the construction of  b .
Therefore,  d  is the required proper factor of  N .
Finding the period
Shor's period-finding algorithm relies heavily on the ability of a quantum computer to be in many states simultaneously.
Physicists call this behavior a "superposition" of states.
To compute the period of a function  f , we evaluate the function at all points simultaneously.
Quantum physics does not allow us to access all this information directly, however.
A measurement will yield only one of all possible values, destroying all others.
If not for the no-cloning theorem, we could first measure  f(x)  without measuring  x , and then make a few copies of the resulting state (which is a superposition of states all having the same  f(x) ).
Measuring  x  on these states would provide different  x  values which give the same  f(x) , leading to the period.
Because we cannot make exact copies of a quantum state, this method does not work.
Therefore, we have to carefully transform the superposition to another state that will return the correct answer with high probability.
This is achieved by the quantum Fourier transform.
Shor thus had to solve three "implementation" problems.
All of them had to be implemented "fast", which means that they can be implemented with a number of quantum gates that is polynomial in  \log N .
Create a superposition of states.
This can be done by applying Hadamard gates to all qubits in the input register.
Another approach would be to use the quantum Fourier transform (see below).
Implement the function  f  as a quantum transform.
To achieve this, Shor used repeated squaring for his modular exponentiation transformation.
It is important to note that this step is more difficult to implement than the quantum Fourier transform, in that it requires ancillary qubits and substantially more gates to accomplish.
Perform a quantum Fourier transform.
By using controlled rotation gates and Hadamard gates, Shor designed a circuit for the quantum Fourier transform (with  Q = 2^{q} ) that uses just  \dfrac{q (q - 1)}{2} = O \!
\left((\log Q)^{2} \right)  gates.
After all these transformations a measurement will yield an approximation to the period  r .
For simplicity assume that there is a  y  such that  \dfrac{y r}{Q}  is an integer.
Then the probability to measure  y  is  1 .
To see this, we notice that then
e^{- \frac{2 \pi i b y r}{Q}} = 1
for all integers  b .
Therefore, the sum whose square gives us the probability to measure  y  will be  \dfrac{Q}{r} , as  b  takes roughly  \dfrac{Q}{r}  values and thus the probability is  \dfrac{1}{r^{2}} .
There are  r  possible values of  y  such that  \dfrac{y r}{Q}  is an integer, and also  r  possibilities for  f(x_{0}) , so the probabilities sum to  1 .
Note: Another way to explain Shor's algorithm is by noting that it is just the quantum phase estimation algorithm in disguise.
The bottleneck
The runtime bottleneck of Shor's algorithm is quantum modular exponentiation, which is by far slower than the quantum Fourier transform and classical pre-/post-processing.
There are several approaches to constructing and optimizing circuits for modular exponentiation.
The simplest and (currently) most practical approach is to mimic conventional arithmetic circuits with reversible gates, starting with ripple-carry adders.
Knowing the base and the modulus of exponentiation facilitates further optimizations.
Reversible circuits typically use on the order of n^3 gates for n qubits.
Alternative techniques asymptotically improve gate counts by using quantum Fourier transforms, but are not competitive with fewer than 600 qubits owing to high constants.
Discrete logarithms
Given a group G with order  p  and generator  g \in G , suppose we know that  x = g^{r} \in G , for some  r \in \mathbb{Z}_p , and we wish to compute  r , which is the discrete logarithm:  r = {\log_{g}}(x) .
Consider the abelian group  \mathbb{Z}_{p} \times \mathbb{Z}_{p} , where each factor corresponds to modular addition of values.
Now, consider the function
f \colon \mathbb{Z}_{p} \times \mathbb{Z}_{p} \to G \;;\; f(a,b) = g^{a} x^{- b} .
This gives us an abelian hidden subgroup problem, as  f  corresponds to a group homomorphism.
The kernel corresponds to the multiples of  (r,1) .
So, if we can find the kernel, we can find  r .
See also
GEECM, a factorization algorithm said to be "often much faster than Shor's"
Grover's algorithm
References
Further reading
.
Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Oxford University Press, 2007,
"Explanation for the man in the street" by Scott Aaronson, "approved" by Peter Shor.
(Shor wrote "Great article, Scott!
That’s the best job of explaining quantum computing to the man on the street that I’ve seen.").
An alternate metaphor for the QFT was presented in one of the comments.
Scott Aaronson suggests the following 12 references as further reading (out of "the 10105000 quantum algorithm tutorials that are already on the web."):
.
Revised version of the original paper by Peter Shor ("28 pages, LaTeX.
This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994.
Minor revisions made January, 1996").
Quantum Computing and Shor's Algorithm, Matthew Hayward's Quantum Algorithms Page, 2005-02-17, imsa.edu, LaTeX2HTML version of the original LaTeX document, also available as PDF or postscript document.
Quantum Computation and Shor's Factoring Algorithm, Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
Shor's Factoring Algorithm, Notes from Lecture 9 of Berkeley CS 294–2, dated 4 Oct 2004, 7 page postscript document.
Chapter 6 Quantum Computation, 91 page postscript document, Caltech, Preskill, PH229.
Quantum computation: a tutorial by Samuel L. Braunstein.
The Quantum States of Shor's Algorithm, by Neal Young, Last modified: Tue May 21 11:47:38 1996.
III.
Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm, Lecture notes on Quantum computation, Cornell University, Physics 481–681, CS 483; Spring, 2006 by N. David Mermin.
Last revised 2006-03-28, 30 page PDF document.
This paper is a written version of a one-hour lecture given on Peter Shor's quantum factoring algorithm.
22 pages.
Chapter 20 Quantum Computation, from Computational Complexity: A Modern Approach, Draft of a book: Dated January 2007, Sanjeev Arora and Boaz Barak, Princeton University.
Published as Chapter 10 Quantum Computation of Sanjeev Arora, Boaz Barak, "Computational Complexity: A Modern Approach", Cambridge University Press, 2009,
A Step Toward Quantum Computing: Entangling 10 Billion Particles, from "Discover Magazine", Dated January 19, 2011.
Josef Gruska - Quantum Computing Challenges also in Mathematics unlimited: 2001 and beyond, Editors Björn Engquist, Wilfried Schmid, Springer, 2001,
External links
Version 1.0.0 of libquantum: contains a C language implementation of Shor's algorithm with their simulated quantum computer library, but the width variable in shor.c should be set to 1 to improve the runtime complexity.
PBS Infinite Series created two videos explaining the math behind Shor's algorithm, "How to Break Cryptography" and "Hacking at Quantum Speed with Shor's Algorithm".
