© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

International Conference on Computer Information Systems and Industrial Management Applications (CISIM)

Finding a Needle in a Haystack: From Baldwin Effect to Quantum Computation

Akira Imada

Published Jun 1, 2007• 2 citations

Abstract

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."

DOI: 10.1109/cisim.2007.29

Related papers

Quantum Mechanics Helps in Searching for a Needle in a Haystack

Lov K. Grover

Quantum mechanics can speed up a range of search applications over unsorted data. For example, imagine a phone directory containing $N$ names arranged in completely random order. To find someone's phone number with a probability of 50%, any classical algorithm (whether deterministic or probabilistic) will need to access the database a minimum of $0.5N$ times. Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. By properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly. As a result, the desired phone number can be obtained in only $O(\sqrt{N})$ accesses to the database.

arXiv:quant-ph/9706033•Physical Review Letters•Jul 14, 1997•4,306 citations

Quantum search protocol for an atomic array

Marlan O. Scully, Muhammad Suhail Zubairy

Quantum computers can, in principle, exceed the speed of ordinary computers by taking advantage of quantum coherence and entanglement. It is possible to find a ``needle in a haystack'' of $N\ensuremath{-}1$ straws in only $\sqrt{N}$ searches by utilizing coherent superposition states. In the present paper we show how modern quantum optics may provide a simple and practicable quantum search procedure, which may also yield insights into quantum search algorithms in general.

Physical Review A•Jul 5, 2001•11 citations

Contemplating quantum computation

D. Mermin

People with surprisingly diverse points of view see quantum computation as vindicating their pet idea of what quantum mechanics is all about. The present speaker is no exception. In this introductory talk I shall describe a few elementary quantum algorithms with a view to revealing their intrinsic charm, and illustrating this blind-men-and-the-elephant aspect of that charm.

Optical Fiber Communication Conference•Jan 1, 2001•0 citations

Letters to Michael Nielsen

Christopher A. Fuchs

February 1996, “Goo-Losh” Mmm, goulash…is that how you spell it? Thanks for the tip. I haven't heard the reaction of Bennett and company on this business yet, but when I do, I'll send a report your way. I've been thinking about Kochen–Specker theorems lately; they're very nice you know…especially the ones with small numbers of vectors. Implications for “quantum information”? There must be! In particular, why can't one go much further in this effort to prove the theorem with smaller and smaller numbers of vectors? Why is there no proof of this property (i.e., no noncontextual hidden variables for the outcomes of standard von Neumann measurements), the very second you admit a measurement that is nonorthogonal to the others? Just food for late night thoughts. March 1996, “The Commitments” It's a good movie; did you ever see it? Suppose you need some cash and so you go to your Automated Teller Machine (ATM). You insert your bank card and the machine asks you for your Personal Identification Number (PIN). It does this for the obvious reason that it wants to know that you are indeed who you say you are before it hands over the money. That's a good safeguard. However suppose, as really did happen a year or two ago, someone had set up a fake ATM in place of the real one.

Cambridge University Press eBooks•Jan 6, 2011•0 citations

Another classical analog of Grover's quantum search

Shayak Bhattacharjee

In this work I describe a classical analog of Grover's quantum searching algorithm, explaining why a quantum algorithm should be able to perform search in O(sqrtN) steps and also acting as a useful pedagogic demonstration.

arXiv:1411.6551•Nov 21, 2014•0 citations

Test-state approach to the quantum search problem

Arun Sehrawat, Le Huy Nguyen, Berthold‐Georg Englert

The search for ``a quantum needle in a quantum haystack'' is a metaphor for the problem of finding out which one of a permissible set of unitary mappings---the oracles---is implemented by a given black box. Grover's algorithm solves this problem with quadratic speedup as compared with the analogous search for ``a classical needle in a classical haystack.'' Since the outcome of Grover's algorithm is probabilistic---it gives the correct answer with high probability, not with certainty---the answer requires verification. For this purpose we introduce specific test states, one for each oracle. These test states can also be used to realize ``a classical search for the quantum needle'' which is deterministic---it always gives a definite answer after a finite number of steps---and 3.41 times as fast as the purely classical search. Since the test-state search and Grover's algorithm look for the same quantum needle, the average number of oracle queries of the test-state search is the classical benchmark for Grover's algorithm.

arXiv:1102.3628•Physical Review A•May 17, 2011•5 citations

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."

Quantum mechanics can speed up a range of search applications over unsorted data. For example, imagine a phone directory containing

N

names arranged in completely random order. To find someone's phone number with a probability of 50%, any classical algorithm (whether deterministic or probabilistic) will need to access the database a minimum of

0.5N

times. Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. By properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly. As a result, the desired phone number can be obtained in only

O(\sqrt{N})

accesses to the database.

Quantum computers can, in principle, exceed the speed of ordinary computers by taking advantage of quantum coherence and entanglement. It is possible to find a ``needle in a haystack'' of $N\ensuremath{-}1$ straws in only

\sqrt{N}

searches by utilizing coherent superposition states. In the present paper we show how modern quantum optics may provide a simple and practicable quantum search procedure, which may also yield insights into quantum search algorithms in general.

February 1996, “Goo-Losh” Mmm, goulash…is that how you spell it? Thanks for the tip. I haven't heard the reaction of Bennett and company on this business yet, but when I do, I'll send a report your way. I've been thinking about Kochen–Specker theorems lately; they're very nice you know…especially the ones with small numbers of vectors. Implications for “quantum information”? There must be! In particular, why can't one go much further in this effort to prove the theorem with smaller and smaller numbers of vectors? Why is there no proof of this property (i.e., no noncontextual hidden variables for the outcomes of standard von Neumann measurements), the very second you admit a measurement that is nonorthogonal to the others? Just food for late night thoughts. March 1996, “The Commitments” It's a good movie; did you ever see it? Suppose you need some cash and so you go to your Automated Teller Machine (ATM). You insert your bank card and the machine asks you for your Personal Identification Number (PIN). It does this for the obvious reason that it wants to know that you are indeed who you say you are before it hands over the money. That's a good safeguard. However suppose, as really did happen a year or two ago, someone had set up a fake ATM in place of the real one.

The search for ``a quantum needle in a quantum haystack'' is a metaphor for the problem of finding out which one of a permissible set of unitary mappings---the oracles---is implemented by a given black box. Grover's algorithm solves this problem with quadratic speedup as compared with the analogous search for ``a classical needle in a classical haystack.'' Since the outcome of Grover's algorithm is probabilistic---it gives the correct answer with high probability, not with certainty---the answer requires verification. For this purpose we introduce specific test states, one for each oracle. These test states can also be used to realize ``a classical search for the quantum needle'' which is deterministic---it always gives a definite answer after a finite number of steps---and 3.41 times as fast as the purely classical search. Since the test-state search and Grover's algorithm look for the same quantum needle, the average number of oracle queries of the test-state search is the classical benchmark for Grover's algorithm.