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

Physical Review A

Classical analog of quantum search

Lov K. Grover, Anirvan M. Sengupta

Published Feb 27, 2002• 33 citations
Publisher

Abstract

Quantum search is a quantum-mechanical technique for searching N possibilities in only $\sqrt{N}$ steps. A similar algorithm applies in a purely classical setting when there are N oscillators, one of which is of a different resonant frequency. We could identify which one this is by measuring the oscillation frequency of each oscillator, a procedure that would take about N cycles. We show, how by coupling the oscillators together in a very simple way, it is possible to identify the different one in only $\sqrt{N}$ cycles. In case there are multiple oscillators of a different frequency, we can estimate the number of these in a time which is the square root of that required by the sampling method. The analog also leads to some energy routing algorithms for mechanical systems.

DOI
10.1103/physreva.65.032319

Related papers

From coupled pendulums to quantum search

Lov K. Grover, Anirvan M. Sengupta

Quantum search is a quantum mechanical technique for searching N possibilities in only √ N steps.There are several different perspectives from which one can get to the algorithm -Schrodinger's equation, antenna array, rotation in a two-dimensional Hilbert space, just to name a few.This paper gives a fresh perspective on the algorithm in terms of a resonance phenomenon which is implemented through classical coupled oscillators.Consider N oscillators, one of which is of a different resonant frequency.We could identify which one this is by measuring the oscillation frequency of each oscillator, a procedure that would take about N cycles.We show how, by coupling the oscillators together in a very simple way, it is possible to identify the different one in only √ N cycles.In case there are multiple oscillators of a different frequency, we can estimate the number of these in a time which is the square-root of that required by the sampling method.An extension of this technique to the quantum case leads to the quantum search & some novel algorithms.

Computational matematics series/Computational mathematics series•Feb 14, 2002•2 citations

From Coupled Pendulums to Quantum Search

Lov K. Grover, Anirvan M. Sengupta

Quantum search is a quantum mechanical technique for searching N possibilities in only sqrt(N) steps. This paper gives a fresh perspective on the algorithm in terms of a resonance phenomenon which is implemented through classical coupled oscillators. Consider N oscillators, one of which is of a different resonant frequency. We could identify which one this is by measuring the oscillation frequency of each oscillator, a procedure that would take about N cycles. We show how, by coupling the oscillators together in a very simple way, it is possible to identify the different one in only sqrt(N) cycles. An extension of this technique to the quantum case leads to the quantum search algorithm.

arXiv:quant-ph/0109123•Sep 25, 2001•0 citations

From coupled pendulums to quantum search

Lov K. Grover, Anirvan M. Sengupta

Abstract Quantum search is a quantum mechanical technique for searching N possibilities in only √ N steps. There are several different perspectives from which one can get to the algorithm - Schro¨dinger’s equation, antenna array, rotation in a two-dimensional Hilbert space, just to name a few. This paper gives a fresh perspective on the algorithm in terms of classical coupled oscillators. Consider N oscillators, one of which is of a different resonant frequency. We could identify which one this is by measuring the oscillation frequency of each oscillator, a procedure that would take about N cycles. We show how, by coupling the oscillators together in a very simple way, it is possible to identify the different one in only √ N cycles. In case there are multiple oscillators of a different frequency, we can estimate the number of these in a time which is the square-root of that required by the sampling method. An extension of this technique to the quantum case leads to the quantum search and some novel algorithms.

Chapman & Hall/CRC eBooks•Feb 14, 2002•8 citations

Complex Quantum Queries

Lov K. Grover

A quantum mechanical computer can search a database consisting of N items in O(sqrt(N)) elementary quantum queries (a query is defined as any question to the database to which a binary (YES/NO) answer is required; an elementary query is a query pertaining to only one of the N possible states). A classical computer would take at least O(N) elementary queries. This paper shows that a quantum mechanical algorithm that can query information relating to multiple states, can search the database in a single query. A classical algorithm will be limited to the information theoretic bound of at least O(log N)queries (which it would achieve by using a binary search). A similar result was recently independently obtained by Terhal & Smolin by a different method.

•Jun 3, 1997•0 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

A fast quantum mechanical algorithm for database search

Lov K. Grover

An unsorted database contains N records, of which just one satisfies a particular property.The problem is to identify that one record.Any classical algorithm, deterministic or probabilistic, will clearly take O (N) steps since on the average it will have to examine a large fraction of the N records.Quantum mechanical systems can do several operations simultaneously due to their wave like properties.This paper gives an O ( JN) step quantum mechanical algorithm for identifying that record.It is within a constant factor of the fastest possible quantum mechanical algorithm.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1996•8,830 citations
Quantum search is a quantum-mechanical technique for searching N possibilities in only N\sqrt{N}N​ steps. A similar algorithm applies in a purely classical setting when there are N oscillators, one of which is of a different resonant frequency. We could identify which one this is by measuring the oscillation frequency of each oscillator, a procedure that would take about N cycles. We show, how by coupling the oscillators together in a very simple way, it is possible to identify the different one in only N\sqrt{N}N​ cycles. In case there are multiple oscillators of a different frequency, we can estimate the number of these in a time which is the square root of that required by the sampling method. The analog also leads to some energy routing algorithms for mechanical systems.
Quantum search is a quantum mechanical technique for searching N possibilities in only √ N steps.There are several different perspectives from which one can get to the algorithm -Schrodinger's equation, antenna array, rotation in a two-dimensional Hilbert space, just to name a few.This paper gives a fresh perspective on the algorithm in terms of a resonance phenomenon which is implemented through classical coupled oscillators.Consider N oscillators, one of which is of a different resonant frequency.We could identify which one this is by measuring the oscillation frequency of each oscillator, a procedure that would take about N cycles.We show how, by coupling the oscillators together in a very simple way, it is possible to identify the different one in only √ N cycles.In case there are multiple oscillators of a different frequency, we can estimate the number of these in a time which is the square-root of that required by the sampling method.An extension of this technique to the quantum case leads to the quantum search & some novel algorithms.
Quantum search is a quantum mechanical technique for searching N possibilities in only sqrt(N) steps. This paper gives a fresh perspective on the algorithm in terms of a resonance phenomenon which is implemented through classical coupled oscillators. Consider N oscillators, one of which is of a different resonant frequency. We could identify which one this is by measuring the oscillation frequency of each oscillator, a procedure that would take about N cycles. We show how, by coupling the oscillators together in a very simple way, it is possible to identify the different one in only sqrt(N) cycles. An extension of this technique to the quantum case leads to the quantum search algorithm.
Abstract Quantum search is a quantum mechanical technique for searching N possibilities in only √ N steps. There are several different perspectives from which one can get to the algorithm - Schro¨dinger’s equation, antenna array, rotation in a two-dimensional Hilbert space, just to name a few. This paper gives a fresh perspective on the algorithm in terms of classical coupled oscillators. Consider N oscillators, one of which is of a different resonant frequency. We could identify which one this is by measuring the oscillation frequency of each oscillator, a procedure that would take about N cycles. We show how, by coupling the oscillators together in a very simple way, it is possible to identify the different one in only √ N cycles. In case there are multiple oscillators of a different frequency, we can estimate the number of these in a time which is the square-root of that required by the sampling method. An extension of this technique to the quantum case leads to the quantum search and some novel algorithms.
A quantum mechanical computer can search a database consisting of N items in O(sqrt(N)) elementary quantum queries (a query is defined as any question to the database to which a binary (YES/NO) answer is required; an elementary query is a query pertaining to only one of the N possible states). A classical computer would take at least O(N) elementary queries. This paper shows that a quantum mechanical algorithm that can query information relating to multiple states, can search the database in a single query. A classical algorithm will be limited to the information theoretic bound of at least O(log N)queries (which it would achieve by using a binary search). A similar result was recently independently obtained by Terhal & Smolin by a different method.
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.
An unsorted database contains N records, of which just one satisfies a particular property.The problem is to identify that one record.Any classical algorithm, deterministic or probabilistic, will clearly take O (N) steps since on the average it will have to examine a large fraction of the N records.Quantum mechanical systems can do several operations simultaneously due to their wave like properties.This paper gives an O ( JN) step quantum mechanical algorithm for identifying that record.It is within a constant factor of the fastest possible quantum mechanical algorithm.