\documentclass[a4paper,onesided,12pt]{report}
\usepackage{styles/598_report}
\usepackage[utf8x]{inputenc} % To use Unicode (e.g. Turkish) characters
\renewcommand{\labelenumi}{(\roman{enumi})}
\usepackage{amsmath, amsthm, amssymb,nccmath}
\usepackage{fixltx2e}
\usepackage[euler]{textgreek}
 % Some extra symbols
\usepackage[bottom]{footmisc}
\usepackage{cite}
\usepackage{graphicx}
\usepackage{longtable}
\graphicspath{{figures/}} % Graphics will be here

\usepackage{multirow}
\usepackage{subfigure}
\usepackage{algorithm}
\usepackage{algorithmic}

\begin{document}

\setlength{\abovedisplayskip}{3pt}
\setlength{\belowdisplayskip}{3pt}
\newcommand\tab[1][1cm]{\hspace*{#1}}

\chapter*{CMPE 598 - Lecture Notes}
\large
\vspace*{-10mm}
\begin{center}
Mert Kalaylıoğlu\\
April 24, 2018
\end{center}
\vspace*{-2mm}
\tab\LARGE{\textbf{1. Shor's Algorithm for Factorization}}\\
\normalsize 
\tab Given a positive integer, find its factors.\\
\tab There exists a fast classical algorithm for detecting whether the number is prime. If so, problem solved.\\
\tab There exists a fast classical algorithm for detecting whether the number is a power (i.e. of the form $a^b \ for \ b > 1$).\\
\tab $x = a^b$\\
\tab $log x = b*log a$ so b cannot be bigger than logx.\\
\tab \textbf{Binary Search:} If you can find a factor, you can find all other factors as well using the same method repeatedly.\\
\\
\tab Assume you are given a number pq where p and q are primes.\\
\tab We want to factor a large integer N.
\vspace*{-7mm}
\begin{itemize}
\item FACTORING is reduced to finding \textbf{a non-trivial square root} of 1 modulo N.\\
$y^2 \equiv 1 \ (mod N) \ (y \in {1, 2, ..., N-1})$\\
if N = 15\\
\textbf{trivial square roots of 1 (mod 15)}\\
$1^2  \equiv 1 \ (mod 15)$ not exciting\\
$(-1)^2  \equiv 1 \ (mod 15)$ not exciting\\
$14^2  \equiv 1 \ (mod 15)$ not exciting\\
$-1 \equiv 14 \ (mod 15)$\\
\textbf{non-trivial square root of 1 (mod 15)}\\
$4^2 \equiv 1 \ (mod 15)$\\

If y is a non-trivial square root of 1 mod N,\\
Then N divides $y^2-1 = (y+1)(y-1)$, but N does \textbf{not} divide neither $y-1$ nor $y+1$. So this means that $gcd(y-1, N) > 1$ because if $y-1$ and N were relatively prime, then since N divides $(y-1)(y+1)$, it would have to divide $(y+1)$.\\

\item Finding such a root is reduced to computing \textbf{the order of a random integer modulo N}.\\
Pick a random number X (mod N).\\
The order of X (mod N) is the smallest number r such that $X^r \equiv 1 \ (mod N)$.\\
\textbf{Example:} The order of 2 mod 15 is 4. $2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 1, 2^5 = 2, 2^6 = 4, 2^7 = 8, 2^8 = 1,...$
\item The order of an integer is precisely the period of a particular periodic superposition.\\
"Period = Order"

\item And, periods of superpositions can be found by the quantum FFT.
\end{itemize}
\tab Classical FFT's input is an M-dimensional, complex valued vector $\alpha$ (where M is a power of 2, say $2^m$) and its output is an M-dimensional, complex valued vector  $\beta$;
\begin{equation}
\begin{bmatrix}
    \beta_{0}      \\
    \beta_{1}      \\
    \vdots   \\
    \beta_{M-1}  
\end{bmatrix}
= \frac{1}{\sqrt{M}}
\begin{bmatrix}
    1 & 1 & 1 & \dots  & 1 \\
    1 & W & W^2 & \dots  & W^{M-1} \\
    1 & W^2 & W^4 & \dots  & W^{2(M-1)} \\
    1 & W^3 & W^6 & \dots  & W^{3(M-1)} \\
    \vdots & \vdots & \vdots & \ddots & \vdots \\
    1 & W^{(M-1)} & W^{2(M-1)} & \dots  & W^{(M-1)(M-1)}
\end{bmatrix}
\begin{bmatrix}
    \alpha_{0}      \\
    \alpha_{1}      \\
    \vdots   \\
    \alpha_{M-1}  
\end{bmatrix}
\end{equation}
\tab where W is a complex $M^{th}$ root of unity.\\
\tab FFT runs in $O(M*logM)$ steps.\\
\tab \textbf{Input:} A superposition of m = log M qubits $|\alpha\hspace{-0.3em}> = \sum_{j=0}^{M-1}\alpha_j\ |j\hspace{-0.3em}>$.
\begin{equation}
\begin{bmatrix}
    \alpha_{0}      \\
    \alpha_{1}      \\
    \vdots   \\
    \alpha_{M-1}  
\end{bmatrix}
= \alpha_{0}
\begin{bmatrix}
    1      \\
    0      \\
    0      \\
    \vdots   \\
    0  
\end{bmatrix}
+ \alpha_{1}
\begin{bmatrix}
    0      \\
    1      \\
    0      \\
    \vdots   \\
    0  
\end{bmatrix}
+ \alpha_{2}
\begin{bmatrix}
    0      \\
    0      \\
    1      \\
    \vdots   \\
    0  
\end{bmatrix}
+ ... + \alpha_{M-1}
\begin{bmatrix}
    0      \\
    0      \\
    0      \\
    \vdots   \\
    1  
\end{bmatrix}
\end{equation}
\tab \textbf{Method:} We'll use $O(m^2)$ quantum operations to obtain the superposition. \\
$|\beta\hspace{-0.3em}> = \sum_{j=0}^{M-1}\beta_j\ |j\hspace{-0.3em}>$\\
\tab \textbf{Output:} A random m-bit number j (i.e. $0 \leq j \leq M-1$), from the probability distribution $Pr[j] = |\beta_j|^2$.\\
\tab Suppose the input to quantum Fourier sampling is periodic with period k, for some k that divides M. Then the output will be a multiple of $\frac{M}{k}$, and it is equally likely to be any of the k multiples of $\frac{M}{k}$.
\begin{equation}
| \alpha\hspace{-0.3em}> \ =
\begin{pmatrix}
    \alpha_{0}      \\
    \alpha_{1}      \\
    \vdots   \\
    \alpha_{M-1}  
\end{pmatrix}
\end{equation} 
\tab $| \alpha\hspace{-0.3em}>$ is such that $\alpha_j = \alpha_i$ whenever  i = j mod k where k is a particular integer that divides M. So there are $\frac{M}{k}$ repetitions of same sequence ($\alpha_0, \alpha_1, ..., \alpha_{k-1}$) of length k.\\
\tab \textbf{And suppose exactly one of these k numbers is non-zero}, say $\alpha_j$.\\
\tab Suppose the vector $|\alpha\hspace{-0.3em}> = (\alpha_0, \alpha_1, ..., \alpha_{M-1})^T$ is periodic with period k with no offset (that is, the non-zero terms are $\alpha_0, \alpha_k, \alpha_{2k}, ...$). Thus $|\alpha\hspace{-0.3em}> = \sum_{j=0}^{\frac{M}{k}-1} \sqrt{\frac{k}{M}} \ |jk\hspace{-0.3em}>$.

\textbf{Claim:}
\vspace*{-6mm}
\begin{equation}
|\beta\hspace{-0.3em}> = \frac{1}{\sqrt{k}}\sum_{j=0}^{k-1}|\frac{jM}{k}\hspace{-0.3em}>
\end{equation}
\tab In the input vector, the coefficient of $\alpha_l$ is $\sqrt{\frac{k}{M}}$ if $k$ divides $l$, and zero otherwise. The $j^{th}$ coefficient $|\beta\hspace{-0.3em}>$ is
\begin{equation}
\beta_j = \frac{1}{\sqrt{M}}\sum_{l=0}^{M-1}w^{jl}\alpha_l =  \frac{\sqrt{k}}{M}\sum_{i=0}^{\frac{M}{k}-1}w^{jik}
\end{equation}
\tab So this sum is the geometric series $1 + w^{jk} + w^{2jk} + ...$ containing $\frac{M}{k}$ terms and with ratio $w^{jk}$. There are two cases. If the ratio is exactly 1, which happens if $jk \equiv 0 \ mod \ M$, then the sum of the series is just the number of terms. If the ratio isn't 1, apply the usual formula for geometric series to find that the sum is
\begin{equation}
\frac{1-w^{jk(\frac{M}{k})}}{1-w^{jk}} = \frac{1-w^{jM}}{1-w^{jk}} = 0
\end{equation}
\tab So $\beta_j = \frac{1}{\sqrt{k}}$ is M divides jk, and is zero otherwise.
Also works (with little modification) for the case where the offset is non-zero.\\
\tab Suppose s independent samples are drawn uniformly from $\{0, \frac{M}{k}, \frac{2M}{k}, ..., \frac{(k-1)M}{k}\}$.
Then, with probability at least $1 - \frac{k}{2^s}$, the greatest common divisor of these samples is $\frac{M}{k}$.\\
\tab \textbf{Proof:} The only way this can fail is if all samples are multiples of $j\frac{M}{k}$, for some $j > 1$. So, fix any integer $j \geq 2$. The chance that a particular sample is a multiple of $j\frac{M}{k}$ is at most $\frac{1}{j} \leq \frac{1}{2}$, so the chance that \textbf{all samples} are multiples of $j\frac{M}{k}$ is at most $\frac{1}{2^s}$. The probability that this bad thing will happen for some $j \leq k$ is at most $k\frac{1}{2^s}$, since these are k candidates for the number j.\\
\tab How does the classical FFT work?\\
\tab "Divide \& Conquer"\\
\tab from input $(\alpha_0, \alpha_1, ..., \alpha_{M-1})^T$ to output $(\beta_0, \beta_1, ..., \beta_{M-1})^T$
\begin{figure}[H]
\begin{center}
\includegraphics[width=0.8\columnwidth]{res1.png}
\end{center}
\end{figure}
\vspace*{-16mm}
$w^{\frac{M}{2}} = -1.$\\
\tab In the quantum version, the input is now encoded in the $2^m$ amplitudes of $m = logM$ qubits. So the decomposition of the inputs to evens and odds is determined by the least significant qubit. We will design a quantum circuit (subroutine) $QFT_M$. $QFT_{\frac{M}{2}}$ will be applied to the remaining m-1 qubits.
\begin{figure}[H]
\begin{center}
\includegraphics[width=0.65\columnwidth]{res2.png}
\end{center}
\end{figure}
\vspace*{-16mm}
\begin{equation}
H \ =
\begin{pmatrix}
    \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}     \\
    \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}     
\end{pmatrix}
\end{equation} 
\vspace*{-10mm}
\begin{equation}
Other \ lines \ =
\begin{pmatrix}
    1 & 0    \\
    0 & 1     
\end{pmatrix}
\end{equation} 
\begin{equation}
A =
\begin{pmatrix}
    1 & 0 & 0 & \dots & 0     \\
    0 & 1 & 0 & \dots & 0     \\
    0 & 0 & 1 & \dots & 0     \\
    \vdots   \\
    0 & 0 & 0 & \dots & 1     
\end{pmatrix}
\otimes
\begin{pmatrix}
    \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}     \\
    \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}     
\end{pmatrix}
=
\begin{pmatrix}
    \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}   & 0 & 0 & \dots  & 0 & 0\\
    \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}  & 0 & 0 & \dots  & 0 & 0\\ 
    0 & 0  & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}  & \dots  & 0 & 0   \\
     0 & 0  & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & \dots  & 0 & 0  \\
    \vdots   \\
    0 & 0  &  0 & 0  & \dots   &\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}  \\
     0 & 0  &  0 & 0  & \dots   &\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} 
\end{pmatrix}
\end{equation} 
\tab 01100 0 $\rightarrow$ even\\
\tab 01100 1 $\rightarrow$ odd
\vspace*{-6mm}
\begin{equation}
\begin{pmatrix}
    \alpha_{y_0}: \text{even} \\
    \alpha_{y_1}: \text{odd}
\end{pmatrix}
\end{equation} 
\vspace*{-12mm}
\begin{equation}
A 
\begin{pmatrix}
    \alpha_{y_0} \\
    \alpha_{y_1}
\end{pmatrix}
=
\begin{pmatrix}
    \frac{\alpha_{y_0} + \alpha_{y_1}}{\sqrt{2}}\\
    \frac{\alpha_{y_0} - \alpha_{y_1}}{\sqrt{2}}
\end{pmatrix}
\end{equation} 
\tab For each j, an operation is done in the classical FFT on the $(\frac{M}{2}+ j)^{th}$ wire. If j is represented by the m-1 bits $j_1, j_2, ..., j_{m-1}$, then $w_j = \prod_{l=1}^{m-1}w^{2^{j_l}}$. Ex: m = 3, \\m - 1 = 2, $j_2j_1$.
\begin{figure}[H]
\begin{center}
\includegraphics[width=0.65\columnwidth]{res3.png}
\end{center}
\end{figure}
\vspace*{-16mm}
\begin{equation}
Gate \ with \ 2 \ qubits =
\begin{bmatrix}
    1 & 0 & 0 & 0 \\
    0 & 1 & 0 & 0 \\
    0 & 0 & 1 & 0 \\
    0 & 0 & 0 & W^{2^j}
\end{bmatrix}
\end{equation} 

\end{document}