\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{rsfs}

\usepackage{graphicx}
\usepackage{color}

\textheight 260mm
\topmargin 5mm
\textwidth 180mm
\oddsidemargin -7mm

\newtheorem{algorithm}{Algorithm}

\pagestyle{myheadings}
\markright{(CISIM'2007 -- at Elk, Poland)}
\thispagestyle{empty}

\begin{document}
\begin{huge}

%% the problem with this fancy name has attracted and is still attracting researchers.
%% we now try a bird's view of how 
%% from a biological model of evolution called baldwin effect to quantum computation

\clearpage  % (title) =========================================
\begin{center}
\color{blue}
{\bf Finding a Needle in a Haystack: \\ 
from  \\
Baldwin Effect \\ 
to \\
Quantum Computation}\\

\color{black}
\hspace*{1in}\\ 
\begin{Large}
Akira Imada  \\
\bigskip
Brest State Technical University, Belarus
\end{Large}
\end{center}

%% Here we try a bird's eye view of this topic ranging from a biological evolution
%% of Baldwin effect to quantum computation

%% This is a metaphor of how difficult the search is.
%% Again a metaphore but in fact if we have an efficient small metal detector or ]
%% even a strong magnet ...

\clearpage  % =========================================
\begin{figure}[bhtp]
\begin{center}
%%\includegraphics[width=8cm]{b19objects363.jpg}
%%\includegraphics[width=8.5cm]{usne6757.jpg}
%%\includegraphics[width=8.5cm]{ted-hay-24.3.jpg}
\includegraphics[width=8.5cm]{hay-1.eps}
\includegraphics[width=8.5cm]{hay-2.eps}
\end{center}
\end{figure}


%% interesting definition of word brilliance in a world wide web page
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Alora's proposition (2007)}\\
\color{black}

\begin{figure}[bhtp]
\begin{center}
  \includegraphics[width=1.5cm]{mozart.eps}
%%\includegraphics[width=1.5cm]{karajan-1.eps}
  \includegraphics[width=1.5cm]{karajan-2.eps}
\end{center}
\end{figure}

Brilliance = Ability to find a needle \\in a haystack.\\
\bigskip
{\LARGE
%% let me paraphrase what he said.
{\it ``Art is to create a rarely possible appreciation \\
somewhere in a  huge universe of our brain.''}
}
\end{center}

%% This makes me think that ...

\clearpage  % =========================================
\hfill {\large (Cont'd)}
\begin{center}   
(Artificial) {\it INTELLIGENCE} \\ can search, classify and recognize normal objects\\
while \\
only {\it BRILLIANCE} \\ 
can search for a needle in a hay. 
\end{center}


%% we have a long argued question in ... 
%% hopefully not as they concluded
%% much more simple form of literature ...
%% probably this is the simplest form of poem
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Could an endlessly typing monkey eventually create Shakespeare by chance?}\\

\color{black}
\hspace*{1in}\\
Hopefully not! \\

\hspace*{1in}\\
Then what about {\it haiku}? \\
%%$\Rightarrow$ 
%%{\LARGE 
Is there really a chance it would happen at all?
%% Is it  more likely it would happen?
%%might be more likely.
\end{center}

%% \clearpage % =========================================
%% \begin{figure}[bhtp]
%% \begin{center}
%% \includegraphics[width=3cm,height=9cm]{1269.jpg}
%% \end{center}
%% \end{figure}


%% this is one of the most populer ...
\clearpage % =========================================
\vspace*{0.5in}

\hspace*{1in} 
����������\\
\hspace*{2in} 
�������Ƃ�����\\
\hspace*{3in} �΂�����\\



%% It sounds like
\clearpage % =========================================
\vspace*{0.5in}
\hspace*{1in} 

\hspace*{1in} 
U-Gu-I-Su-No \\
\hspace*{2in} 
Ka-Sa-O-To-Shi-Ta-Ru \\
\hspace*{3in} Tsu-Ba-Ki-Ka-Na 



\clearpage  % =========================================
\begin{center} \color{blue}
{\bf How many possible different candidates}
\color{black}
\begin{displaymath}
76^{17} \approx 10^{31}
\end{displaymath}

\bigskip
{\LARGE It's still like a search for {\it a-needle-in-a-haystack}\\ 
for a monkey to create a meaningful one.}
\end{center}


%% by the way it's not difficult. Why don't we use magnet or metal detector?

%% start with haiku tategaki 
%% artist is a needle finder

%% Let's name a few
%% I think everyone has some familiar ones
%% All are from the title when I googled with key-words of needle-in-a-hay and pdf
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Computational analogue of a-needle-in-a-haystack}\\
\bigskip
{\LARGE
\color{red}
A specific rare cases 
\color{black}
in a  huge database;\\
\color{red}
A real necessary information 
\color{black}
from world-wide-web; \\
\color{red}
Oil spills in the ocean  
\color{black}
from satellite image; \\
\color{red}
A cause of failures  
\color{black}
in diagnosing a huge code; \\   %% from software-engineering
\color{red}
A collision 
\color{black}
of a hash function; \\  
%% cryptography \\
etc...... \\
$\Downarrow$ \\
Such searches are very important for us.
}
\end{center}


\clearpage  % =========================================
%% I became interested in this topic for the first time when ...
%% My first encounter to this prolble is when ...
\begin{center} \color{blue}
%%{\bf First motivated}
{\bf Associative memory by Spiking neurons}


\color{black}
\bigskip
Fitness landscape \\
$\Downarrow$ \\
Hopfield network ... many peaks in a rugged land \\
vs.\\
Spiking neurons ... like a flat island in a huge lake
\end{center}

%% ... when they are to be evolved.
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf A standard initial distribution \\of fitness values}\\
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=2.2cm]{histgram-bga-25n-2p.eps}
\includegraphics[width=14cm,height=2.2cm]{histgram-bga-25n-8p.eps}
\includegraphics[width=14cm,height=2.2cm]{histgram-bga-25n-16p.eps}
\end{center}
\end{figure}


%% On the other hand ...
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A-tiny-flat-island-in-a-huge-lake}\\

\color{black}
\bigskip
{\LARGE
A fictitious 1-D fitness-landscape \\ of Hebbian-learning by spiking neurons
}
\color{black}
\bigskip
\begin{figure}[bhtp]
\begin{center}
%% \includegraphics[width=9cm,height=3cm]{hebbian-ls.eps}   %% maybe delete this
\includegraphics[width=15cm,height=3cm]{spike-ls.eps}
\end{center}
\end{figure}

\end{center}
%% This is a topic I talked about a couple of years ago in this conference.


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Then, fitness distribution is ...}
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=5.0cm]{histgram-needle.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center}
\vspace*{1in}
{\bf It's not possible to hillclimb\\ if not a hill to climb!}
\caption{Assuming only one configulation of  $n$-bit binary strings being a needle,
the number of random trials needed until the needle was found is plotted against $n$.
result is an average during 100 runs.}
\end{center}
}

%% Yet another example is ...
%% two seemed to be quite easy while the other two seemed ...
%% winner's result in the competition held in 1999 for  detecting intrusion in the dataset

\clearpage  % =========================================
\begin{center}
\color{blue}
{\bf Network intrusion data \\ among normal transaction data}

\color{black}
\bigskip
E.g. $\Rightarrow$ 4 attack types in KDD-cup-99 dataset\\
\hspace*{1in}\\
The winner's result 
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=15cm,height=2.5cm]{table-1.eps}
\end{center}
\end{figure}


%% We also have a report in which 9 machine learning techniques are applied to these attack data

\clearpage  % =========================================
\begin{center}
\color{blue}
{\bf Detection rate by Sabhnani et al.~(2003)}
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=18cm,height=8.5cm]{table-2.eps}
\end{center}
\end{figure}

%% \color{black}
%% {\it
%% \begin{table}[h]
%% \begin{center}
%% \begin{tabular}{l c c c c} \hline
%% \hspace*{.1in}                     & Probe  & DoS  & U2R  &  R2L \\ \hline
%% Multi-layer Perceptron             & 88.7   & 97.2 & 13.2 & 5.6  \\
%% Gaussian Classifier                & 90.2   & 82.4 & 22.8 & 9.6  \\
%% $K$-mean Clustering                & 87.6   & 97.3 & 29.8 & 6.4  \\
%% Nearest Cluster Algorithm          & 88.8   & 97.1 &  2.2 & 3.4  \\
%% Radial Basis Function              & 93.2   & 73.0 &  6.1 & 5.9  \\
%% Leader Algorithm                   & 83.8   & 97.2 &  6.6 & 1.0  \\
%% Hypersphere Algorithm              & 84.8   & 97.2 &  8.3 & 1.0  \\
%% Fuzzy Art Map                      & 77.2   & 97.0 &  6.1 & 3.7  \\
%% C4.5 Decision Tree                 & 80.8   & 97.0 &  1.8 & 4.6  \\ \hline
%% \end{tabular} 
%% \end{center}
%% \end{table}
%% }

\clearpage  % =========================================
\begin{center} \color{blue}
%% {\bf Some Intrusions \\
%% are immune to be detected.} \\ 

 {\bf Some Intrusions  are immune to \\ any detectors} \\ 

\bigskip
\color{black}
{\LARGE
Probably because they are like needles in a huge hay.\\
\hspace*{1in}\\
(Joshi et al. 2001) \\
{\it ``If a class is very rare, e.g., 0.5\%,\\
prediction of non-target will be 99.5\%.''}} \\
{\Large 
\bigskip
(Nevertheless, we have still many innocent optimistic reports of success.)}
\end{center}
%% So, we have to be careful



\clearpage   % =========================================
\color{blue}
\begin{center} \color{blue}
%%{\bf Let's study the other 4 cases \\ more in detail!}
{\bf We now look at the other 4 cases \\ more in detail!}
\end{center}
\color{magenta}
\begin{itemize}
\item [I.] Hinton \& Nowlan's experiment
\item [II.]Reduced even-parity problem as a benchmark
\item [III.]A robot navigation
\item [IV.]Quantum computation
\end{itemize}


\clearpage   % =========================================
\begin{center}
\color{magenta}
\hspace*{1in}\\
\hspace*{1in}\\
\[<I>\] Hinton \& Nowlan's Simplest Needle in a Hay.
\end{center}

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Hinton \& Nowlan's Needle (1987)}\\
\end{center}

%% approximately one million points
\begin{figure}[h]
\begin{center}
\includegraphics[width=15cm,height=1.5cm]{a-needle-0.eps}
\end{center}
\end{figure}

\color{black}
\noindent
$\bullet$ A-needle $\Rightarrow$ A configuration of 20-bit binary strings
$\bullet$ Haystack $\Rightarrow$ $2^{20}-1$ search points

%% We tried a random search with a same condition as Hinton & Nowlan's
%% I have never observed the needle more than 26bits by ANY search

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Their choice of 20-bit was a good one!}\\
\end{center}

\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm,height=6cm]{random-search-needle-2.eps}
%%\includegraphics[width=10cm,height=6cm]{random-search-needle.eps}
\end{center}
\end{figure}

% their smart trick is an inclusion of flexible genes which is expressed with red 9 here
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Evolution under Baldwin effect \\ -- Lifetime learning of phenotype}\\
\end{center}
{\LARGE
\color{black}
\hspace*{1in}A genotype:
\begin{center}
(10\color{red}9\color{black}010\color{red}99\color{black}0110010010\color{red}9\color{black}1)\\
%%(10901099011001001091)\\
$\Downarrow$
\end{center}
\hspace*{1in} Its phenotype:
\begin{center}
(10\color{red}1\color{black}010\color{red}01\color{black}0110010010\color{red}0\color{black}1)\\
(10\color{red}0\color{black}010\color{red}11\color{black}0110010010\color{red}1\color{black}1)\\
...
\end{center}
}

\clearpage  % =========================================
\hfill {\large (Cont'd)}
\begin{center}   
\bigskip
(Their assumption)\\
The closer the {\it genotype} to the needle,\hfill\\
\hfill the faster the learning of {\it phenotype.} \\
$\Downarrow$ \\
This makes the needle-like-peak smoother.
\end{center}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Their GA implementation}\\
\color{black}
\bigskip
\color{red} 1000 \color{black} 
genotypes with 
\color{red} 25\% \color{black} 
flexible genes, \\
each allowed 
\color{red} 1000 \color{black} 
lifetime learnings; \\
\bigskip
Roulette wheel selection; \\
One-point cross over;\\
Mutation; \\
...... \\
\end{center}



%% random search is the same as before but this time against number of search points instead of 
%% number of bits
%% we may see a tremendous improvement
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Baldwin effect looks great!}\\
\end{center}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=8.5cm]{kauno-linear-2.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\hfill {\large (Cont'd)}
\begin{center}   

\hspace*{1in}\\
Note, anyway, in both cases, \\
\color{red} $O(N)$  \color{black} steps are necessary!
\end{center}

%% are we REALLY happy ...
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Are we happy with this Baldwin effect?}\\

\bigskip
\color{black}
{\LARGE
Why should we continue \\
when lifetime-learning already has found the needle? \\

$\Downarrow$ \\

(Turney 1987)\\
{\it ``Not from an engineering  but a biological interest.''}
}
\end{center}

%% we tried histgrams ...
%% by and large
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Is a high fitness gene a good gene?}\\

\Large
\color{black}
{(
\end{center}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=15cm,height=3cm]{lifetime-success-001.eps}
\includegraphics[width=15cm,height=3cm]{lifetime-success-002.eps}
%% \includegraphics[width=16cm,height=4cm]{lifetime-success-01.eps}
%% \includegraphics[width=16cm,height=4cm]{lifetime-success-02.eps}
%% \includegraphics[width=16cm,height=4cm]{lifetime-success-1.eps}
%% \includegraphics[width=16cm,height=4cm]{lifetime-success-2.eps}
\end{center}
\end{figure}


\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm,height=6cm]{random-search-needle-2.eps}
%%\includegraphics[width=10cm,height=6cm]{random-search-needle.eps}
\end{center}
\end{figure}

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Goodness depends on number of 9?}
\end{center}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=15cm,height=3cm]{lifetime-success-002.eps}
\includegraphics[width=15cm,height=3cm]{lifetime-success-003.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\hfill {\large (Cont'd)}
\hspace*{1in}\\
\begin{center}   


%% \clearpage   % =========================================
%% \begin{center} \color{blue}
%% {\bf How many 9's are necessary?}\\
%% \end{center}
%% \begin{figure}[bhtp]
%% \begin{center}
%% \includegraphics[width=9cm,height=6cm]{how-flexible-necessary.eps}
%% \end{center}
%% \end{figure}


%% \clearpage   % =========================================
%% \begin{center} \color{blue}
%% {\bf Is the number of 9's decreasing?}\\
%% \end{center}

%% \bigskip
%% \begin{figure}[bhtp]
%% \begin{center}
%% \includegraphics[width=16cm,height=8cm]{lamarck-number-of-9.eps}
%% \end{center}
%% \end{figure}


%% we experiment with 200 different random seeds
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf An extinction!}\\
\color{black}
\bigskip
{\Large In the 1st generation,\\
only 4 successful genotypes are found at the luckiest case.

\begin{figure}[h]
\begin{center}
\includegraphics[width=7cm,height=4cm]{baldwin-survived.eps}
\end{center}
\end{figure}
Evolution was not successful.}
\end{center}

%% this is believed to be intractable
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf What about Lamarckian Inheritance?}\\

\color{black}
\bigskip
{\LARGE
An inverse mapping from phenotype to genotype  is necessary.\\
\hspace*{1in}\\
Turney (1996)\\
{\it ``We believe that computing this mapping is intractable,''}
}
\end{center}


%% I don't know this computational lamarkian model is meaningful in a biological sence...
%% but this hypothesis used to try to explain why girrafe has a long neck
%% nowadays now one believe this happen in nature
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Why giraffe has a long neck?}\\

\color{black}
\bigskip
{\LARGE
Let's re-map a few of successful 9's in phenotype \\to its genotype. \\


\begin{center}
\includegraphics[width=15cm,height=3cm]{lifetime-success-001.eps}
\includegraphics[width=15cm,height=3cm]{lifetime-success-002.eps}
%% \includegraphics[width=16cm,height=4cm]{lifetime-success-01.eps}
%% \includegraphics[width=16cm,height=4cm]{lifetime-success-02.eps}
%% \includegraphics[width=16cm,height=4cm]{lifetime-success-1.eps}
%% \includegraphics[width=16cm,height=4cm]{lifetime-success-2.eps}
\end{center}
\end{figure}


\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm,height=6cm]{random-search-needle-2.eps}
%%\includegraphics[width=10cm,height=6cm]{random-search-needle.eps}
\end{center}
\end{figure}



\begin{figure}[h]
\begin{center}
\includegraphics[width=7cm,height=3cm]{lamarck-avg-fit-2.eps}
\includegraphics[width=3cm,height=3cm]{giraffe.eps}
\end{center}
\end{figure}
Eventually, all 9's disappeared to converge to the needle itself.
}
\end{center}

%% Inspite of a superficial improvement ... 
%% all of these 2 cases ...
\clearpage  % =========================================
\begin{center}\color{blue}
{\bf The number of total points searched,\\
{\Large (not the number of individuals,)} \\
 is almost similar as a random search.}\\

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=8cm,height=4.5cm]{kauno-exponential-2.eps}
\includegraphics[width=8cm,height=4.5cm]{baldwin-1.eps}
\end{center}
\end{figure}

\end{center}


\clearpage  % =========================================
\hfill {\large (Cont'd)}
\begin{center}   
\hspace*{1in}\\
Alas, how to reach the needle longer than 25-bit?
\end{center}


%% the other strongly objected
%% number of punched small halls
\clearpage   % =========================================
\color{magenta}
\begin{center}
%% A Bench Mark \\ \hspace*{1in}   -- 
\[<II>\] Reduced Even-Parity Boolean Function.
\end{center}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf A discussion}\\

{\Large
\hspace*{1in}\\
\color{black}
(Yu \& Miller, 2002)\\
{\it ``Finding Needles in Haystacks is not Hard with Neutrality.'' }\\

\hspace*{1in}\\
vs.\\
\hspace*{1in}\\
(Collins, 2005)\\
{\it ``Finding Needles in Haystacks is Harder with Neutrality.'' }\\

}
\end{center}


%% By reduced we mean only XOR and EQ are used to construct this Boolean function
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Reduced Even-$n$-Parity Problem}\\

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=6cm,height=2cm]{paper-tape.eps}
\end{center}
\end{figure}

\color{black}
{\LARGE Even-parity Boolean function only with XOR and EQ} \\
$\Downarrow$ \\
{\LARGE A commonly used benchmark in GP, GA etc.}
\end{center}


\clearpage   % =========================================
%% \begin{center} \color{blue}
%% {\bf Reduced Even-$n$-Parity Problem}
\color{black}
\hfill {\large (Cont'd)}
%% \end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=12cm,height=4cm]{even-parity.eps}
\end{center}
\end{figure}



%% not many like 90 \% not a few like 10 \% but a half outputs are correct 
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf A strange fitness distribution}\\

\begin{figure}[bhtp]

\begin{center}
\includegraphics[width=12cm,height=3cm]{histgram-parity.eps}
\end{center}
\end{figure}
\color{black}
{\LARGE 
(1) 100\%, (2) 50\%, or (3) 0\% outputs are correct.\\
$\Rightarrow$ No information of ``How good are candidates?''}

\end{center}

%% claimed a success for a maximum of n = 12
%% let me skip the detail
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Yu \& Miller's reported success (2002)}\\

\color{black}
\bigskip
{\LARGE
by {\it Cartesian Genetic Programming} \\

\bigskip
for $n=12$ \\
\bigskip
48 successes out of 100 runs each with 10,000 iterations\\
while\\
none of 4,000,000 randomly created candidates failed
}
\end{center}

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Yu \& Miller's assumption}\\
\hspace*{1in}\\
\bigskip
\color{black}
The success is due to what they call a \\  \color{red} {\it neutral-mutation-on-intron}.
\end{center}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Yu \& Miller's CGP}\\
\end{center}

\begin{itemize}
{\LARGE
\item[(1)] Create 100 gates of XOR or EQ at random.
\item[(2)] Select randomly one output gate out of those 100 created. 
\item[(3)] From one gate to the next, set the two input connections
to either of the output line previously set gate or one of the $n$ input lines at random.  
}
\end{itemize}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf An example genotype of CGP \\ for Even-5-Parity}\\
\end{center}
\color{blue}
%%\hspace*{1in}\\
{\Large
\hspace*{0.9in}
a \hspace{.75in}b \hspace{.85in}c \hspace{0.75in}d \hspace{.80in}e \hspace{.9in} f \hspace{.85in}\\
\color{black}
\hspace*{.5in}
((EQ 1 2)(XOR 3 a)
\color{red}(EQ a 2)
\color{black}(EQ 4 b)
\color{red}(XOR 1 4)
\color{black}(XOR d 5))
\begin{center}
$\Downarrow$
\end{center}
}
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm,height=2cm]{even-5-parity-1.eps}
\end{center}
\end{figure}



\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Neutral mutation on introns}\\

\bigskip
\color{black}
{\Large
Some genes do not contribute to phenotype  $\Rightarrow$ 
\color{red} {\it intron} \color{black}\\
\bigskip
And, so does a mutation on intron $\Rightarrow$ 
\color{red} {\it neutral} \color{black}\\
\hspace*{1in}\\
Hence\\
Size of function is flexible!\\
But the question is, as they claimed, ``Does it enhance the search?''}
\end{center}

%% Later collins objected

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Collins' doubt (2005)}\\

\bigskip
\color{black}
{\Large
"Unable to repeat the same performance as reported."  \\
$\Downarrow$\\
He tried, instead,\\
``a random sampling which uses a fully expressed genotype.''\\
$\Downarrow$\\
Better than Yu \& Miller's result.}
\end{center}




\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Collins' random sampling}\\
\end{center}
\color{black}
{\Large
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[(1)] Create 100 random gates either from XOR or EQ.
\item[(2)] Set the output to the 100-th gate.
\item[(3)] For each gate:
   \begin{itemize}
   \item[(i)] Set the type of the gate to either XOR or EQ at random.
   \item[(ii)] Set one of the input connection of the gate to the previous gate.
   \item[(iii)] Set the other input connection to a randomly selected input line.
   \end{itemize} 
\item[(4)] Repeat (3) up to N.
\end{itemize} 
}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Collins' algorithm excludes many candidates such as...}\\
\end{center}

\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm,height=2.2cm]{even-5-parity-2.eps}
\includegraphics[width=8cm,height=2cm]{even-5-parity-3.eps}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
\includegraphics[width=12cm,height=2.8cm]{even-5-parity-4.eps}
\end{center}
\end{figure}



\clearpage  % =========================================
\hfill {\large (Cont'd)}
\begin{center}   

\hspace*{1in}\\
Anyway, their solutions found are both limited to\\
\color{red} $n < 13$.
\end{center}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf On the other hand...}\\

\color{black}
{\LARGE We human can create an even-$n$-parity for however large $n$}.
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=18cm,height=1cm]{parity-1.eps}
\end{center}
\end{figure}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=5cm,height=4.5cm]{parity-2.eps}
\end{center}
\end{figure}

\clearpage   % =========================================
\color{magenta}
\begin{center}
\[<III>\] A Robot Navigation in 2-D grid.
\end{center}

%% \hspace*{.25in}Yet another  Bench Mark \\ 
%% \hspace*{1.75in} -- A Robot Navigation in 2-D grid.

%% In other words,

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Finding a needle \\ hidden in a huge 2-dimensional grid}\\
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=5cm,height=5cm]{grid.eps}
\end{center}
\end{figure}


%% This is another type of lifetime-learning
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Hinton \& Nowlan's scenario} \\
\end{center}

\color{black}
\begin{center}
{\LARGE
Can parachuters reach the needle in a pastoral\\
if allowed random walks around their falling place?} \\ 
\end{center}

\begin{figure}[bhtp]
\begin{center}
   \includegraphics[width=4cm,height=4.1cm]{parachute.eps}
\rotatebox{90}
{
   \includegraphics[width=4cm,height=6cm]{parachute-22.eps}
}
\end{center}
\end{figure}

%% here we take a different scenario
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Let's try, here, a random walk, instead}\\
\end{center}

\begin{figure}[bhtp]
\begin{center}
   \includegraphics[width=8cm,height=7cm]{walk.eps}
\end{center}
\end{figure}


%% an example of successful random walk wit 178 steps
%% to get one point we need a computation overnight
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Can random-walker reach the needle?}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
   \includegraphics[width=7cm,height=7cm]{trace-96-start.eps}
\end{center}
\end{figure}

%% experimental result  when grid size becomes large
%% a question then will be can a learning ... IN GENERAL?
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Can a learning enhance efficiency?}\\
\end{center}

\bigskip
\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm,height=6cm]{evolution-96.eps}
\includegraphics[width=6cm,height=6cm]{trace-96-end.eps}
\end{center}
\end{figure}

%% this is still our on-going experiment
%% since it needs a couple of nights to get this point

%% because to get one point around here need a cople of overnights run
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A limit in grid size}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=8cm,height=6cm]{one-robot-11.eps}
\includegraphics[width=8cm,height=6cm]{one-robot-22.eps}
\end{center}
\end{figure}





\clearpage  % =========================================
\hfill {\large (Cont'd)}
\begin{center}   

\hspace*{1in}\\
{\LARGE $N/2$ queries on average, and  $(N-1)$ on worst case.\\
are necessary.}\\
\bigskip
{\Large (E.g. imagine breaking a PIN code.)} \\
$\Downarrow$ \\
{\Large We need \color{red} $O(N)$ \color{black} {\it random-trial-\&-errors} or
{\it one-by-one-searches.}}

\end{center}



\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Grover's quantum search (1997)}\\
\color{black}
\bigskip
A speed up from $O(N)$ to $O(\sqrt{N})$.
\end{center}


\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=7.5cm,height=4cm]{fictitious-classics.eps}
\includegraphics[width=7.5cm,height=4cm]{fictitious-quantum.eps}
\end{center}
\end{figure}



\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=7.5cm,height=4cm]{quantum-path.eps}
\includegraphics[width=5cm,height=4cm]{messy-quantum.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf What are differences?}\\
\color{black}
\bigskip
1.
\end{center}
\color{red}
\hspace*{1in} Measurement cannot be done \\ 
\hspace*{2in} before completing computation.


\clearpage  % =========================================
\hfill {\large (Cont'd)}
\bigskip
\color{black}
\begin{center}
2. \\
\bigskip
A Function, like $P(x)$, is applied \\ 
\bigskip
to 
\color{red}{\it superposed} states simultaneously \\
\color{black} not a {\it single} state one-by-one.
\end{center}

\clearpage  % =========================================
\hfill {\large (Cont'd)}
\begin{center}   
\bigskip
\color{black}
3. \\ 
\color{red}
We must know {\it when to stop.}\\

\bigskip
\color{black}
{\LARGE While in a {\it classical computer},
we could continue the run after conversion,  e.g., in GA.}
\end{center}

%% we already get what we want
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Grover's algorithm}\\
\end{center}
{\LARGE
\color{black}
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[1.] Compute $P(x)$ for all possible $x$.\\
    \hspace*{.3in} \color{red}{\Large (Done simultaneously, and cannot be measured 
                               at this moment.)}\color{black}
\item[2.] Rotate the state of needle $\pi/2$ radian while not all others. \\
%% iff it's the needle {\Large $P(x)=1$.}\\
    \hspace*{.3in} \color{red} {\Large (Also done simultaneously.)} \color{black}
\item[3.] Repeat 1.~- 2. $\pi \sqrt{N}/8$ iterations. \\
    \hspace*{.3in} \color{red} {\Large (One must know when to stop.)} \color{black}
\item[4.] Measure all states. \\
    \hspace*{.3in} \color{red} {\Large (The needle is measured with 
                                        a high probability close to 1.)}
\end{itemize}
}



\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Bit \& Qubit}\\
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=10cm,height=4cm]{quantum-computation.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Qubit is a superposition of two basis}\\
\color{black}
\begin{displaymath}
|0\rangle = a |0\rangle + b |1\rangle
\end{displaymath}
and 
\begin{displaymath}
|1\rangle = c |0\rangle + d |1\rangle
\end{displaymath}
{\Large
where $a,b,c,d \in Z$, and e.g., $\| c \|^2$ is a probability 
for $|1\rangle$  to be   $|0\rangle$.}
\end{center}


\clearpage  % =========================================

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=7cm]{grover.eps}
\end{center}
\end{figure}


%% we already get what we want
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A toy implementation by photons}\\
\end{center}


\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=7cm]{photon-implement.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A quantum walk on the line}\\
\color{black}

%% When a particle goes from A to B, it takes all possible paths all at the same time.
%% The probability of observing the particle doing the quantum walk
%% at any given point $n$ at $t$  (Nayak \& Vishvanath)

\color{black}

\begin{Large}
\begin{displaymath}
p(n, t) = \| \psi_L (n, t) \|^2 + \| \psi_R (n, t) \|^2
\end{displaymath}
where
\begin{displaymath}
\psi_L = \frac{1+(-1)^{n+t}}{2} \int_{-\pi}^{\pi}{\frac{dk}{2 \pi}}
(1 + \frac{\cos k}{\sqrt{1 + \cos^2 k}}) \exp \{{-i(\omega_k t + kn)\}}
\end{displaymath}

\begin{displaymath}
\psi_R = \frac{1+(-1)^{n+t}}{2} \int_{-\pi}^{\pi}{\frac{dk}{2 \pi}}
\frac{\exp (i k)}{\sqrt{1 + \cos^2 k}}) \exp \{{-i(\omega_k t + kn)\}}
\end{displaymath}
\end{Large}
\end{center}

\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A propagation of wave function}\\
\end{center}

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=1.5cm]{wave-f-1.eps}
\end{center}
\end{figure}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=1.5cm]{wave-f-20.eps}
\end{center}
\end{figure}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=16cm,height=1.5cm]{wave-f-100.eps}
\end{center}
\end{figure}



%% I think we are running out of time and hope this conlulde the tolk, thank you
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Concluding Remarks}\\
\end{center}

\color{black}
{\LARGE
\begin{itemize}
\setlength{\itemsep}{0pt}
\item Searching for a needle in a hay is open \& important issue.
\item We need real efficient approaches.
\item Not yet so far a real efficient one.
\bigskip
\item We have to avoid an effect of \\
\hspace*{0.6in}{\it like-to-hear-what-we-would-like-to-hear.}\\
as all of today's cases seem to have it more or less.
\end{itemize}
}


\end{huge}
\end{document}


