\documentclass[12pt]{article}
%% \documentstyle[12pt,eclepsf]{article}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{rsfs}

\textheight 230mm
\topmargin 5mm
\textwidth 160mm
\oddsidemargin -2mm

\pagestyle{myheadings}
\markright{(Introduction to Quantum Computation)}

\newtheorem{formula}{Rule}
\newtheorem{example}{Example}
\newtheorem{excersize}{Excersize}
\newtheorem{algorithm}{Algorithm}
\newtheorem{axiom}{Axiom}


\begin{document}
\thispagestyle{empty}

\title{{\bf Introduction to Quantum Computation}}
\author{Akira Imada \\
Brest State Technical University, Belarus \\
        \hspace*{1in}\\
        \hspace*{1in}\\
        (last modified on)}
\maketitle


\section{Basic Concept for Quantum Computation}
In general, a Hilbert space of wave functions.
For quantum-C, in particular,
{\it finite dimensional complex vector space with an inner product
that are spanned by abstract wave function such as $|\to \rangle$}
will be sufficent. (Rieffel, 2000)\\


\noindent
Rieffel (2000) introduced an example of two {\it basis vector}
$| \uparrow \rangle$ and $| \to \rangle$
which are both {\it state vectors}.
Then wrote {\it ``When we measure state
the state $\psi = a | \uparrow \rangle + b | \to \rangle$ is measured as
$| \uparrow \rangle $ with the probability $\| a \|^2$ and
$| \to \rangle $ with the probability $\| b \|^2$.} \\


\noindent
Then what means by ``spanned?''
Ambainis (2003) uses this word as
\begin{quote}
{\it Let $\mathcal{H}$ be the subspace spanned by states $|\psi_i\rangle$.}
\end{quote}
or 
\begin{quote}
{\it Consider Hilbert space spanned by 
$ | x \rangle | i \rangle $ 
where 
$ x \in \{0,1\}^n$ 
corresponds to a vertex of hypercube and 
$i \in \{1, \cdots, n \} $ 
corresponds to an edge.}
\end{quote}

\noindent
As for Hamiltonian
\begin{quote}
One can define walk on the line on the set of states $|n\rangle$,
$n \in Z$. 
To do that, we take Hamiltonian
$\mathcal{H}$ 
defined by 
$\mathcal{H} |n \rangle = - | n-1 \rangle +2 | n \rangle - | n+1 \rangle$ 
Running quantum walk for time $t$ is just applying the transformation $U^{iHt}$
\end{quote}

\bigskip
\noindent
{\bf Ket Notation}\\
Quantum state spaces and transformations acting on them can be descriged 
in terms of vectors and matices or {\it bra/ket} notation.
Kets like $|x \rangle$ denote column vectors and typically quantum states  (Rieffel, 2000).\\

\noindent
{\bf Qubit}\\
Qubit is a column vector in a two dimensional complex vector space 
where a paticular basis, e.g., $|0 \rangle$  and $| 1 \rangle$
where $|0 \rangle$  and $| 1 \rangle$  correspond to 0 and 1 in classical comuter. \\


\noindent
However qubits is a superposition of $|0 \rangle$  and $| 1 \rangle$
--- $a |0 \rangle + b | 1 \rangle$.
That is, 
the  probility  of measurment being $|0 \rangle$ is $\|a\|^2$ 
and $| 1 \rangle$ being $\|b\|^2$  (Rieffel, 2000).\\


\noindent
{\bf Example of state}\\
The position on the line $| x \rangle$, 
and joint state of a particle at posiion x with a coin in state
$| L \rangle$, 
$| L, x \rangle$  (Rieffel, 2000).\\





\noindent
J. Kempe (2003) wrote
{\it "Imagine a particle on a line whose position is described by a wave-packet 
$| \psi_{x_0} \rangle$ 
localized around a position $x_0$,
i.e. the function 
$\langle x | \psi_{x_0} \rangle$ 
corresponds to a wave-packet
centered around $x_0$.} \\

\noindent
This make us a clear image.
A particle with a state of its polarity, an electoron with a state of its spin ...
In the case of randome walk
a particle in a certain position in an $n$-dimensional lattice whose state is 0 or 1.



\subsection{Random Walk}
\noindent
Now let $P$ be the momentum operator.
The translation of the particle, corresponding to a step
of length $l$ can be represented by the unitary operator
$U_l = \exp (-iPl/\hbar)$ so that 
$U_l | \psi_{x_0} \rangle U_l | \psi_{x_0-l} \rangle$ (Kempe, 2003). \\

\noindent
Ambainis (2003) further spcialized the situation.
{\it We consider the state space consisting of states
$| n,0 \rangle$ and $| n,1 \rangle$.
While classical computer uses a single binary bit.
The counter part of {\it bit} of quantum computer 
is {\it qubit} which is a unit vector in a complex Hilbert space $C^2$. \\

\noindent
Now that we can guess what Ambainis (2003) denote 
$| n, 0 \rangle$ and  $| n, 1 \rangle$ in the context of 
random walk in $n$-dimensional hypercube, as
\begin{center}
$| {\mbox {\small a vertex in the hypercube, wave function of a state}} \rangle$.
\end{center}

\end{document}

[6] R. P. Feynman and A. R. Hibbs. Quantum mechanics and
path integrals. International series in pure and applied
physics. McGraw-Hill, New York, 1965.





%% ===

\subsubsection*{Hilbert Space}
Hilbert Space is, to simply put, an abstract vector space
in which 
distances and angles can be defiened by inner product. 
Hilbert space is a generalization or extenxion of Euclidean space 
in which {\it points} is no more Cartesian co-ordinate like $(x_1, x_2, \cdots)$
but more abstract ones such as functions. All what is necessary is those points
maintan the following {\it axioms.}

\begin{axiom}[Vector Space] 
We refer a space $V$ as Vector Space when 
(i) for all points $\mbox {\bf a}, {\mbox {\bf b}} \in V$,
an operation $\mbox {\bf a} + \mbox {\bf b} \in V$, and (ii) for any complex number $c$
and any $\mbox {\bf a} \in V$, an operation $t\mbox {\bf a} \in V$ are difined and 
when the followings hold.
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[$1^{\circ}$] ${\mbox{\bf a}} + {\mbox{\bf b}} = {\mbox{\bf b}} + {\mbox{\bf a}}$
\item[$2^{\circ}$] $({\mbox{\bf a}} + {\mbox{\bf b}}) + {\mbox{\bf c}}
                   = {\mbox{\bf a}} + ({\mbox{\bf b}} + {\mbox{\bf c}})$
\item[$3^{\circ}$] ${\mbox {\bf x}} \in V$ always exists which fulfills 
                   ${\mbox {\bf a}} + {\mbox {\bf x}} = {\mbox {\bf b}}$ for 
                   $\forall {\mbox {\bf a}}, {\mbox {\bf b}} \in V.$
\item[$4^{\circ}$] $t({\mbox {\bf a}} + {\mbox {\bf b}}) 
                    = t {\mbox {\bf a}} + t {\mbox {\bf b}}$
\item[$5^{\circ}$] $(s + t) \mbox {\bf a} = s\mbox {\bf a} + t \mbox {\bf a}$
\item[$6^{\circ}$] $(st)\mbox {\bf a} = s(t\mbox {\bf a})$
\item[$7^{\circ}$] $e$ exists such that $e \mbox {\bf a} = \mbox {\bf a}$

\end{itemize}
\end{axiom}






\noindent
We now assume $|0\rangle$ is $(1,0)^T$ and $|1\rangle$ is $(0,1)^T$, that is, two orthonormal basis.

Quantum computer maniputates registers each of which has $n$ qubits.
if each qbit has an orthonormal basis $|0\rangle$ and $|1\rangle$
then n qubit system has a basis
expressed by the tensor product




\section{Search by Quantum Random Walk}
\noindent
Since Feynman proposed a possibility to use quantum mechanics in 1982 \cite{feyn-1}\cite{feyn-2},
the topic has attracted mainly physicists' and especially recently computer scientists'
interest and curiosity.\\

\noindent
In 1997, Grover \cite{grov} reported an algorithm exploiting  concepts in quantum mechanics 
to search for  a needle in a haystack more efficiently than a traditional computation.
As previously mentioned, we don't know essentially more efficient algorithm
to search for a needle in a haystack than the one whose complexity is 
$O(N)$ where $N$ is the number of points in the whole search space.
For example, we can see the complexity is $O(N)$ as shown in Fig.~5
if we plot the data already shown in Fig.~2
as a function of number of points of the search space instead of the number of bits.\\


\noindent
Grover's proposed algorithm was proofed to be able to search for 
the needle with a complexity of $O(\sqrt{N})$
as shown in the fictitious graph in Fig.~6.
However, practical quantum computer hardware has never existed yet.
Up to now, all we have had are just a few toy implementation of 
quantum computers.\footnote{At the moment 
I wrote this paper, I found an article in New York Times which read
{\it ``D-Wave, a start-up company in Burnaby, British Columbia, demonstrated 
'the world's first commercial quantum computer' in February.''}
But many Physicists and Computer Scientists are still fishy about that. The head line was 
{\it ``A Giant Leap Forward in Computing? Maybe Not. 
If a 'practical quantum computer' had been built and demonstrated, 
it would be a wonderful thing.''} --- New York Times on 8th March 2007 by Jason Pontin.} 
Nevertheless, arguments regarding the possibility of quantum algorithms becomes more and more active these days.
Concerning the topic of this paper -- search for a needle -- see, for example,
Kempe's wonderful introductory overview of {\it quantum random walks.} The author wrote,
{\it "We will give a thorough introduction to the necessary terminology without overburdening the reader with unnecessary mathematics."}\\

\subsection{Notations -- A little intimidating though}
\noindent
While the state space of a quantum system, in general, 
is modeled by a Hilbert space of wave functions,
the finite quantum system we need for quantum computing, in particular,
is sufficient to be modeled on a Hilbert space of finite dimensional complex vector 
with an inner product that are spanned by abstract wave functions. \\

\noindent
Classical computer systems represent a single bit of information
deterministically: the value is either a logic 0 or a
logic 1. Quantum computer systems represent a single bit of
information as what they call a {\it qubit}, which is a unit vector in a complex
Hilbert space \cite{gree}. \\

\noindent
Here we use the {\it bra/ket} notation coined from {\it bracket}, 
which is introduced by Dirac \cite{dira}
The {\it ket} symbol is denoted by $\vert x \rangle$
and the corresponding {\it bra} is denoted by $< x \vert $.
The {\it ket} describes a quantum state and the corresponding {\it bra}
is its complex conjugate \cite{gree}.\\

\noindent
In computer science domains, the {\it ket} and {\it bra}
is a column  and row vector respectively. For example, the orthonormal basis 
$\{\vert0\rangle, \vert1\rangle\}$
can be expressed like $\{(1,0)^T, (0,1)^T\}$ by using this {\it ket}.
Any complex linear combination of two {\it kets} is also a {\it ket}. 
The inner product of two vectors is denoted by 
$ <x \vert y\rangle $.
Note that since $\vert 0\rangle$ and $\vert 1\rangle$ 
are orthonormal,
$ <0 \vert 1 \rangle =0 $.
On the other hand, 
$ \vert x\rangle<y \vert $
denotes the outer product of the vectors (See \cite{gree}).\\


\noindent
Then $n$ bit binary string in the traditional computation can be denoted
$\vert b_{n-1} b_{n-2} \cdots b_0\rangle $
where each $b_j$ is either 0 or 1.
Furthermore, we abbreviate this by using corresponding decimal number.
For example $\vert 12\rangle$  means $\vert 1100\rangle$  (See, e.g.,  \cite{spec}).

\subsection{Quantum Random Walk}
\noindent
Our needle search in a haystack is after all {\it searching the Boolean hypercube.}
The first algorithm of this type was proposed by Shenvi et al.~\cite{shen}.
Shenvi starts his argument
\begin{quote}
The discrete time random walk can be described by the repeated application of 
a unitary evolution operator $U$.
This operator acts on a Hilbert space $H^C \otimes H^S$ 
where $H^C$ is the Hilbert space associated with a quantum coin and
$H^S$ is the Hilbert space associated with the nodes of the graph
($\otimes$ is tensor products).
The operator$U$ can be written as 
\begin{displaymath}
U = S \cdot C
\end{displaymath}
where $S$ is a permutation matrix which performs a controlled shift based on 
the state of the quantum coin, and $C$ is
a unitary matrix which ``flips'' the quantum coin \cite{ahar}.
\end{quote}

\noindent
Ambainis \cite{amba} clearly summarizes the algorithm.
\begin{quote}
Let $V$ be the set of vertices and $E$ be the set of edges. 
We use basis states 
$\vert v, 3\rangle$ for $\forall v \in V$
and $e \in E$ 
such that the edge $e$ is incident to the vertex $v$. 
One step of quantum walk now consists of the following:
\end{quote}

\bigskip
\begin{algorithm}\hspace{1in}
\begin{itemize}
\item[(1)] For each $v$, perform a coin flip transformation $C_v$ on the states $\vert v, e\rangle$
\item[(2)] Perform shift $S$ defined as follows. If edge e has two vertices in its both ends,
$v$ and $v^{\prime}$, then 
$ S \vert v, e\rangle = \vert v^{\prime}, e\rangle$
and 
$ S \vert v^{\prime}, e\rangle = \vert v, e\rangle$.
\end{itemize}
\end{algorithm}

\bigskip
\noindent
Ambainis \cite{amba} continues:
\begin{quote}
As a coin flip $C_v$ Grover's diffusion $D_n$ is a good option, where
$D_n$ is $n \times n$ matrix in which all elements except for the diagonal ones are $2/m$, and  
diagonal elements are all $(-1 + 2/m)$.\\

\noindent
In the Boolean hypercube, we have $N = 2^n$ vertices $v_x$ indexed by $n$-bit strings. 
Two vertices $v_x$ and $v_y$ are connected by an edge if the corresponding strings $x$ and $y$ 
differ in exactly one place. 
The maximum distance between two vertices is $n = \log N.$ 
Thus, Grover's algorithm could search this graph in $O(\sqrt N \log N)$ steps. 
Shenvi et al.~\cite{shen} showed how to search it by quantum walk in $O(\sqrt N)$ steps. 
Consider now Hilbert space spanned by 
$\vert x \rangle \vert i \rangle$
where 
$\mbox{\bf x} \in \{0,1\}^n$
corresponds
to a vertex of hypercube and 
$i \in \{1, 2, \cdots, n\}$
corresponds to an edge.
\end{quote}

\noindent
Ambainis \cite{amba} summarizes the algorithm clearly as follows.

\bigskip
\begin{algorithm}\hspace{1in}
\begin{itemize}
\item[(1)] Generate the starting state
\begin{displaymath}
\frac{1}{\sqrt{2^n n}}\sum_{x,i} \vert x \rangle \vert i\rangle.
\end{displaymath}
\item[(2)] Perform $O(\sqrt N)$ steps with each step consisting of 
\begin{itemize}
\item[(i)]Apply $D_n$ to $\vert i \rangle$ register if the vertex $x$ is not the target. Otherwise
Apply $-I$ (identity matrix).
\item[(ii)] Apply shift $S$ defined by 
\begin{displaymath}
S: \vert x \rangle \vert i\rangle \hspace{.1in} \rightarrow \hspace{.1in} \vert x^i\rangle \vert i\rangle.
\end{displaymath}
\end{itemize}
If there is no target items, then the algorithm stays in the starting state.
If there is a single target vertex $v_x$, then, 
running this algorithm for $O(\sqrt N)$ steps and measuring the state gives $\vert x, i\rangle$ 
for the target $x$ and some $i$ with a high probability.
\end{itemize}
\end{algorithm}


\bigskip
\noindent
Let me stop now since we are running out of space and time.
Hoping to have a hot and useful discussion on this topic in the session at Elk.

\bigskip
\begin{thebibliography}{99}
\bibitem{hint}
G. E. Hinton, and S. J. Nowlan 
``How Learning Can Guide Evolution.''
Complex Systems, Vol. 1, 1987, pp. 495--502 

\bibitem{mill-1}
R. Mills, and R. A. Watson
``Genetic assimilation and canalization in the Baldwin effect.''
In Proceedings of the European Conference on Artificial Intelligence, 2005, pp. 353-362.

\bibitem{mill-2}
R. Mills, and R. A. Watson
"On Crossing fitness Valleys with the Baldwin Effect."
In Proceedings of Artificial Life X, 2006, pp. 493--499.

\bibitem{coll-1}
M. Collins ``
Counting Solutions in Reduced Boolean Parity.''
In Workshop Proceedings of the Conference on Genetic and Evolutionary Computation, 
2004, pp. 26--30.

\bibitem{yu}
T. Yu, and J. Miller
``Finding Needles in Haystacks Is Not Hard with Neutrality.''
In Proceedings of the European Conference on Genetic Programming,
LNCS 2278, Springer, 2002, pp. 13--25.

\bibitem{mill}
J. F. Miller, and P. Thomson ``Cartesian genetic programming.''
In Proceedings of the European Conference on Genetic Programming,
LNCS 1802, Springer, 2000, pp. 121--132.

\bibitem{coll-2}
M. Collins 
``Finding Needles in Haystacks is Harder with Neutrality.''
In Proceedings of the 2005 Conference on Genetic and Evolutionary Computation, 2005
pp. 1613 -- 1618.

\bibitem{feyn-1}
R. Feynman
``Simulating physics with computers. International Journal of Theoretical.''
Physics Vol. 21, 1982, pp. 467--488.

\bibitem{feyn-2}
R. Feynman
``Quantum mechanical computers.'' 
Foundations of Physics, Vol. 16, 1986, pp. 507--531.

\bibitem{grov}
L. K. Grover
``Quantum Mechanics helps in searching for a needle in a haystack.''
Physical Review Letter, Vol. 79, 1997, pp. 325--328. 

\bibitem{gree}
G. W. Greenwood
``Finding Solutions to NP Problems: Philosophical Differences Between Quantum and Evolutionary Search Algorithms,'' 
In Proceedings of the Congress on Evolutionary Computation,
2001, pp. 815 - 822.


\bibitem{spec}
L. Spector,  H. Barnum, H. J. Bernstein, and N. Swamy
"Finding a Better-than-Classical Quantum AND/OR Algorithm using Genetic Programming"
In Proceedings, of the Congress on Evolutionary computation, 1999, pp. 2239--2246.


\bibitem{kemp}
J. Kempe ``Quantum Random Walks -- An Introductory Overview.'' 
Contemporary Physics, Vol. 44 Issue 4 (also preprint quant-ph/0303081), 2003, pp. 307-327.  

\bibitem{dira}
P. Dirac
``The Principles of Quantum Mechanics.'' 
Oxford University Press, 4th edition, 1958.

\bibitem{shen}
N. Shenvi, J. Kempe, and B. Whaley
"A Quantum Random Walk Search Algorithm"
Physical Review A, Vol 67 (also preprint quant-ph/0210064), 2003.

\bibitem{ahar}
D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani, 
``Quantum Walks On Graphs.''
In Proceedings of ACM Symposium on Theory of Computing, ACM
(also preprint quant-ph/0012090), 2001, pp. 50--59.

\bibitem{amba}
A. Ambainis
``Quantum Walks and Their Algorithmic Applications ``
International Journal of Quantum Information,
Vol 1 (also preprint quant-ph/0403120), 2003, pp. 507--518.



\end{thebibliography} 
