Quantum factorizing algorithm

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. 

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. 

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. 

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. 

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. 

There is another quantum routine to be discussed before moving to Shot s factorization algorithm. The order of a number is a concept from Number Theory, which is beyond the scope of this book. However, some of its features, necessary to understand Shot s algorithm, will be discussed on this section. 

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. 

Quantum Fourier Transform (QFT), as explained in Chapter 3, is a key step for quantum algorithms which exhibit exponential speed up. Its main application is in the Shot s factorization algorithm, which uses order finding and period finding [12]. These are in turn variations of the general procedure known as phase estimation [13],... 

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

It is interesting to note that to actually implement a useful algorithm it is necessary to implement a certain number of quantum operations within the coherence time. Recently, we reported that it was possible to increase the number of coherent rotations by a factor of 10 by matching the Rabi frequency with the frequency of the proton in the polyoxometalate SIM GdW30. Under these conditions, it was possible to perform at least 80 such operations (Figure 2.14) [75]. 

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. 

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

We remark that the simulation scheme for master equation dynamics has a number of attractive features when compared to quantum-classical Liouville dynamics. The solution of the master equation consists of two numerically simple parts. The first is the computation of the memory function which involves adiabatic evolution along mean surfaces. Once the transition rates are known as a function of the subsystem coordinates, the sequential short-time propagation algorithm may be used to evolve the observable or density. Since the dynamics is restricted to single adiabatic surfaces, no phase factors... 

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. 

---