$\require{cancel} \newcommand{\Ket}[1]{\left|{#1}\right\rangle} \newcommand{\Bra}[1]{\left\langle{#1}\right|} \newcommand{\Braket}[1]{\left\langle{#1}\right\rangle} \newcommand{\Rsr}[1]{\frac{1}{\sqrt{#1}}} \newcommand{\RSR}[1]{1/\sqrt{#1}} \newcommand{\Verti}{\rvert} \newcommand{\HAT}[1]{\hat{\,#1~}} \DeclareMathOperator{\Tr}{Tr}$
Shor's Algorithm¶
First created in August 2018
One of the motivation of investment in quantum computing is to factorise large numbers, which can be used in code breaking. This article however is a study note, not to emphasis the potentials of quantum computing technology in commercial or military use.
A recap on modular arithmetic: (All numbers here are integer.)
$a\equiv b\pmod N\Leftrightarrow a-b=kN.~~~$
e.g. $11\equiv5\pmod3$, as $3\mid(11-5)$ where $\mid$ reads "divides".
That is to say that 11 and 5 have the same remainder when divided by 3.
Most "intuitive" properties apply. Some to be used in this context are given below.
$a\equiv b\pmod N\Rightarrow ma\equiv mb\pmod N~~\forall m\in\mathbb I$.
Proof: $a\equiv b\pmod N\Rightarrow a-b=kN\Rightarrow m(a-b)=k'N\Rightarrow ma\equiv mb\pmod N.$
$a\equiv b\pmod N\Rightarrow p(a)\equiv p(b)\pmod N$,
where $p(x)$ is a polynomial of $x$.
Proof: $a\equiv b\pmod N\Rightarrow a^m-b^m=(a-b)\sum_{r=0}^{m-1}a^{m-r-1}b^r=0\pmod N.$
If $m$ is coprime with $N$, we have
- $ma\equiv mb\pmod N\Rightarrow a\equiv b\pmod N$, and
- $a\equiv b\pmod{\varphi(N)}\Rightarrow m^a\equiv m^b\pmod N$ (which is not generally true without the LHS condition).
Here $\varphi$ is Euler's totient function.
Basic Idea¶
Let us start from the end game of factorising $N$ into two prime numbers: $N=p_1p_2$.
Setting the Scene¶
With modular arithmetic, if $a^r\equiv 1\pmod N$, we have $a^{x+r}=a^x\cdot a^r\equiv a^x\cdot1\pmod N\equiv a^x\pmod N$ ($a^x$ and $N$ is coprime).
This is analogous to $f(x+r)=f(x)$. The smallest value of $r$ that satisfy this condition is called the period.
Now let us find an arbitrary number $a\in[2,N-1]$ which is coprime with $N$. That means $\gcd(N,a)=1$. (Computing GCD using Euclidean algorithm takes polynomial time, which we will discuss later.)
If $\gcd(N,a)>1$, then the value of GCD is a factor of $N$ and the problem is solved. This is highly unlikely for large $N$. So we continue, assuming that $\gcd(N,a)=1$.
Now we have $a$ and $N$ coprime, we will find the period $r$ that is positive and even. Failing that, we will need to select a different $a$ and try again. (We only need few repetitions to find a period that is even.)
Here are what we have so far:
- $a\in[2,N-1].$
- $\gcd(N,a)=1.$
- $a^r\equiv1\pmod N.$
- $r/2\in\mathbb N.$
Doing the Trick¶
$N\mid a^r-1=(a^{r/2}-1)(a^{r/2}+1).$
We know $(a^{r/2}-1)$ is not a multiple of $N$. Otherwise, $r/2$ would be the period.
We also require $(a^{r/2}+1)$ being not a multiple of $N$ either. Otherwise, we will start again with another $a$. (Such case is rare so another call will usually fix it.)
Given the above, one of two prime factors of $N$ ($p_1$ or $p_2$) must be a factor of either $a^{r/2}-1$ or $a^{r/2}+1$. Another GCD run will determine which case is true, hence solve the factorisation problem.
As a result, the factorisation problem is reduced to period finding problem (with the assistence of polynomial time Euclidean algorithm to find GCD).
An Example¶
Let $N=15$ and $a=7$. The period is found to be 4.
- $7\in[2,14].$
- 15 and 7 are coprime.
- $7^4\equiv1\pmod{15}.$
- $4/2=2\in\mathbb N.$
$15\mid7^4-1=(7^2-1)(7^2+1)=48\cdot 50.~~$ Neither 48 nor 50 are multiple of 15, but $\gcd(15,48)=3$. Dividing 15 by 3, we have $15=3\cdot 5.$
Period Finding¶
Factorisation problem can be reduced to period finding problem, as illustrated above. That involves some classical algorithm of polynomial time (Euclidean algorithm to find GCD).
Classical algorithm requires exponential time to find the period. By making use of quantum parallelism and constructive interference, Shor's algorithm can do the same in polynomial time.
From the above example, where $N=15$ and $a=7,~~ 7^1\equiv7\pmod{15},~~ 7^2\equiv4\pmod{15},~~ 7^3\equiv4\cdot7\equiv13\pmod{15},~~ 7^4\equiv13\cdot7\equiv1\pmod{15}.$ So the period is $4$. Also, $7^{x+4}\equiv7^x\cdot7^4\equiv7^x\equiv1\pmod{15}.$
The Unitary¶
Let us define $f(x)=xa\pmod N$, and find a unitary $U_a$ to implement it.
Phase shifting "wrap around" at $2\pi$, which is a familiar pattern in modular arithmetic. So $R_z(\phi)=\begin{bmatrix}1&0\\0&e^{i\phi}\end{bmatrix}$ closely resembles $f(x)$.
We want to iterate $r$ times to have the phase shifted by $2\pi$. This means after $k$ iteration, the phase is $2\pi k/r.$
Code Section Template¶
# Initialisation
import sys
sys.path.append('../')
from qtol import *
# Iteration
# Number of qubits
qbNum = 1
# Define the Quantum and Classical Registers
q = QuantumRegister(qbNum)
c = ClassicalRegister(qbNum)
qc = QuantumCircuit(q, c)
# Preparation
qc.iden(q)
# Circuit building
# ...
# Finalisation
# ...
show_me(qc, q, c, show_latex=True, show_bloch_vector=True, show_histogram=True)
circuit_drawer(qc)
