Using Shor’s Algorithm to Achieve Factor Decomposition

Introduction to Shor’s Algorithm

The time complexity of Shor’s algorithm to decompose integer N on a quantum computer is \(logN\), which is almost the exponential acceleration of \(e\) for the most effective classical factorization algorithm known. Such acceleration may break modern encryption mechanism such as RSA on a quantum computer.

The basic idea of Shor’s algorithm

The main problem to be solved by Shor’s algorithm is: given an integer N, find its prime factor. That is, determine the two prime factors \(p_1\)and \(p_2\) which satisfy \(p_1\cdot p_2=N\) for a given large number of \(N\) in polynomial time. Before introducing the steps of Shor’s algorithm, I would like to discuss more about the number theory.

Number theory:

Factorization involves some knowledge of number theory and can be reduced to the following functions:

\[f(x) = a^x\mathrm{mod} N\]

For a seek of \(a\), \(a\) and \(N\)are mutually exclusive, you can get a factor right away by calling \(gcd (a,N)\), as the period \(r\) of \(f(x)\) satisfies \(f(x) = (x+r)\). In this case, we can get \(a^x = a^{x+r}\mathrm{mod}N\forall x\). And some integer \(q\) satisfies \(a^r-1 = (a^{r/2}-1)(a^{r/2}+1) = qN​\) in the equation \(a^r = 1+qN​\). This also shows that you can find the factor of \(N​\) by using \(gcd​\).

Therefore, the core of Shor’s algorithm is to transform the problem of large number decomposition into the problem of finding period (as shown in the following). We can construct a unitary matrix \(U_{x,N} \left| {j} \right\rangle \left| {k} \right\rangle -> \left| {j} \right\rangle \left| {x^jk \mathrm{mod} N} \right\rangle\), then the result of end satisfies \({x^r} = 1\left( {\bmod N} \right)\).

Below we take \(N = 15\) as an example to introduce the steps of Shor’s algorithm in factorization:

  1. Select an arbitrary number, such as \(a = 2\) (<15)

  2. \(gcd⁡ (a,N) = gcd (2,15) = 1\)

  3. Fine the period of function \(f(x) = {a^x}\bmod N\), which satisfies \(f(x + r) = f\left( x \right)\)

  4. Get r = 4 through the circuit diagram calculation

  5. \(gcd ({a^{\frac{r}{2}}} + 1,N) = gcd (5,15) = 5\)

  6. \(gcd ({a^{\frac{r}{2}}} - 1,N) = gcd (3,15) = 5\)

  7. For \(N = 15\), the two decomposed prime numbers are 3 and 5. Problem solved.

Quantum circuit of Shor’s algorithm:

../_images/shor.png