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• 35 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 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•13 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

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•9,689 citations

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.

InTech eBooks•Apr 26, 2011•1 citation

Grover's Search Algorithm for Database Validation

Dr CH Pavan Satish, K. Bhargavi, G.Vanaja +2 more

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.

International Journal of Engineering Research and Science & Technology•Mar 22, 2026•0 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 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.
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.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
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.