Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal 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• 3 citations
Publisher

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,424 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

Hay from the Haystack: Explicit Examples of Exponential Quantum Circuit Complexity

Yifan Jia, Michael M. Wolf

arXiv:2205.06977•Communications in Mathematical Physics•May 7, 2023•11 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•1 citation

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

Oblivious verification of common string

Claude Crépeau, Louis Salvail

. We consider a situation where two parties, Alice and Bob, share a common secret string and would like to mutually check their knowledge of that string. We describe a simple and e#cient protocol based on oblivious transfer to check mutual knowledge of a common string in such a way that honest parties will always succeed in convincing each other, while a dishonest party interacting with an honest party will have vanishingly small probability of convincing him. Moreover, a dishonest party gains only a very small amount of information about the secret string from running the protocol: whoever enters the protocol with no knowledge of the secret string would have to enter this protocol an exponential number of times in order to gain non-negligible information about the string. 1 Introduction Didn't you worry last time you typed your PIN (Personal Identification Number) to an unknown Automated Teller Machine (ATM) that it could be a fake and that the sole purpose of this ATM could be t...

Quarterly - Centrum voor Wiskunde en Informatica•Jun 1, 1995•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 NNN 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.5N0.5N0.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(N)O(\sqrt{N})O(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 N\sqrt{N}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.
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.
. We consider a situation where two parties, Alice and Bob, share a common secret string and would like to mutually check their knowledge of that string. We describe a simple and e#cient protocol based on oblivious transfer to check mutual knowledge of a common string in such a way that honest parties will always succeed in convincing each other, while a dishonest party interacting with an honest party will have vanishingly small probability of convincing him. Moreover, a dishonest party gains only a very small amount of information about the secret string from running the protocol: whoever enters the protocol with no knowledge of the secret string would have to enter this protocol an exponential number of times in order to gain non-negligible information about the string. 1 Introduction Didn't you worry last time you typed your PIN (Personal Identification Number) to an unknown Automated Teller Machine (ATM) that it could be a fake and that the sole purpose of this ATM could be t...