\documentclass[11pt, letterpaper]{article}
\usepackage{amssymb,amsmath,amsthm,algorithmic}
\addtolength{\hoffset}{-0.45in}
\addtolength{\textwidth}{0.6in}
\addtolength{\voffset}{-0.35in}
\addtolength{\textheight}{0.5in}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{obs}{Observation}[section]
\newcommand{\gap}{\par\vspace{5pt}}
\newcommand{\Gap}{\par\vspace{10pt}}
\newcommand{\tab}{\par\hspace{5pt}}
\newcommand{\Tab}{\par\hspace{10pt}}
\newcommand{\TAB}{\par\hspace{20pt}}
\begin{document}
\bibliographystyle{plain}
\title{Quantum Computing Review}
\author{Amir Hossein Jabbari}
\maketitle
\section{Bits and Qubits}
Consider an electron in a hydrogen atom;
\begin{itemize}
\item in a {\em classical system}, this electron is either in it's normal orbit $1S^1$ (ground = 0), or in the exited position in the next orbit $2S^1$(exited =1).
\item in a {\em quantum mechanical system}, it is not known in which state the electron is. In fact the electron is in a linear superposition of the two states, and is called a qubit\cite{ekert-basic}.
\[
\begin{array}{ll}
|\psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle & \mbox {$\alpha , \beta \in C$ and $\alpha^2+\beta^2=1$}
\end{array}
\]
To know the electron's state, measurement in the $\{|0\rangle,|1\rangle\}$ is needed. Where measurement yields to $|0\rangle$ with the probability $\alpha^2$ , and $|1\rangle$ with the probability $\beta^2$. Moreover, measurement process will alter the state of the qubit. The new state is exactly the outcome of the measurement. That means, no more information about $\alpha$ and $\beta$ could be collected by repeating the measurement\cite{barenco96quantum}.
\end{itemize}
\section{Quantum Teleportation \cite{Vazirani}}
Alice wants to send $\chi = \left( \begin{array}{c} \alpha \\ \beta \end{array} \right)$ in a public channel:
\begin{enumerate}
\item Alice applies {\em Controlled-Not}\footnote{Controlled-Not is unitary operation that takes two qubits, and uses the first as control and the second as target. If the first is 0, do nothing, If the first is 1, then NOT the second.}\cite{barenco95elementary} operation on her two qubits.
\[\chi(C-NOT)=(\alpha | 0 \rangle + \beta |1 \rangle)(|00\rangle +|11\rangle)=\alpha|000\rangle + \alpha|011\rangle + \beta|110\rangle + \beta|101\rangle \]
\item Alice applies {\em Hadamard Transformation}\footnote{Hadamard Transformation:\[\begin{array}{ll}|0\rangle\longrightarrow \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \\ |1\rangle\longrightarrow \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\end{array}\]}\cite{barenco95elementary} on first qubit.
\[\chi(C-NOT)(H)= \frac{1}{\sqrt{2}}(\alpha|000\rangle +\alpha|100\rangle + \alpha|011\rangle +\alpha|111\rangle + \beta|010\rangle - \beta|110\rangle + \beta|001\rangle - \beta|101\rangle)\]
\item Alice can rewrite the first two bits in the Bell basis:
\[\begin{array}{ll}
(|00\rangle+|11\rangle)(\alpha|0\rangle +\beta|1\rangle)+\\
(|00\rangle-|11\rangle)(\alpha|0\rangle +\beta|1\rangle)+\\
(|01\rangle+|10\rangle)(\alpha|0\rangle-\beta|1\rangle)+\\
(|01\rangle-|10\rangle)(-\alpha|0\rangle+\beta|1\rangle)
\end{array}\]
\item Alice sends Bob the information about which Bell pair she has used.
\item Bob performs a correct rotation resulting in $(\alpha|0\rangle + \beta|1\rangle)$.
\end{enumerate}
\section{Quantum Physics and Church-Turing Machine}
\subsection{Classic Church Turing machine}
{\em Turing Machine} could be imagined as a machine with two parts:
\begin{enumerate}
\item A {\em tape} with infinite length in either side.
\item A {\em Head} which can move back and forth over the tape. It can also read, write and delete the contents of the tape.
\end{enumerate}
Here is the working instruction of {\em the machine}:
\begin{enumerate}
\item The tape has been partitioned. Each partition can hold either a 1 or a 0.
\item in each step the head could do one of the following:
\begin{enumerate}
\item halt.
\item move one partition to left.
\item move one partition to right.
\item delete the content of a partition and write over it.
\end{enumerate}
\end{enumerate}
A program is a set of instructions. Whenever no instruction is applied, {\em the Turing machine} halts.
As an Example, below a {\em Turing machine} with instruction to compute the {\em parity function} is presented:
\[ f_{(n)} = \left\{\begin{array}{ll}
1 &\mbox{if $n$ is odd}\\
0 &\mbox{otherwise}
\end{array}
\right. \]
The set of instructions for this function is:
\[ \begin{tabular}{|c|c||c|c|} \hline
{\em Curr. State}&{\em curr.Value}&{\em next State}&{next Value} \\ \hline
1 & 1 & 0 & 2 \\ \hline
2 & 0 & R & 3 \\ \hline
3 & 0 & 1 & 5 \\ \hline
3 & 1 & 0 & 4 \\ \hline
4 & 0 & R & 1 \\ \hline
\end{tabular}\]
The above instruction means:
\begin{enumerate}
\item If the program is at state 1 and scanning 1, then write 0 and go to state 2.
\item If the program is at state 2 and scanning 0, then head moves one partition to right and goes to state 3.
\item If the program is at state 3 and scanning 0, then write 1 and goes to state 5.
\item If the program is at state 3 and scanning 1, then write 0 and goes to state 4.
\item If the program is at state 4 and scanning 0, then head moves one partition to right and goes to state 1.
\end{enumerate}
Now lets try $f_{(2)}$ on the {\em Turing machine}:
$2 = 10_{(binary)}$
Starting with State 1 and reading first bit from left to right:
\begin{enumerate}
\item At state 1 and scanning 1, therefore write 0 and go to state 2\footnote{The bar over 0 represents the position of the head.}.
\={0}0
\item At state 2 and scanning 0, therefore the head moves one partition to right and the program goes to state 3.
0\={0}
\item At state 3 and scanning 0, therefore head writes 1 and goes to state 5.
0\={1}
\item At state 5 and scanning 1.
\end{enumerate}
The output of the machine is:
$f_{(2)} = 1$
\subsection{Church-Turing Theses and Quantum Computing}
The model described above is a classic Turing-machine, in every state it is known that what the head of the machine will read. {\em Probabilistic Turing Machine} works the same way, except in every state the head either reads 1 or 0, with some probability\cite{deutsch85quantum}.
\theorem The Modern Church-Turing theorem states that:
{\em Any reasonable model of computation can be efficiently simulated by a probabilistic Turing machine.}
However, as Feynman pointed out, it appears that the evolution of quantum systems cannot be efficiently simulated with a classical Turing machine,. Not even with a probabilistic one, since computational trajectories in a probabilistic Turing machine cannot interfere with each other(as is possible in a quantum computer).
\bibliography{quantComp}
\end{document}