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

Science

Searching a Quantum Phone Book

Gilles Brassard A

Published Jan 31, 1997• 101 citations
Publisher

Abstract

Finding a phone number in a directory when one knows the name is easy; much harder is finding the name given the number. On average, a search algorithm will have to scan half the total number of entries. If the database or directory is extremely large, the search may be impossible with classical computers. New possibilities emerge, however, with quantum computing. As Brassard discusses in his Perspective, a new algorithm developed by L. K. Grover enables much faster searching of large databases if one uses a quantum computer.

DOI
10.1126/science.275.5300.627

Related papers

A fast quantum mechanical algorithm for database search

Lov K. Grover

Imagine a phone directory containing N names arranged in completely random order. In order to find someone's phone number with a 50% probability, any classical algorithm (whether deterministic or probabilistic) will need to look at a minimum of N/2 names. 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)) steps. The algorithm is within a small constant factor of the fastest possible quantum mechanical algorithm.

arXiv:quant-ph/9605043•May 29, 1996•45 citations

Grover’s Search Algorithm

Mikio Nakahara

Suppose there is a stack of N unstructured files and we want to find a particular file (or files) out of the N files. To find someone’s phone number in a telephone directory is an easy structured datebase search problem, while to find a person’s name who has a particular phone number is a more difficult unstructured database seach problem, with which we are concerned in this chapter. It is required to take O(N) steps on average if a classical algorithm is employed. If we check the files one by one, we will hit the right file with probability 1/2 after N/2 files are examined. It turns out that this takes only O( √ N) steps with a quantum algorithm, first discovered by Grover [1, 2, 3]. Our presentation in this chapter closely follows [4] and [5].

CRC Press eBooks•Mar 11, 2008•0 citations

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

Searching with a quantum computer

N. David Mermin

The nature of the search Suppose you know that exactly one n -bit integer satisfies a certain condition, and suppose you have a black-boxed subroutine that acts on the N = 2 n different n -bit integers, outputting 1 if the integer satisfies the condition and 0 otherwise. In the absence of any other information, to find the special integer you can do no better with a classical computer than to apply the subroutine repeatedly to different random numbers until you hit on the special one. If you apply it to M different integers the probability of your finding the special number is M/N . You must test ½ N different integers to have a 50% chance of success. If, however, you have a quantum computer with a subroutine that performs such a test, then you can find the special integer with a probability that is very close to 1 when N is large, using a method that calls the subroutine a number of times no greater than. This very general capability of quantum computers was discovered by Lov Grover, and goes under the name of Grover's search algorithm . Shor's period-finding algorithm and Grover's search algorithm, together with their various modifications and extensions, constitute the two masterpieces of quantum-computational software. One can think of Grover's black-boxed subroutine in various ways. The subroutine might perform a mathematical calculation to determine whether the input integer is the special one. Here is a simple example.

Cambridge University Press eBooks•Aug 30, 2007•0 citations

Strength and Weakness in Grover's Quantum Search Algorithm

Ahmed Younes

Grover's quantum search algorithm is considered as one of the milestone in the field of quantum computing. The algorithm can search for a single match in a database with $N$ records in $O(\sqrt{N})$ assuming that the item must exist in the database with quadratic speedup over the best known classical algorithm. This review paper discusses the performance of Grover's algorithm in case of multiple matches where the problem is expected to be easier. Unfortunately, we will find that the algorithm will fail for $M>3N/4$, where $M$ is the number of matches in the list.

arXiv:0811.4481•Nov 27, 2008•17 citations

Grover's Search Algorithm for Database Validation

Datapro Computers Pvt Ltd, Shravani Salapu

In my project I would have considered how the old search algorithms that are used when working with large unstructured data set end up taking linear time (O(N)) that in effect is the time that scales with the size of the data. These old ways get gradually sluggish, as everything gets bigger. Then I read about quantum computing, and especially Search Algorithm that was developed by Grover which is capable of quadratic speed-up with a complexity of O(sqrt(N)) of unstructured data. I created a hybrid system which fuses classical and quantum search applied on Flask as the web front end and Qiskit as the quantum one. This will enable me to compare the simple linear algorithm of searching through the list item-by-item with the quantum algorithm of Grover which uses superposition, a marking oracle to identify the desired item, and multiple amplitude amplification diffusion operators. The web page also accepts a student ID, and actually searches both simultaneously and allows me to tweak a depolarizing noise model so as to more closely mimic real quantum hardware. I measured such variables as the number of calls to the oracle, the number of qubits that I require, the quantum run time, and the number of measurements that I receive out of the quantum measurement. As the results indicate, the algorithm developed by Grover reduces the number of operations significantly compared to the classical one, and it must be emphasized that the algorithm remains quite effective even in the case of simulated noise. On the whole, it demonstrates that the classical and quantum components may be an efficient method to deal with the large search in the database.

•Aug 11, 2026•0 citations
Finding a phone number in a directory when one knows the name is easy; much harder is finding the name given the number. On average, a search algorithm will have to scan half the total number of entries. If the database or directory is extremely large, the search may be impossible with classical computers. New possibilities emerge, however, with quantum computing. As Brassard discusses in his Perspective, a new algorithm developed by L. K. Grover enables much faster searching of large databases if one uses a quantum computer.
Imagine a phone directory containing N names arranged in completely random order. In order to find someone's phone number with a 50% probability, any classical algorithm (whether deterministic or probabilistic) will need to look at a minimum of N/2 names. 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)) steps. The algorithm is within a small constant factor of the fastest possible quantum mechanical algorithm.
Suppose there is a stack of N unstructured files and we want to find a particular file (or files) out of the N files. To find someone’s phone number in a telephone directory is an easy structured datebase search problem, while to find a person’s name who has a particular phone number is a more difficult unstructured database seach problem, with which we are concerned in this chapter. It is required to take O(N) steps on average if a classical algorithm is employed. If we check the files one by one, we will hit the right file with probability 1/2 after N/2 files are examined. It turns out that this takes only O( √ N) steps with a quantum algorithm, first discovered by Grover [1, 2, 3]. Our presentation in this chapter closely follows [4] and [5].
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.
The nature of the search Suppose you know that exactly one n -bit integer satisfies a certain condition, and suppose you have a black-boxed subroutine that acts on the N = 2 n different n -bit integers, outputting 1 if the integer satisfies the condition and 0 otherwise. In the absence of any other information, to find the special integer you can do no better with a classical computer than to apply the subroutine repeatedly to different random numbers until you hit on the special one. If you apply it to M different integers the probability of your finding the special number is M/N . You must test ½ N different integers to have a 50% chance of success. If, however, you have a quantum computer with a subroutine that performs such a test, then you can find the special integer with a probability that is very close to 1 when N is large, using a method that calls the subroutine a number of times no greater than. This very general capability of quantum computers was discovered by Lov Grover, and goes under the name of Grover's search algorithm . Shor's period-finding algorithm and Grover's search algorithm, together with their various modifications and extensions, constitute the two masterpieces of quantum-computational software. One can think of Grover's black-boxed subroutine in various ways. The subroutine might perform a mathematical calculation to determine whether the input integer is the special one. Here is a simple example.
Grover's quantum search algorithm is considered as one of the milestone in the field of quantum computing. The algorithm can search for a single match in a database with NNN records in O(N)O(\sqrt{N})O(N​) assuming that the item must exist in the database with quadratic speedup over the best known classical algorithm. This review paper discusses the performance of Grover's algorithm in case of multiple matches where the problem is expected to be easier. Unfortunately, we will find that the algorithm will fail for M>3N/4M>3N/4M>3N/4, where MMM is the number of matches in the list.
In my project I would have considered how the old search algorithms that are used when working with large unstructured data set end up taking linear time (O(N)) that in effect is the time that scales with the size of the data. These old ways get gradually sluggish, as everything gets bigger. Then I read about quantum computing, and especially Search Algorithm that was developed by Grover which is capable of quadratic speed-up with a complexity of O(sqrt(N)) of unstructured data. I created a hybrid system which fuses classical and quantum search applied on Flask as the web front end and Qiskit as the quantum one. This will enable me to compare the simple linear algorithm of searching through the list item-by-item with the quantum algorithm of Grover which uses superposition, a marking oracle to identify the desired item, and multiple amplitude amplification diffusion operators. The web page also accepts a student ID, and actually searches both simultaneously and allows me to tweak a depolarizing noise model so as to more closely mimic real quantum hardware. I measured such variables as the number of calls to the oracle, the number of qubits that I require, the quantum run time, and the number of measurements that I receive out of the quantum measurement. As the results indicate, the algorithm developed by Grover reduces the number of operations significantly compared to the classical one, and it must be emphasized that the algorithm remains quite effective even in the case of simulated noise. On the whole, it demonstrates that the classical and quantum components may be an efficient method to deal with the large search in the database.