Shor’s algorithm

Figure 7.4 Proposals of hardware for QC. (a) Ions trapped in a radiofrequency cavity and cooled by lasers (b) molecule used to implement Shor s algorithm with NMR using...

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. 

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. 

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. 

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. 

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. 

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. 

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

The idea of using quantum states for computation was first considered by Be-nioff [12]. Recently, Shor s proof that encrypted messages could be quickly deciphered by quantum algorithms which allow for a fast factorization of numbers into primes [13] has caused much excitement. 

There is no classical algorithm known that solves the factorization problem in polynomial time though the problem has been studied extensively. (The term polynomial refers to the memory necessary to code the input which is 0 n) for the factorization problem.) Nowadays, the factorization is so widely believed to be practically insolvable for large n that it is even used as the basis for cryptosystems [54,55]. Shor s celebrated result is that the third problem can be solved in polynomial time on a probabilistic quantum computer. 

Again, Shor s and Grover s algorithms are based on the ideas given by Deutsch and Jozsa in [5]. 

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. 

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. 

---