Factoring

• The quantum algorithm which has probably done the most for popularizing quantum computation is Shor's factoring algorithm. As noted above, a fast algorithm for factoring numbers with several hundred digits would invalidate some of the most widely used encryption systems. Shor's algorithm provides theoretical evidence for such an algorithm, waiting only for a practical physical realization.
• The general approach used by Shor is based on a classical probabilistic method for factoring. The classical algorithm is exponential in the number of digits - Shor's is (quantum) polynomial.
• Outline of Shor's algorithm for factoring a number M:

  1.

  Choose an integer y < M arbitrarily. If y is not relatively prime to M, we've found a factor of M. Otherwise apply the rest of the algorithm.

  2.

  Let n be such that $M^2 \leq 2^n < 2M^2$. We begin with n qubits, each in state $\vert{0}\rangle$. We now apply the Walsh transformation W to superpose all states:
  

  $$\sum_{a=0}^{2^n-1}\vert{0}\rangle \overset{W}\longmapsto \frac{1}{\sqrt{2^n}}\sum_{a=0}^{2^n-1}\vert{a}\rangle.$$

  
  

  3.

  Apply a transformation which implements raising to powers $\pmod{M}$:
  

  $$\frac{1}{\sqrt{2^n}}\sum_{a=0}^{2^n-1}\vert{a}\rangle \mapsto \frac{1}{\sqrt{2^n}}\sum_{a=0}^{2^n-1}\vert{a, f(a)}\rangle$$

  
  

  where $f(a) = y^a\pmod{M}$.

  4.

  Measure to find a state whose amplitude has the same period as f.

  5.

  Apply a quantum Fourier transform to invert the frequency.

  6.

  Extract the period, which we expect to be the order of $y\pmod M$.

  7.

  Find a factor of M.

  When our estimate for the period, q, is even, we use the Euclidean algorithm to efficiently check whether either y^q/2+1 or y^q/2-1 has a non-trivial common factor with M.

  8.

  Repeat the algorithm, if necessary.