$
\newcommand{\ket}[1]{\lvert {#1}\rangle}
\newcommand{\ds}{\displaystyle}
$

# Shor's Algorithm

## Introduction
Problem
> Integer factorization

Use Case
> $n = p \cdot q$, where $p,q$ are large prime numbers, often used in cryptographic functions

Classical Solution
> **General Number Field Sieve** has best asymptotic behaviour
> Superpolynomial scaling:
> $\displaystyle O(e^{(\ln n)^\frac{1}{3}(\ln\ln n)^{\frac{2}{3}}})$

Shor's Algorthim
> Factorization algorithm with poylnomial complexity <br/>
> Partially on Quantum processor, pre & post processing is classical
> Quantum complexity: $O\big( (\log n)^2 (\log \log n) (\log \log \log n) \big)$
> Polynomial time achieved with Quantum Forier Transform



----

## Algorithm


### 1. Preconditions of $n$

Exit if $n$ is any of the following
- even
- prime 
- prime power

### 2. Attempt brute-force solution

Pick a random integer $x \lt n$, and calculate $\gcd(x, n)$.

If this is not 1, then we have a factor of $n$.

### 3. Quantum Algorithm

1. Pick q as the smallest power of 2 where $n^2 \leq q \leq 2n^2$

2. Find the period $r$ of $x^a \mod n$

3. Measure $c$ which has property $\displaystyle \frac{c}{q} \approx \frac{d}{r}$, where $d \in \mathbb{N}$



### 4. Determine ratio

$r, d$ can be determined if $gcd(d, r) = 1$ using fraction expansion algorithm

### 5. Try to obtain factors

Return to step 2
> if $r$ is odd <br/>
> if $x^{\frac{r}{2}} \equiv -1 \mod n$

Factors are 
>$\displaystyle p, q = \gcd(x^{\frac{r}{2}} \pm 1, n)$

----


### Quantum Fourier Transform (QFT)

Define QFT with respect to an ONB $\left\{\ket{x}\right\} = {\ket{0}, \dots, \ket{q-1}}$
> $\ds QFT: \ket{x} \mapsto \frac{1}{\sqrt{q}} \sum\limits_{y=0}^{q-1} \exp \left\{ \frac{2\pi i}{q}x \cdot y \right\} \ket{y} = \frac{1}{\sqrt{q}} \sum\limits_{y=0}^{q-1} \omega^{x \cdot y} \ket{y}$

Apply QFT to a general state $\ds\ket{\psi} = \sum_x \alpha_x\ket{x}$ :
> $\ds QFT(\ket{\psi}) = \frac{1}{\sqrt{q}} \sum\limits_{y=0}^{q-1} \beta_y\ket{y}$ <br/>
> where the $\beta_y$'s are the discrete Fourier tansform of the amplitudes $\alpha_x$

The QFT is unitary
> $QFT^\dagger QFT\ket{x} = \ket{x}$


----

## References

- [Lecture Notes - Shor's Algorithm][1]
- [Continued Fraction Expansion][2]

 [1]: https://qudev.phys.ethz.ch/content/QSIT15/Shors%20Algorithm.pdf
 [2]: https://www.math.u-bordeaux.fr/~pjaming/M1/exposes/MA2.pdf

----

## Addendum I - Euclidean Algorithm

$
\gcd(a,b) = 
\Bigg\{\begin{split}
&b  & \text{ if } a \bmod b = 0 \\
&\gcd(b, a \bmod b) & \text{ else } \\
\end{split}
$

### References

- [Euclidean Algorithm][1]

 [1]: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm


```python
# Euclidian Algorithm
def gcd(a, b):
    h,l = (max(a,b),min(a,b))
    q = h % l
    if q == 0:
        return l
    return gcd(l,q)

def is_coprime(a, b):
    return (gcd(a, b) == 1)
        
```

----
$\newcommand{\ds}{\displaystyle}$
## Addendum II - Continued Fractions

Tools to approximate a Real number to a Rational number.

### Example 1 - 1 and 2

'1' can be written as a fraction
> $\ds1 = \frac{2}{3-1}$

and as a continued/infinite fraction
> $\ds1 = \frac{2}{3-\frac{2}{3-\frac{2}{3-\dots}}}$

interestingly, using 2 instead would suggest the contradiction $1=2$
> $\ds2 = \frac{2}{3-\frac{2}{3-\frac{2}{3-\dots}}}$

### Example 2 - $\sqrt{2}$

> $
\begin{split}
\sqrt{2} &= 1.414213  \\
&= 1 + 0.41421  \\
&= 1 + \frac{1}{\frac{1}{0.41421 }} \\
&= 1 + \frac{1}{2+ 0.41421 } \\
&= 1 + \frac{1}{2+ \frac{1}{2 + \frac{1}{2 + \dots}}} \\
\end{split}
$ <br/>
> Sequence `11111111...`

### Example 3 - $\phi$ (Golden Ratio)
> $
\begin{split}
\phi &= \frac{1 + \sqrt{5}}{2} \\
&= 1 + \frac{1}{1+ \frac{1}{1 + \frac{1}{1 + \dots}}}
\end{split}
$ <br/>
> Sequence `11111111...`

### Example 4 - $e$ (2.718)
> $
\begin{split}
e &= \frac{1 + \sqrt{5}}{2} \\
&= 2 + \frac{1}{1+ \frac{1}{2 + \frac{1}{1 + \frac{1}{1 + \frac{1}{4 + \dots}}}}}
\end{split}
$ <br/>
> Sequence - `2114116118...`

### Example 5 - Rational $\frac{1473}{50}$
*Rational numbers tend to be finite*
> $29 + \frac{1}{2 + \frac{1}{5 + \frac{1}{1 + \frac{1}{3}}}}$

### Example 5 -$\pi$
> $
\begin{split}
\pi &= 3.14159265358979 \\
&= 3 + \frac{1}{7+ \frac{1}{15 + \frac{1}{1 + \frac{1}{292 + \dots}}}} \\
3 &= 3.0 \\
3 + \frac{1}{7} = \frac{22}{7} &= 3.14 \\
3 + \frac{1}{7+\frac{1}{15}} = \frac{333}{106} &= 3.1415 \\
3 + \frac{1}{7+\frac{1}{15 + 1}} = \frac{355}{113} &= 3.141592 \\
3 + \frac{1}{7+\frac{1}{15 + \frac{1}{1 + \frac{1}{292}}}} = \frac{103993}{33102} &= 3.14159265 \\
\end{split}
$

----

## Addendum III - Example, Factoring n=21

### 1. Choose a random integer $x$, where $1 < x < n$

> if x *is **not** coprime* with n (i.e. x=6) <br/>
> $\gcd(x,n) = \gcd(6, 21) = 3$ <br/>
> $\therefore \frac{21}{3} = 7$ <br/>
> The factors are 7 and 3 

> if x *is coprime* with n (i.e. x=11) <br/>
> $\gcd(11,21) = 1$ <br/>
> then continue...

### 2. Determine q

> Where q is the smallest power of 2 between $n^2$ and $2n^2$ <br/>
> $441 \leq q < 882 \land \log_2(q) = l : l \in \mathbb{N}$ <br/>
> $l=9, q=512$

> Initial state for 2 registers with length of 'l' <br/>
> $\ket{\Phi_i} = \ket{0}_{r_1} \ket{0}_{r_2} = \ket{0}^{\otimes 2^l}$

### 3. Initialize first register ($r_1$)

> Initialize first register with superposition of all stats $a \pmod{q}$ 
> $\ds\ket{\Phi_0} = \frac{1}{\sqrt{512}} \sum\limits_{a=0}^{511} \ket{a}\ket{0} $ <br/>
> therefore all bits are $\frac{1}{\sqrt{2}}\Big(\ket{0} + \ket{1}\Big)$


### 4. Initialize second register ($r_2$)

> Initialize Register with superposition of all states $x^a \pmod{n}$
> $\ds
\begin{split}
\ket{\Phi_1} &= \frac{1}{\sqrt{512}} \sum\limits_{a=0}^{511} \ket{a}\ket{11^a(\bmod{21})} \\
&= \frac{1}{\sqrt{512}} \Big( \ket{0}\ket{1} + \ket{1}\ket{11} + \ket{2}\ket{16} + \ket{3}\ket{8} \dots \Big)
\end{split}$ <br/><br/>
> The sequence looks like this
>$ 
\begin{matrix}
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\
1 & 11 & 16 & 8 & 4 & 2 & 1 & 11 & 16 & 8 & 4 & \dots \\
\end{matrix}
$ <br/>
> *The period is 6, but not yet observable*

### 5. Quantum Fourier Transform
> $\ds \overset{\sim}{\ket{\Phi}} = \frac{1}{512} \sum\limits_{a=0}^{511} \sum\limits_{c=0}^{511} e^{\big(\frac{1}{512} 2\pi i a c\big)} \ket{c}\ket{11^a(\bmod{21})}$

### 6. Measurement
> Probability for state $\ket{c, x^k\pmod{n}}$ e.g. $k=2 \rightarrow \ket{c,16}$ <br/>
> $\ds
\begin{split}
p(c) &= \Bigg| {\frac{1}{512}}_{a:11^a} \sum\limits_{\bmod{21}=16}^{511} e^{\big(\frac{1}{512} 2\pi iac\big)} \Bigg|^2 \\
&= \Bigg| {\frac{1}{512}}_{a:11^a} \sum\limits_{b} e^{\big(\frac{1}{512} 2\pi i(6b+2)c\big)} \Bigg|^2\\
\end{split}$ <br/>
>
> Simulation of the probability amplitude of a period of 6


```python
PERIOD=6

import sympy as sm
import numpy as np
import matplotlib.pyplot as plt

fig = plt.gcf()
fig.set_size_inches(8,5)

sm.var('x')
# This function is a simulation, it does not 
# reflect a multi-modal normal distribution 
f = lambda x: ((sm.cos((x*PERIOD*2*sm.pi)/512)+1)/2)**80/PERIOD

x = np.linspace(0,512,1000)
y = np.array([f(v) for v in x],dtype='float')

plt.title(r"Probaility Amplitudes with a period of 6 peaks fro $c =\frac{512}{6} \cdot d, d \in \mathbb{Z}$")
plt.plot(x,y,color='gray')
plt.fill_between(x,y,0,color='#c0f0c0')

plt.show()
```



### 7. Determine the period
Continued Fraction Expansion (determine r) 
> $\ds \Bigg| \frac{c}{q} - \frac{d}{r} \Bigg| = \overset{!}{\leq} \frac{1}{1024}$ <br/><br/>
> Use continued fraction expansion <br/>
> $\ds
\begin{split}
\frac{c}{q} &= a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \dots}}  \\
\tfrac{d_0}{r_0} &= \tfrac{a_0}{1} \\
\tfrac{d_1}{r_1} &= \tfrac{1+a_0a_1}{a_1} \\
\tfrac{d_n}{r_n} &= \tfrac{a_nd_{n-1} + d_{n-2}}{a_nr_{n-1} + r_{n-2}} \\
&\dots \\
\end{split}
$

Assume the reading was **427** <br/> 
> So <br/>
> e = $\ds \Bigg| \frac{427}{512} - \frac{d}{r} \Bigg| \overset{!}{\leq} \frac{1}{1024}$ <br/><br/>
> Use continued fraction expansion <br/>
> $\ds
\begin{split}
\frac{427}{512} &= 0.83398\dots \\
&= 0 + \frac{1}{1 + \frac{1}{5 + \frac{1}{42 + \frac{1}{2}}}} \\
\tfrac{d_0}{r_0} &= \tfrac{0}{1} = 0 \;\;\; &e = \tfrac{427}{512} > \tfrac{1}{1204} \text{  no match}\\
\tfrac{d_1}{r_1} &= \tfrac{1}{1} = 1 \;\;\; &e = \tfrac{85}{512} > \tfrac{1}{1204} \text{  no match}\\
\tfrac{d_2}{r_2} &= \tfrac{5}{6} = 0.8\dot{3} \;\;\; &e = \tfrac{2}{3072} < \tfrac{1}{1204} \text{  match!}\\
\tfrac{d_3}{r_3} &= \tfrac{427}{512} = 0.83398\dots \;\;\; &e = 0 \\
\end{split}
$ <br/><br/>
> $\frac{5}{6}$ is a match, &#x2003; $d(427)$ and $r(6)$ are coprime, &#x2003; therefore the period **r = 6**

Assume the reading was **171** <br/>
> we would get $\frac{d}{r} = \frac{1}{3}$, &#x2003; $d(171)$ and $r(3)$ are *not* coprime, therefore this does not work, try again.

### 8. Check r (determine factors)

Check r is even
> $6 \pmod{2} = 0$

Check if $x^{\tfrac{r}{2}} \pmod{n} \ne -1$
> $11^{\tfrac{6}{2}} \pmod{21} = 11^3 \pmod{21} = 1331 \pmod{21} = 8 \ne 1330$

Calculate factors via $x^{\tfrac{r}{2}}\pmod{n} \pm 1$
> $1331 \pmod{21} - 1 = 7$ <br/>
> $1331 \pmod{21} + 1 = 9$ <br/>


```python

```

78b3eb20957370e4568125a1a85715e2c203f0ff
ipynb
Jupyter Notebook
notebooks/quantum-computing/shors_algorithm.ipynb
sparkboom/my_jupyter_notes
9255e4236b27f0419cdd2c8a2159738d8fc383be
MIT
notebooks/quantum-computing/shors_algorithm.ipynb
sparkboom/my_jupyter_notes
9255e4236b27f0419cdd2c8a2159738d8fc383be
MIT
notebooks/quantum-computing/shors_algorithm.ipynb
sparkboom/my_jupyter_notes
9255e4236b27f0419cdd2c8a2159738d8fc383be
MIT
Qwen/Qwen-72B
1. YES
2. YES