\documentclass[10pt]{article}
\usepackage{graphicx}

\textheight 225mm
%\topmargin 5mm
\textwidth 175mm
\oddsidemargin -7mm

\newtheorem{algorithm}{Algorithm}

\title{Finding a needle in a haystack --- from 
 Baldwin Effect to Quantum Computation}

\author{Brest State Technical University\\
           Moskowskaja 267, Brest 224017 Republic of Belarus\\
           akira@bsty.by}

\date{}

\begin{document}
\maketitle
\pagestyle{empty}
\thispagestyle{empty}

\begin{abstract}
\noindent
If we want to break someone else's PIN -- Personal Identification Number -- of, say, an ATM -- Automated Teller Machine --, how many trial would be necessary when we want to be efficient? This is a sort of what we call a-needle-in-a-hay-stack problem. In 1987, in their seminal paper, Hinton \& Nowlan proposed a Genetic Algorithm with a needle being a unique configuration of 20-bit binary string while all other configurations being haystack. What they proposed was to exploit the Baldwin effect calling it a life-time-learning of individuals of their Genetic Algorithm. Since then there has been a fair amount of exploration of this problem, claiming, "This is a-needle-in-a-hay-stack problem, and we've found a more efficient algorithm than a random search." Some of them, however, were found to be the results of an effect of like-to-hear-what-we-would-like-to-hear. In this talk, we will try a bird's eye view on what we have as examples on this issue and how they were explored, including the approach by means of Quantum Computation which claims, "The steps to find a needle are order square-root of N while those of exhaustive search are order of N where N is the number of search points."
\end{abstract}
 

\section{Introduction}
Usually in an ATM -- Automated Teller Machine or in a pribate web page, we need to show
our PIN -- Personal Identification Number, and  for the security reason we are allowed to try an input
just a couple of time, typically three times. So it might interest us if we are allowed to repeat
trial-and-error  until we reach the legitimate number, how many times would be necessary?
Though, typically PIN is a 4-digit decimal, we now assume $n$-bit binary PIN.
Here two really simple strategies are shown, that is, (i) random search and (ii) exhaustive one-by-one search.  
In Fig.~1 and Fig.~2, both results of number of trials until we find a hidden unique PIN
averaged after  100 trials as a function of $n$. 
In both cases we see the number of trials explode exponentially as number of bit increases.
The motivation of this paper is to argue if we have more efficient strategies or not.
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=8.3cm,height=5cm]{one-by-one.eps}
\includegraphics[width=8.8cm,height=5cm]{random-search.eps}
\end{center}
\caption{Number of trials needed to find out a hidden unique PIN
averaged after 100 trials as a function of $n$. One is by a random search (left) 
and  exhaustive search one by one (left).}
\end{figure}


\section{Baldin Effect}
It was Hinton \& Nowlan \cite{hint} who firstly proposed computationl model of the Baldwin Effect in 1987.
The scenario was exactly the same as above mentioned one. 
What he proposed is {\it a life time learning} of each of the individuals
in a search algorithm based on populational. That is, each indidual has adaptive genes in addition to
the original 0's and 1's. Let's denote it here 9's. For example, the individual is 
\begin{displaymath}
(0 1 1 0 0 9 0 0 0 9 9 1 1 0 0 1 1 9 0 1).
\end{displaymath}
Then each individual is allowed to assign 0 or 1 at the location of 9, which is refered to as learning of 
individual. They are allowed to try this learning, say, 1000 times, in their life time.
If, by chance, individal is mach to the needle the number of learning is the fitness of the individual.
This might be called the Baldwin effect.
It has attracted, and is still attracting, many computer scientists.
In 2005,  Mills \& Watson \cite{mill-1} made a more deeply analitical approach to the issue.
Mills \& Watson gave us an analyses in exactly the same universe as Hinton \& Nowlan's shown almost two decades ago,
while many others see the phenomenon or apply the model to a more sophistcated problems, and later, in 2006,
extended the analysis to more complex but still symple universe of {\it two needles} whose length is different
each other on a  compltely flat plateau \cite{mill-2}.
What is the Baldwin effect more specifically? As Mills \& Watson cleary summarizes,
{\it ``The Baldwin Effect indicates that individually learned behaviours acquired during an organism's 
lifetime can influence the evolutionary path taken by a population, without any direct Lamarckian 
transfer of traits from phenotype to genotype.
... Our knowledge of modern genetics suggests that an organism's lifetime adaptations cannot influence 
the course of evolution because learned characteristics do not change ones own genes. ... 
The hypothesis appears very similar to Lamarck's disproved beliefs that an acquired 
trait is directly inherited by offspring.''}


\subsection{Discussion in this Section}
Hinton \& Nowlan showed that the number of genes whose value is 9 reduced over time of evolution.
From engineering view, this is not interesting any more. Why? Because we could now the secret PIN
when in the first generation if at least one of those individuals reaches the needle it's enough.
In the right graph in Fig.~2 the results of life time learning in the initial population.
with a mostly empty circle. We can see enormous reduction of the number of individuals until
the needle firstly is found. The extended profile is shown in the light graph. But, alas,
if we count the total number of points which is shown by the filled circle in the left graph,
we realize the result is almost the same as the random search.
As a matter of fact the time needed to reach the needle is almost the same in all those three cases;
that is random, exhaustive, and search by lifetime learning.

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=8cm,height=5cm]{baldwin-1.eps}
\includegraphics[width=8.9cm,height=4.7cm]{baldwin-2.eps}
\caption{Left: The number of individuals (partly filled circle) and the number of points visited (filled circle)
until any of individuals reaches to the needle. Right: the scale was chanced for the plots of the number of individuals
in the Left one.}
\end{center}
\end{figure}


\section{Neutral Mutation on Intron}
\subsection{Reduced Even-n-Parity Problem}
Even-n-Parity problem is a classic benchmark problems in Evolutionary Computation research.
Given any $n$-bit binary input, it returns 1 if the number of 1 of the input is even,
otherwise it returns 0. 
Assume now we are  constructing a population of candidate solutions of Even-n-Parity logic 
circuit only by using {\it XOR} and {\it EQ} Boolean functions, which is called 
a {\it reduced} Even-n-Parity problem.
We can evaluate each of those candidate solutins by giving it all possible combinations of 
$n$-bit binary string one by one.
When we check each result of whether the output is correct or not, we will notice that 
there are only three cases: (i) all of the results for those $2^n$ test cases are correct;
(ii) a half of the results are correct, and (iii) all are incorrect.\\

\noindent
The number of all possible candidates when we are allowed to use either of 
{\it XOR} and {\it EQ} gates from 1 up to $N$ will be
\begin{displaymath}
\sum_i^N{2^i}n^{i+1}.
\end{displaymath}
The number of solutions are analytically given by Collins \cite{coll}.
The author wrote for $n=12$, for instance, the number of sollutions is $2.568 \times 10^{134}$
while the number of possible candidats is $1.315 \times 10^{142}$
when we use  up to 100 of {\it XOR} or {\it EQ}.
That is to say, the ratio of solutions in the search space is 0.00042\%.
So we might say the solution is like {\it needles in a haystack}.

\noindent
Then we have a very interesting disscussions described in the following two subsections.

\subsection{Finding Needles in Haystacks is Not Hard with Neutrality?}
In 2002, Yu and Miller \cite{yu}
applied {\it Cartesian Genetic Programming} (CGP) 
\cite{mill} to the even-n-Parity problem.



\begin{algorithm}[Candidate Creation in CGP]\hspace{1in}
\begin{itemize}
\item[(1)] Create 100 gatess of XOR or EQ at random.
\item[(2)] Select randomely one output gate out of those 100. 
\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 $n$ input lines.  
\end{itemize}
\end{algorithm}

\noindent
Let me show an example, praphrasing the one from Yu \& Miller's paper \cite{yu}, 
assume now we create 6 gates instead of 100 just for the sake of simplicity.
The gate is numbered {\it a, b, c, d, e, f}, and the gate $f$ is the output unit.
Then a genotype will be 
\begin{displaymath}
((EQ, 1, 2)^a (EQ, 3, a)^b (XOR, a, a)^c (XOR, b, 3)^d (EQ, 4, c)^e (EQ, d, 4)^{f=out})
\end{displaymath}
The phenotype of this example genotype is
\begin{displaymath}
1 \hspace{.1in} {\mbox{\tiny EQ}} \hspace{.1in} 2 \hspace{.1in} {\mbox{\tiny EQ}} \hspace{.1in} 
3 \hspace{.1in} {\mbox{\tiny XOR}}\hspace{.1in} 4 \hspace{.1in} {\mbox{\tiny EQ}} \hspace{.1in} 5
\end{displaymath}
Note that the 3rd gene $c$ and the 5th gene $e$ do not contribute to constract the phenotype,
and hence this is called {\it introns}. 
As you might notice that this CGP representation enevitably includes introns.
Mutation of the introne will have no effect on the phenotype and 
and this is why it is called {\it neutral}.\\

\noindent
By running an evolutionary algorithm with one parent and 4 offspring, 
the authors showed this neutral mutation on the intron enhances 
the ability to search for the solutions.
To be more specific, with the maximum number of gates being 100 
and the maximum iteration being 10,000,
carefully tuned 48 CGP runs out of 100 for $n=12$ find a solution, while 
a random search, that is,
any randomly generated 4,000,000 candidates for $n=12$ were not solutions. 

\subsection{Finding Needles in Haystacks is Harder with Neutrality?}
Collins doubted the result of the paper by Yu and Miller in the above subsection.
In his paper, he argued that 10,000 iterations with 4 offspring are 
a sample of at most 40,000 points in the search space. 
The CGP Yu \& Miller reported for $n=12$ results in all gates were EQ, and
the solution density in the case of 12 parity with one type of gate
is 0.003756\%. Hence an expected success rate should be 
\begin{displaymath}
1 - (1 - 0.00003756)^{40000} = 0.778
\end{displaymath}
and as such, Yu \& Millers average success rate of 48\% mentioned above is not a good one.
He propose a random sampling of candidates as follows.

\begin{algorithm}[Randomly sampling non-CGP representations] \hspace{1in}
\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 imput connection of the gate to the previous gate.
   \item[(iii)] Set the other imput connection to a randomly selected input line.
   \end{itemize} 
\item[(4)] Repeat (3) up to N.
\end{itemize} 
\end{algorithm}


\noindent
Then author wrote, ``We recorded 0.0204\% success from a sample of 10 million trials.''
Notice that this result was without an evolution where Yu \& Miller's didn't find
any solutions in 40 million trials.


\subsection{Discussion in this Section}
Collin's logic seems to be clear. 
However, what about the condition of {\it ``the number of gates up to 100?''}
Although he also admitingly wrote, 
{\it ``This sampling method is also not 'fair' -- it over samples short functions as well,''}
the situation would be worse than that.\\

\noindent
Implication of Yu \& Miller's paper is for $n$ larger than 12 will be no more possible to be found.
And the list the Collin's paper regarding the density of the solutions in the search space is 
up to $n=15$. But just brief check shows it's really easy to find a simplest solutions even for $n=16$
shown in the Fig. 5 \ref{fig:parity-1}


\begin{figure}[bhtp] \label{fig:parity-1}
\begin{center}
\includegraphics[width=16cm,height=1cm]{parity-1.eps}
\caption{An example of solutions of Reduced Even-16-Parity found a human not a computer algorithm.}
\end{center}
\end{figure}

\begin{figure}[bhtp] \label{fig:parity-2}
\begin{center}
\includegraphics[width=5cm,height=4.5cm]{parity-2.eps}
\caption{Yet another example of solutions of Reduced Even-16-Parity}
\end{center}
\end{figure}

\section{Search by Quantum Random Walk}
Back in 1997, Grover \cite{grov} porposed a concept in Quantam Mechanics 
to search for  a needle in a haystack more efficiantly than a traditional computation.
As previously mentioned, we don't know essentially more efficient algorithm
to search 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, if we plot the number of individuals 
in the case of exhaustive search for the needle 
until needle is found  shown in Fig. 2
as a function of number of points of the search space instead of the number of bits 
we can see the order of complexity is $\O(N)$. See Fig. 5.

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=9cm,height=6cm]{one-by-one-linear.eps}
\end{center}
\end{figure}

\noindent
Grover's proposed algorithm was probed to search for the needle with $(O\sqrt{N})$
as shown in the fictitious graph in Fig. 8.
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=8cm,height=4cm]{fictitious-quantum.eps}
\caption{A fictitious plot of the order of complexity of Grover's Quantum algorithm.}
\end{center}
\end{figure}
Practical quantum computer hardware is not yet available.
Up to now, all we have is just a few of 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 Physisists 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 of the topic of this paper -- search for a needle -- see, for example,
Kempe's introductory overview of quantum random walks. The auther wrote
"We will give a thorough introduction to the necessary terminology without overburdening the reader with unnecessary mathematics." 




\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 canalisation 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 (2006)
"On Crossing fitness Valleys with the Baldwin Effect."
Proceedings of Artificial Life X, 2006, pp. 493--499.

\bibitem{coll}
M. Collins ``Counting Solutions in Reduced Boolean Parity''
In Proceeding of GECCO, 2004, pp. ???--???

\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{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{kemp}
J. Kempe 
``Quantum Random Walks -- An Introductory Overview." 
Contemporary Physics Vol. 44 (Preprint quant-ph/0303081), 2003, pp. ????-???


\end{thebibliography}
\end{document}



