Shor's algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization, formulated in 1994. Informally, it solves the following problem: Given an integer , find its prime factors.

On a quantum computer, to factor an integer , Shor's algorithm runs in polynomial time (the time taken is polynomial in , which is the size of the input).[1] Specifically, it takes quantum gates of order using fast multiplication,[2] 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.[3] 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 widely-used RSA scheme. 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 into , using an NMR implementation of a quantum computer with qubits.[4] 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.[5][6] In 2012, the factorization of was performed with solid-state qubits.[7] Also, in 2012, the factorization of was achieved, setting the record for the largest integer factored with Shor's algorithm.[8] In April 2012, the factorization of was achieved, although this used adiabatic quantum computation rather than Shor's algorithm.[9] In November 2014, it was discovered that this 2012 adiabatic quantum computation had also factored larger numbers, the largest being ,[10][11] (this number is equal to ).


The problem that we are trying to solve is, given an odd composite number , find an integer , strictly between and , that divides . We are interested in odd values of because any even value of trivially has as a prime factor. We can use a primality-testing algorithm to ensure that is indeed composite.

Moreover, for the algorithm to work, we need not to be any power of a prime. This can be tested by checking that is not an integer for any .

Since is not a power of a prime, it is the product of two coprime integers greater than . As a consequence of the Chinese remainder theorem, the number has at least four distinct square roots modulo , two of which are and . The aim of the algorithm is to find a square root that is different from and ; such a will lead to a factorization of , as in other factoring algorithms, like the quadratic sieve.

In turn, finding such a is reduced to finding an element 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 , as this is a hard problem on a classical computer.

Shor's algorithm consists of two parts:

  1. A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding.
  2. A quantum algorithm to solve the order-finding problem.

Classical part[edit]

  1. Pick a random number .
  2. Compute , the greatest common divisor of and . This may be done using the Euclidean algorithm.
  3. If , then this number is a nontrivial factor of , so we are done.
  4. Otherwise, use the quantum period-finding subroutine (below) to find , which denotes the period of the following function:
    This is the order of in the group , which is the smallest positive integer for which , or . By Euler's Theorem, divides , where denotes Euler's totient function.
  5. If is odd, then go back to step 1.
  6. If , then go back to step 1.
  7. Otherwise, and are both nontrivial factors of , so we are done.

For example: Given , , and , we have , where and . For that is a product of two distinct primes, and , the value of is just , which for is . Note that divides .

Quantum part: period-finding subroutine[edit]

Quantum subroutine in Shor's algorithm.

The quantum circuits used for this algorithm are custom designed for each choice of and each choice of the random used in . Given , find such that , which implies that . The input and output qubit registers need to hold superpositions of values from to , and so have qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least different values of that produce the same , even as the period approaches .

Proceed as follows:

  1. Initialize the registers to
    This initial state is a superposition of states, and is easily obtained by generating independent qubits, each a superposition of and states. We can accomplish this by initializing the qubits to the zero-position, and then applying the hadamard gate in parallel to each of the qubits, where .
  2. Construct as a quantum function and apply it to the above state, to obtain
    This is still a superposition of states. However, the qubits, i.e, the input qubits and () output qubits, are now entangled or not separable, as the state cannot be written as a tensor product of states of individual qubits.
  3. Apply the quantum Fourier transform to the input register. This transform (operating on a superposition of states) uses a -th root of unity such as to distribute the amplitude of any given state equally among all of the states, and to do so in a different way for each different . We thus obtain
    This leads to the final state
    Now, we reorder this sum as
    This is a superposition of many more than states, but many fewer than states, as there are fewer than distinct values of . Let
    • be a -th root of unity,
    • be the period of ,
    • be the smallest of the for which (we actually have ), and
    • indexes these , running from to , so that .
    Then is a unit vector in the complex plane ( is a root of unity, and and are integers), and the coefficient of in the final state is
    Each term in this sum represents a different path to the same result, and quantum interference occurs — constructive when the unit vectors point in nearly the same direction in the complex plane, which requires that point along the positive real axis.
  4. Perform a measurement. We obtain some outcome in the input register and some outcome in the output register. As is periodic, the probability of measuring some state is given by
    Analysis now shows that this probability is higher the closer the unit vector is to the positive real axis, or the closer is to an integer. Unless is a power of , it will not be a factor of .
  5. Since is close to some integer , the known value is close to the unknown value . Performing [classical] continued fraction expansion on allows us to find approximations of it that satisfy two conditions:
    1. .
    2. .
    Given these conditions (and assuming is irreducible), is very likely to be the appropriate period , or at least a factor of it.
  6. Check (classically) if . If so, then we are done.
  7. Otherwise, (classically) obtain more candidates for by using multiples of , or by using other with near . If any candidate works, then we are done.
  8. Otherwise, try again starting from step 1 of this subroutine.

Explanation of the algorithm[edit]

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[edit]

The integers less than and coprime with form the multiplicative group of integers modulo , which is a finite abelian group . The size of this group is given by . By the end of step 3, we have an integer in this group. As the group is finite, must have a finite order , which is the smallest positive integer such that

Therefore, divides (also written ). Suppose that we are able to obtain and that it is even. (If is odd, then see step 5.) Now is a square root of modulo that is different from . This is because is the order of modulo , so , or else the order of in this group would be . If , then by step 6, we have to restart the algorithm with a different random number .

Eventually, we must hit an of order in such that . This is because such a is a square root of modulo other than and , whose existence is guaranteed by the Chinese remainder theorem, as is not a prime power.

We claim that is a proper factor of , i.e., . In fact, if , then divides , so that , which goes against the construction of . If, on the other hand, , then by Bézout's identity, there are integers such that

Multiplying both sides by , we obtain

As divides , we find that divides , so that , again contradicting the construction of .

Therefore, is the required proper factor of .

Finding the period[edit]

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 , we evaluate the function at all points simultaneously.

Quantum physics does not allow us to access all this information directly, though. A measurement will yield only one of all possible values, destroying all others. If not for the no cloning theorem, we could first measure without measuring , and then make a few copies of the resulting state (which is a superposition of states all having the same ). Measuring on these states would provide different values which give the same , 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 .

  1. 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).
  2. Implement the function 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.
  3. Perform a quantum Fourier transform. By using controlled rotation gates and Hadamard gates, Shor designed a circuit for the quantum Fourier transform (with ) that uses just gates.[12]

After all these transformations a measurement will yield an approximation to the period . For simplicity assume that there is a such that is an integer. Then the probability to measure is . To see this, we notice that then

for all integers . Therefore, the sum whose square gives us the probability to measure will be , as takes roughly values and thus the probability is . There are possible values of such that is an integer, and also possibilities for , so the probabilities sum to .

Note: Another way to explain Shor's algorithm is by noting that it is just the quantum phase estimation algorithm in disguise.

The bottleneck[edit]

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.[13][14] Reversible circuits typically use on the order of gates for qubits. Alternative techniques asymptotically improve gate counts by using quantum Fourier transforms, but are not competitive with fewer than 600 qubits due to high constants.

Discrete logarithms[edit]

Given prime with generator where , suppose we know that , for some , and we wish to compute , which is the discrete logarithm: . Consider the abelian group , where each factor corresponds to modular multiplication of nonzero values, assuming is prime. Now, consider the function

This gives us an abelian hidden subgroup problem, as corresponds to a group homomorphism. The kernel corresponds to modular multiples of . So, if we can find the kernel, we can find .

In popular culture[edit]

On the television show Stargate Universe, the lead scientist, Dr. Nicholas Rush, hoped to use Shor's algorithm to crack Destiny's master code. He taught a quantum cryptography class at the University of California, Berkeley, in which Shor's algorithm was studied.

In the animated film Summer Wars, the character Kenji Koiso reads an article titled "Shor's Factorization Algorithm" while riding on a train, foreshadowing his ability to understand and calculate complex equations.

In the TV series The Big Bang Theory it was mentioned in a Physics bowl competition in season 1 episode 13.

See also[edit]


  1. ^ See also pseudo-polynomial time.
  2. ^ Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1996). "Efficient Networks for Quantum Factoring" (PDF). Physical Review A. 54 (2): 1034–1063. arXiv:quant-ph/9602016. Bibcode:1996PhRvA..54.1034B. doi:10.1103/PhysRevA.54.1034.
  3. ^ "Number Field Sieve". Retrieved 23 October 2015.
  4. ^ Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H. & Chuang, Isaac L. (2001), "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance" (PDF), Nature, 414 (6866): 883–887, arXiv:quant-ph/0112176, Bibcode:2001Natur.414..883V, CiteSeerX, doi:10.1038/414883a, PMID 11780055
  5. ^ Lu, Chao-Yang; Browne, Daniel E.; Yang, Tao & Pan, Jian-Wei (2007), "Demonstration of a Compiled Version of Shor's Quantum Factoring Algorithm Using Photonic Qubits" (PDF), Physical Review Letters, 99 (25): 250504, arXiv:0705.1684, Bibcode:2007PhRvL..99y0504L, doi:10.1103/PhysRevLett.99.250504, PMID 18233508
  6. ^ Lanyon, B. P.; Weinhold, T. J.; Langford, N. K.; Barbieri, M.; James, D. F. V.; Gilchrist, A. & White, A. G. (2007), "Experimental Demonstration of a Compiled Version of Shor's Algorithm with Quantum Entanglement" (PDF), Physical Review Letters, 99 (25): 250505, arXiv:0705.1398, Bibcode:2007PhRvL..99y0505L, doi:10.1103/PhysRevLett.99.250505, PMID 18233509
  7. ^ Lucero, Erik; Barends, Rami; Chen, Yu; Kelly, Julian; Mariantoni, Matteo; Megrant, Anthony; O'Malley, Peter; Sank, Daniel; Vainsencher, Amit; Wenner, James; White, Ted; Yin, Yi; Cleland, Andrew N.; Martinis, John M. (2012). "Computing prime factors with a Josephson phase qubit quantum processor". Nature Physics. 8 (10): 719. arXiv:1202.5707. Bibcode:2012NatPh...8..719L. doi:10.1038/nphys2385.
  8. ^ Martín-López, Enrique; Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Alvarez, Roberto; Zhou, Xiao-Qi; O'Brien, Jeremy L. (12 October 2012). "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". Nature Photonics. 6 (11): 773–776. arXiv:1111.4147. Bibcode:2012NaPho...6..773M. doi:10.1038/nphoton.2012.259. Retrieved October 23, 2012.
  9. ^ Nanyang Xu; Jing Zhu; Dawei Lu; Xianyi Zhou; Xinhua Peng; Jiangfeng Du (30 March 2012). "Quantum Factorization of on a Dipolar-Coupling Nuclear Magnetic Resonance System". Physical Review Letters. 108 (13): 130501. Bibcode:2012PhRvL.108m0501X. doi:10.1103/PhysRevLett.108.130501. PMID 22540684.CS1 maint: Uses authors parameter (link)
  10. ^ Zyga, Lisa (28 November 2014). "New largest number factored on a quantum device is ". Science X Network. Retrieved 4 August 2015.
  11. ^ Nikesh S. Dattani; Nathaniel Bryans (November 2014). "Quantum factorization of with only qubits". arXiv:1411.6758 [quant-ph].
  12. ^ Shor 1999, p. 14
  13. ^ Markov, Igor L.; Saeedi, Mehdi (2012). "Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation". Quantum Information and Computation. 12 (5–6): 361–394. arXiv:1202.6614. Bibcode:2012arXiv1202.6614M.
  14. ^ Markov, Igor L.; Saeedi, Mehdi (2013). "Faster Quantum Number Factoring via Circuit Synthesis". Phys. Rev. A. 87 (1): 012310. arXiv:1301.3210. Bibcode:2013PhRvA..87a2310M. doi:10.1103/PhysRevA.87.012310.
  15. ^ Bernstein, Daniel J.; Heninger, Nadia; Lou, Paul; Valenta, Luke (2017). "Post-quantum RSA" (PDF). International Workshop on Post-Quantum Cryptography: 311–329. Archived (PDF) from the original on 2017-04-20.

Further reading[edit]

External links[edit]