Finding a Needle in a Haystack: From Baldwin Effect to Quantum Computation
Akira Imada · 2007
If we want to break someone else's PIN (personal identification number) of, say, an ATM (automated teller machine), how many trials would be necessary when we want to be efficient? This is a sort of what we calla-needle-in-a-hay-stackproblem. In 1987, in their wonderful paper, Hinton & Nowlan proposed a genetic algorithm with a needle being a unique configuration of 20-bit binary string while all other configurations being a haystack. What they proposed was to exploit alifetimelearningof individuals in their genetic algorithm, calling it the Baldwin effectinacomputer. Since then there has been a fair amount of exploration of this effect, 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 oflike-to-hear-what-we-would-like-to-hear. In this talk, we will try a bird's eye view on a few examples we have had so far, and how they were explored, including the approach by means of quantum computation which claims, "The steps to find a needle areO(radicN) while those of exhaustive search by a traditional computer are O(N) whereNis the number of search points."