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

One of the main features of the Shor algorithm is that it uses the QFT operation, which needs only O(n ) operations while its classical analogous, the FFT (Fast Fourier Transform) needs 0(u2 ) operations. 

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. 

Let us first review an application of QFT a quantum circuit to estimate the phase of a state, (p, which is eigenket of an operator U U u) = The procedure requires two 

These controlled operations apply the operator U on the second register, 2 times, where k is the label of the qubit which is controlling the operation, noticing that k = 0,1.r — 1. The f/-controlled operation performs the transformation n) M) n)U u) = taking the system to the state described by Equa- 

---