Shor factorization algorithm

Shor s algorithm runs in time which grows only polynomially with log iV. For instance, in order to factorize a number of 1024 bits, for instance, 100 thousand years are necessary, using present day classical computers. The same task could be made in less than 5 minutes, using a quantum computer running the Shor factorization algorithm. 

Shor factorization algorithm tested in a 7-qubit molecule... 

Figure 5.9 NMR spectra of the first register (3 qubits) in the implementation of the Shor factoring algorithm [18]. (a) Equilibrium spectra (b) Initial pseudo-pure state (c) Output spectra for a = 11 (see text), and (d) Output spectra for a = 7 (see text).

Shor s algorithm for factoring a product N of two prime numbers. At the heart of the algorithm is a periodic function f Z//V Z//V whose period one must calculate in order to find the two prime factors of N. The phase space for computation is a pair of registers of size L, where 2 < N < 2. In other words, the state space for the quantum computer is... 

As of this writing, 3-, 5- and 7-qubit NMR quantum computers have been realized. The latter is capable of carrying out Shor s algorithm to factor the number 15, thus equalling the computational ability of a first-grade elementary school student. 

L.M.K. Vandersypen, M. Steffan, G. Breyta, C.S. Yannoni, M.H. Sherwood, l.L. Chuang, Experimental realization of Shor s quantum factoring algorithm using nuclear magnetic resonance, Nature 414 (2001) 883. 

In Quantum Computing, the Quantum Fourier Transform (QFT) is behind the exponential gain in the speed of algorithms [10] such as Shor s factoring algorithm [11,12], The operator QFT can be implemented using only Q(n ) operations, whereas its classical analogue, the Fast Fourier Transform (FFT) requires about Q(n2 ) operations. Therefore, QFT is implemented exponentially faster than the FFT. 

The most important quantum algorithm, the Shor algorithm [11], uses the QFT for finding the order of a number, which increases the speed of the factorization process. These are basically implemented by the same quantum circuit and are the main reasons for the exponential gain of speed in comparison with the classical factorizing algorithm. 

The factorization algorithm has 4 stages, but only the last one is quantum in nature. In fact, it turns out that the factorization problem can be reduced to an order finding problem, which can be implemented using basically the same quantum routine for phase estimation. Thus, phase estimation and order finding are subroutines to Shor algorithm, and they will be discussed in the next subsections. 

It is clear that for large integers, this procedure is not efficient, since finding the order is a non-trivial procedure. The power of Shor s factorization algorithm lies in the fact that a quantum routine, which is extremely efficient, can be used to determine the order of a number. 

For illustration purposes, we will show how to factorize the number 15, using the Shor s algorithm. This is also the number used in the first, and only, experimental implementation of this algorithm, utilizing the Nuclear Magnetic Resonance technique [21] (see Chapter 5). Since 15 is the product of two prime numbers, 3 and 5, the two first tasks will fail. The third task is to pick randomly a number x, let s choose x = 7, and check if gcd(7,15) > 1. This task is also going to fail, because 7 is not a factor of 15. Therefore, the next step is to find the order, r. 

The most remarkable advance in the field, the one that made the field famous, is the fast factor algorithm discovered by Shor at Bell Laboratories. It demonstrates that exponential speedup can be obtained using a quantum computer to factor large numbers into their prime components. Effectively, this quantum factorization algorithm works because it is no more difficult, using a quantum computer, to factor a large number into its prime factors than it is to multiply the prime factors to produce the large number. It is this condition that renders a quantum computer exponentially better than a classical computer in problems of this type. 

Ekert, A., and R. Jozsa. 1996. Quantum computation and Shor s factoring algorithm. Review of Modem Physics 68(3) 733-753. 

Shor, P. W. Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer. Proc. 35th Annual Symposium on the Foundations of Computer Science Goldwasser, S. Ed. IEEE Computer Society Press Los Alamos, CA, 1994, p. 124. 

The distinctive feature of a quantum computer is the ability to store and process superpositions of numbers [93]. This potential for parallel computation has led to the discovery that certain problems would be more efficiently solved on a quantum computer than on a classical computer [94, 95]. The most dramatic example is an algorithm presented by Shor [96], showing that a quantum computer should be able to factorize large numbers very easily. This would have a large social impact since the security of many data encryption systems relies on the inability of classical computers to factorize large numbers. 

This realization is at the heart of quantum computation and led, in 1993, to Peter Shor s astounding result of a polynomial-time algorithm for factoring on a quantum computer [Shor 1994], In contrast, the best known classical algorithms for factoring are virtually exponential in run time. 

Shoe s algorithnn An algorithm in quantum computing that enables large numbers to be factorized into prime numbers in a way which is much quicker than using tradition computers. This algorithm, which was proposed by the American computer scientist Peter Shor (1959- ) in 1994, has major implications for the security of Internet information transfer. 

However, it was in 1994 that a main breakthrough happened, calling the attention of the scientific community for the potential practical importance of quantum computation and its possible consequences for modem society. Peter Shor discovered a quantum algorithm capable of factorizing large numbers in polynomial time [8]. Classical factorization is a kind of problem considered by computation scientists to be of exponential complexity. 

This basically means that the amount of time required to factorize a number N bits long, increases exponentially with N. In contrast, a quantum computer running Shor algorithm would require an amount of time which would be a polynomial function of N. This is a huge difference To give an example, if IV = 1024 bits, a classical algorithm would take about 100 thousand years to factorize the number, whereas Shor algorithm would accomplish the task in a few minutes ... 

Shor algorithm has not yet been tested in numbers that long, but its quantum working principles have already been demonstrated in laboratory, through the technique of nuclear magnetic resonance (NMR) [9], The algorithm clearly raises important concerns about the security of cryptosystems based on the factorization of large numbers, such as the RSA protocol. Arthur Eckert captures the essence of the problem in the quote [10] .. .modem security systems are in a sense already insecure... . 

P.W. Shor, Algorithms for quantum computation discrete logarithms and factoring, in Pmc. 35th Annual Symp. Found. Comput. Sci. (IEEE Press, Los Alamitos, 1994). 

The circuit was designed to test the prime factors of the integer 15 (that is, 3 and 5), and sequences of 300 pulses separated by different free evolution implemented, in which the qubits in the system interact only with each other. As explained in Chapter 3, in one of the steps of Shor algorithm it is necessary to evaluate the function f x) = a mod N, where N is the number to be factorized (A = 15 in the present case), and u is an integer, co-prime of N, which for A = 15 can be 2,4,7,8,11,13 and 14. This procedure allows the determination of the period of the function f x) = mod N, or the order, r, which is the least integer such that a " = 1 mod 15. From the order or period it is then possible to determine at least one prime factor of N, using classical number theory techniques. If the value for a, which is randomly picked, is chosen to be a = 2, 7, 8, or 13, we will have ri" = 1 mod 15, whereas u = 4, 11 or 14, one will have = 1 mod 15. The cases a = l and a = 11 were tested in the experiment. 

Shor PW (1997) Pol5momial-time algorithms for prime factorization and discrete logeirithms on a quantum computer. SIAM J Comput 26 1484... 

Shor, P.W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Rev. 41(2), 303-332 (1999)... 

---