# Shor's Algorithm
- factor a number

### Fourier Transform
- classical Fourier transform
- input: $x_0,x_1...,x_{n-1}$
- output: $y_0,y_1...,y_{n-1}$
- Definition:
$$y_k=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j e^{2\pi i j\cdot k/N}=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1} \omega_N^{jk}x_j$$
- cost?
- naive: $O(N^2)$ for $N$-vector
- more efficient: Fast Fourier Transform (FFT): $O(n\log n)$

- Quantum Fourier transform (QFT)
- acts on **orthonormal basis** $|0\rangle,|1\rangle,...,|N-1\rangle$
$$|y_k\rangle=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi i j\cdot k/N}|k\rangle$$
- If start at a basis state, **no entanglement** will be created (results in a product state)
- Resources of $n$-qubit QFT gate:
- $O(n)$ hadamard gates
- $O(n^2)$ single qubit rotation gates (2 CNOT each)
- at most $n/2$ swap gate: $O(n)$ (3 CNOT each)
> $O(n^2)$ Quantum Algorithm
- classical FFT: $O(n2^n)$
- QFT provdes an **exponential** speed up
> QFT is <ins>not</ins> an algorithm to speed up classical transformation
> **Problem:** No way known to **access the amplitude** in quantum computer.
> No way known to **prepare efficiently original state** to be transformed.
> *an ingredient of other quantum algorithm*
### Phase Estimation
- make use of QFT
- Setting:
- $U$: unitary
- eigenvector $|u\rangle$ with eigenvalues $e^{2\pi i\varphi}$, where $\varphi$ is unknown
- **Goal:** to estimate $\varphi, \varphi\in[0,1]$
- Assumption:
- can prepare $|u\rangle$
- can perform controlled-$U^{2^j}$
- **Algorithm:**
1. 1-st register prepare $t$ qubits $|0\rangle$, where $t$ depends on
- precision
- success probability

2-nd register begin in $|u\rangle$, contains as many qubits as needed to store $|u\rangle$
$$|0\rangle|u\rangle$$
2. Hadamard gates to 1-st register
$$|0\rangle|u\rangle\xrightarrow[]{H}\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)|u\rangle$$
3. Controlled-$U^{2^j}$ on 2-nd register
$$\begin{aligned}\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)|u\rangle\xrightarrow[]{c-U^{2^j}}&\frac{1}{\sqrt{2}}|0\rangle|u\rangle+\frac{1}{\sqrt{2}}U^{2^j}|1\rangle|u\rangle\\
=&\frac{1}{\sqrt{2}}|0\rangle|u\rangle+\frac{1}{\sqrt{2}}e^{2\pi i 2^j\varphi}|1\rangle|u\rangle\\
=& \frac{1}{\sqrt{2}}(|0\rangle+e^{2\pi i 2^j\varphi}|1\rangle)|u\rangle
\end{aligned}$$
- $t$-qubit
$$\frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}e^{2\pi i\varphi k}|k\rangle$$
- suppose $\varphi=0.\varphi_1...\varphi_t$
$$\frac{1}{\sqrt{2^t}}(|0\rangle+e^{2\pi i\cdot 0.\varphi_t}|1\rangle)(|0\rangle+e^{2\pi i\cdot 0.\varphi_t\varphi_{t-1}}|1\rangle)...(|0\rangle+e^{2\pi i\cdot 0.\varphi_t...\varphi_1}|1\rangle)$$
The Fourier transform of $|\varphi\rangle=|\varphi_1\rangle|\varphi_2\rangle...|\varphi_t\rangle$

4. apply inverse QFT to the 1-st register
$$\frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}e^{2\pi i\varphi k}|k\rangle|u\rangle\xrightarrow[]{FT^\dagger}|e\rangle|u\rangle$$

5. measure the qubits of first register in computational basis
- **Discuss:**
- To achieve accuracy $2^{-n}$ with probability $(1-\varepsilon)$
$$t=n+\lceil\log(2+\frac{1}{2\varepsilon})\rceil$$
- What if we cannot prepare the eigenstates $|u\rangle$?
$$|\psi\rangle=\sum_u C_u|u\rangle$$
After the estimation, we get
$$\sum_u C_u |\tilde{\varphi_u}\rangle|u\rangle$$
where $\tilde{\varphi_u}$ is a good approximation to the eigenvalue $\varphi_u$
with probability $|C_u|^2$ we get $\tilde{\varphi_u}$
If we do it many times, we can avoid the requirement of preparing $|u\rangle$

### Order Finding
- output $r$ where $x^r=1\text{ mod }N$
- is a hard problem in classical computer (no polynomial time algorithm)
- in quantum computer, it is the phase estimation algorithm applied to the unitary
$$U|y\rangle=|xy\ (\text{ mod }N)\rangle$$
$y$ is an $b$-qubit state
- construct
$$|u_s\rangle=\frac{1}{\sqrt{r}}\sum_{k=0}^r\text{exp}(-\frac{2\pi i s k}{r})|x^k\text{ mod }N\rangle$$
For integer $s$, $|u_s\rangle$ are eigenstates of $U$.
$$U|u_s\rangle=\text{exp}(\frac{2\pi i s}{r})|u_s\rangle$$
so $\text{exp}(\frac{2\pi i s}{r})$ is the eigenvalue of $|u_s\rangle$
This allows us to estimate $\frac{s}{r}=\varphi$
$\Rightarrow$ with the addition work to access order $r$
- **Problem:** not allowed to use $r$, we cannot prepare $|u_s\rangle$
- $\Rightarrow$
$$\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}|u_s\rangle=|x^0(\text{ mod }N)\rangle=|1\rangle$$
$|1\rangle$ is trivial to prepare

- **Algorithm:**
1. prepare 1-st register with $t$ qubits $|0\rangle$
prepare 2-nd regester with $|1\rangle$
2. run phase estimation
3. measuring the first registers
- for each $s$ in the range of $1$ to $r$, this will lead to an estimation of the phase $\varphi=s/r$
- accuracy: $2L+1$ bits
- probability $(1-\varepsilon)/r$
- "$/r$" because don't know which $|u_s\rangle$ $$\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}|u_s\rangle$$
entangled with the second register when measuring.

- **moduler exponentiation**
- speed up exponentiation $|z\rangle|x^z\rangle$
- use the third temporary registers
- <ins>reversible computing</ins>
- $O(L)$ spanning operations
$O(L^2)$ standard multiplication for each operation
$\Rightarrow$ total $O(L^3)$ operations
- How to get $r$ from the output $\varphi$
4. run continued function algorithm (on a classical computer)
- **Continued Fraction Algorithm**
- a rational number $s/r$ such that
$$\left|\frac{s}{r}-\varphi\right|\leq\frac{1}{2r^2}$$
then $s/r$ is a convergence of the continued fraction for $\varphi$, and can be calculated in $O(L^3)$ steps
- idea: express the number as
$$[a_0,a_1,...,a_M]=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{...+\frac{1}{a_M}}}}$$
- check $[a_0],[a_0,a_1],...[a_0,...a_M]$ which satisfies $s/r$
- the algorithm provides efficiently $s'/r'$
- **complexity**
- Hadamard gates: $O(L)$
- Inverse FT: $O(L^2)$
- Modular exponentiation: $O(L^3)$
- classical continued fraction algorithm: $O(L^3)$
- If order finding fails, one has to repeat only for a *constant* number to obtain $r$ with high probability: $O(1)$
$\Rightarrow$ overall cost: $O(L^3)$
> can be reduced to almost $O(L^2)$ by square-and-multiply

### Shor's Algorithm
- Factoring $N$ to two prime numbers
- reduce factoring to order finding
- If we have
$$y^2=1\text{ mod }N\\
(y-1)(y+1)=0\text{ mod }N=k\cdot N$$
If $y\neq \pm1\text{ mod }N$, then
$$\text{gcd}(y+1,N)\\\text{gcd}(y-1,N)$$
must each be a proper divisor of $N$, i.e. prime factors.
- How can we find a non-trivial square root $y$?
1. choose a random $1< x\leq N-1$
2. run the order finding algorithm to find $r$, $x^r=1\text{ mod }N$
- If $r$ is even:
$$\begin{aligned}
x^r&=1\text{ mod }N\\
(x^{r/2}+1)(x^{r/2}-1)&=0\text{ mod }N=k\cdot N
\end{aligned}$$
then $y=x^{r/2}$ is a square root of $1$
and if $x^{r/2}\neq \pm 1$, then compute gcd
> success probability to find a "good" $x$?
> "good": order $r$ is even and $x^{r/2}\neq1$
> **Theorem:** If $N$ is divisible by $l$ distinct odd primes, then at least $$1-\frac{1}{2^{l-1}}$$ elements are "good".
> $l=2\Rightarrow 1/2$ probability to have "good" $x$
> $O(1)$ trials
- If $r$ is not even:
- **Complexity:**
- $O(1)$ for order finding
- overall: $O(L^3)$
- classical factoring: $\text{exp}(O(L^{1/3}))$
- <ins>exponential speedup</ins>

### RSA Algorithm
1. pick random two primes $p,q$, and $n=p\cdot q$
2. pick random public key by $e\in\phi(n)$, where $\phi(n)=(p-1)(q-1)$
3. choose private key $d$ such that $e\cdot d=1\text{ mod }\phi(n)$
4. public key: $(n,e)$
private key: $(n,d)$

- Encryption:
$E(m) = m^e\text{ mod }n$
- Decryption:
$D(c)=c^d\text{ mod }n=m^{e\cdot d}\text{ mod }n=m^{1\text{ mod }\phi(n)}\text{ mod }n= m \text{ mod }n$

> Shor's Algorithm allows us to factor efficiently on a quantum computer
> RSA public key scheme is broken, as soon as sufficiently **large** quantum computer exists.