Factoring problem

Shor's algorithm

Shor's algorithm, first introduced by mathematician Peter Shor, is a quantum algorithm for integer factorization. On a quantum computer, to factor an integer N, Shor's algorithm takes polynomial time in log{N}, specifically O((log{N})^3), demonstrating that integer factorization is in the complexity class BQP. This is exponentially faster than the best-known classical factoring algorithm, the general number field sieve, which works in sub-exponential time - about O(2^{{(log N)}^{1/3}}). Peter Shor discovered the eponymous algorithm in 1994.

Shor's algorithm is important because it can, in theory, be used to "break" the widely used public-key cryptography scheme known as RSA. RSA is based on the assumption that factoring large numbers is computationally infeasible. So far as is known, this assumption is valid for classical computers. No classical algorithm is known that can factor in time polynomial in log N. However, Shor's algorithm shows that factoring is efficient on a quantum computer, so an appropriately large quantum computer can "break" RSA. It was also a powerful motivator for the design and construction of quantum computers and for the study of new quantum computer algorithms.

In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 x 5, using an NMR implementation of a quantum computer with 7 qubits. However, some doubts have been raised as to whether their IBM's experiment was a true demonstration of quantum computation, since no entanglement was observed. Since IBM's implementation, several other groups have implemented Shor's algorithm using photonic qubits, emphasizing that entanglement was observed.


The problem we are trying to solve is: given a composite number N, find an integer p, strictly between 1 and N, that divides N.

Shor's algorithm consists of two parts:

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

Classical part

  1. Pick a random number a < N
  2. Compute gcd(a, N). This may be done using the Euclidean algorithm.
  3. If gcd(a, N) ≠ 1, then there is a nontrivial factor of N, so we are done.
  4. Otherwise, use the period-finding subroutine (below) to find r, the period of the following function:

    f(x) = a^x mbox{mod} N,
    i.e. the smallest positive integer r for which f(x+r) = f(x) Leftrightarrow The order r of a in mathbb{Z}_N.
  5. If r is odd, go back to step 1.
  6. If a r /2 ≡ -1 (mod N), go back to step 1.
  7. gcd(ar/2 ± 1, N) is a nontrivial factor of N. We are done.

Quantum part: Period-finding subroutine

The quantum circuits used for this algorithm are custom designed for each choice of N and the random a used in f(x) = ax mod N. Given N, find Q = 2q such that N^2 le Q < 2N^2, which implies 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 x which produce the same f(x), even as the period r approaches N/2.

Proceed as follows:

  1. Initialize the registers to

    Q^{-1/2} sum_{x=0}^{Q-1} left|xrightrangle left|0rightrangle

    where x runs from 0 to Q − 1. This initial state is a superposition of Q states.

  2. Construct f(x) as a quantum function and apply it to the above state, to obtain

    Q^{-1/2} sum_x left|xrightrangle left|f(x)rightrangle.

    This is still a superposition of Q states.

  3. Apply the quantum Fourier transform to the input register. This transform (operating on a superposition of power-of-two Q = 2q states) uses a Qth root of unity such as omega = e^{2 pi i /Q} to distribute the amplitude of any given left|xrightrangle state equally among all Q of the left|yrightrangle states, and to do so in a different way for each different x:

    U_{QFT} left|xrightrangle
    = Q^{-1/2} sum_y omega^{x y} left|yrightrangle.

    This leads to the final state

    Q^{-1} sum_x sum_y omega^{x y} left|yrightrangle left|f(x)rightrangle.

    This is a superposition of many more than Q states, but many fewer than Q2 states. Although there are Q2 terms in the sum, the state left|yrightrangle left|f(x_0)rightrangle can be factored out whenever x0 and x produce the same value. Let

    omega = e^{2 pi i /Q} be a Qth root of unity,
    r be the period of f,
    x0 be the smallest of a set of x which yield the same given f(x) (we have x0 < r), and
    b run from 0 to lfloor(Q-x_0-1)/rrfloor so that x_0 + rb < Q.
    Then omega^{ry} is a unit vector in the complex plane (omega is a root of unity and r and y are integers), and the coefficient of Q^{-1}left|yrightrangle left|f(x_0)rightrangle in the final state is
    sum_{x:, f(x)=f(x_0)} omega^{x y} = sum_{b} omega^{(x_0 + r b) y} = omega^{x_0y} sum_{b} omega^{r b y}.
    Each term in this sum represents a different path to the same result, and quantum interference occurs — constructive when the unit vectors omega^{ryb} point in nearly the same direction in the complex plane, which requires that omega^{ry} point along the positive real axis.
  4. Perform a measurement. We obtain some outcome y in the input register and f(x_0) in the output register. Since f is periodic, the probability of measuring some pair y and f(x_0) is given by

    left| Q^{-1} sum_{x:, f(x)=f(x_0)} omega^{x y} right|^2
    = Q^{-2} left| sum_{b} omega^{(x_0 + r b) y} right|^2 .

    Analysis now shows that this probability is higher, the closer unit vector omega^{ry} is to the positive real axis, or the closer yr/Q is to an integer.

  5. Turn y/Q into an irreducible fraction, and extract the denominator r′, which is a candidate for r.
  6. Check if f(x) = f(x + r′) Leftrightarrow a^r equiv 1 pmod{N}. If so, we are done.
  7. Otherwise, obtain more candidates for r by using values near y, or multiples of r′. If any candidate works, we are done.
  8. Otherwise, go back to step 1 of the subroutine.

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.

I. Obtaining factors from period

The integers less than N and coprime with N form a finite group under multiplication modulo N. By the end of step 3, we have an integer a in this group. Since the group is finite, a must have a finite order r, the smallest positive integer such that

a^r equiv 1 mbox{mod} N.,

Therefore, N Divides (a r − 1 ). Suppose we are able to obtain r, and it is even. Then

a^r - 1 = (a^{r/2} - 1) (a^{r/2} + 1) equiv 0 mbox{mod} N
Rightarrow N | (a^{r/2} - 1) (a^{r/2} + 1).,

r is the smallest positive integer such that a r ≡ 1, so N cannot divide (a r / 2 − 1). If N also does not divide (a r / 2 + 1), then N must have a nontrivial common factor with each of (a r / 2 − 1) and (a r / 2 + 1).

Proof: For simplicity, denote (a r / 2 − 1) and (a r / 2 + 1) by u and v respectively. N | uv, so kN = uv for some integer k. Suppose gcd(u, N) = 1; then mu + nN = 1 for some integers m and n (this is a property of the greatest common divisor.) Multiplying both sides by v, we find that mkN + nvN = v, so N | v. By contradiction, gcd(u, N) ≠ 1. By a similar argument, gcd(v, N) ≠ 1.

This supplies us with a factorization of N. If N is the product of two primes, this is the only possible factorization.

II. 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, though. A measurement will yield only one of all possible values, destroying all others. But 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.

  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 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.

  3. Perform a quantum Fourier transform.

    By using controlled rotation gates and Hadamard gates Shor designed a circuit for the quantum Fourier transform (with Q = 2q) that uses just q(q-1)/2 = O((log Q)^2) gates. arXiv:quant-ph/9508027v2 p. 14

After all these transformations a measurement will yield an approximation to the period r. For simplicity assume that there is a y such that yr/Q is an integer. Then the probability to measure y is 1. To see that we notice that then

e^{-2 pi i b yr/Q} = 1,
for all integers b. Therefore the sum whose square gives us the probability to measure y will be Q/r since b takes roughly Q/r values and thus the probability is 1/r^2. There are r y such that yr/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.

Modifications to Shor's Algorithm

There have been many modifications to Shor's algorithm. For example, whereas an order of twenty to thirty runs are required on a quantum computer in the case of Shor's original algorithm, in the case of the modification done by David McAnally at the University of Queensland an order of only four to eight runs on the quantum computer is required.

Deutsch and the many worlds interpretation

Quantum physicist David Deutsch uses Shor's algorithm as an argument against single-universe theory in his book, The Fabric of Reality. His argument is as follows: Consider quantum factorization of a 250-digit number. This requires on the order of 10^5^0^0 times the amount of computational resources which appear to be present. If our visible universe contains only 10^8^0 atoms, how, where and when was the computation performed? Deutsch suggests that the computations are performed in other universes, and concludes that this supports the many worlds interpretation.


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"). This preprint was eventually published as SIAM J.Sci.Statist.Comput. 26 (1997) 1484.

A general textbook on quantum computing.
This book was recommended (includes "a complete review of Shor’s algorithm") in the discussion of Aaronson's blog article (see below).

The authors investigate and optimize the resource requirements of Shor's algorithm. They determine the time complexity of factoring N to be about 72 (log N)^3, using a quantum computer with about 5 log N qubits.

Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood & Isaac L. Chuang, Nature 414, 883–887 (20 Dec 2001). abstract
An implementation of Shor's Algorithm that factorizes the number 15.

Juha J. Vartiainen, Antti O. Niskanen, Mikio Nakahara, Martti M. Salomaa

Austin G. Fowler, Simon J. Devitt, Lloyd C. L. Hollenberg
Quant. Info. Comput. 4, 237-251 (2004)

David McAnally. 45 pages. A refinement of Shor's Algorithm for determining order is introduced, which determines a divisor of the order after any one run of a quantum computer with almost absolute certainty. The information garnered from each run is accumulated to determine the order, and for any k greater than 1, there is a guaranteed minimum positive probability that the order will be determined after at most k runs. The probability of determination of the order after at most k runs exponentially approaches a value negligibly less than one, so that the accumulated information determines the order with almost absolute certainty. The probability of determining the order after at most two runs is more than 60%, and the probability of determining the order after at most four runs is more than 90%.

External links

Search another word or see Factoring problemon Dictionary | Thesaurus |Spanish
Copyright © 2014, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature