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

arXiv:quant-ph/0109123

From Coupled Pendulums to Quantum Search

Lov K. Grover, Anirvan M. Sengupta

Published Sep 25, 2001• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0109123

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

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

Classical analog of quantum search

Lov K. Grover, Anirvan M. Sengupta

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.

Physical Review A•Feb 27, 2002•33 citations

From Schrödinger’s equation to the quantum search algorithm

Lov K. Grover

The quantum search algorithm is a technique for searching N possibilities in only O(N) steps. Although the algorithm itself is widely known, not so well known is the series of steps that first led to it; these are quite different from any of the generally known forms of the algorithm. This paper describes these steps, which start by discretizing Schrödinger’s equation. This paper also provides a self-contained introduction to quantum computing algorithms from a new perspective.

American Journal of Physics•Jul 1, 2001•171 citations

A Coupled Oscillator Model for Grover's Quantum Database Search Algorithm

Aavishkar A. Patel

Grover's database search algorithm is the optimal algorithm for finding a desired object from an unsorted collection of items. Although it was discovered in the context of quantum computation, it is simple and versatile enough to be implemented using any physical system that allows superposition of states, and several proposals have been made in the literature. I study a mechanical realisation of the algorithm using coupled simple harmonic oscillators, and construct its physical model for the simplest case of four identical oscillators. The identification oracle is implemented as an elastic reflection of the desired oscillator, and the overrelaxation operation is realised as evolution of the system by half an oscillation period. I derive the equations of motion, and solve them both analytically and by computer simulation. I extend the ideal case analysis and explore the sensitivity of the algorithm to changes in the initial conditions, masses of springs and damping. The amplitude amplification provided by the algorithm enhances the energy of the desired oscillator, while running the algorithm backwards spreads out the energy of the perturbed oscillator among its partners. The former (efficient focusing of energy into a specific oscillator) can have interesting applications in processes that need crossing of an energy threshold for completion, and can be useful in nanotechnological devices and catalysis. The latter (efficient redistribution of energy) can be useful in processes requiring rapid dissipation of energy, such as shock-absorbers and vibrational shielding. I present some tentative proposals.

arXiv:0711.4733•Nov 29, 2007•3 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
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.
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.
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.
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.
Grover's database search algorithm is the optimal algorithm for finding a desired object from an unsorted collection of items. Although it was discovered in the context of quantum computation, it is simple and versatile enough to be implemented using any physical system that allows superposition of states, and several proposals have been made in the literature. I study a mechanical realisation of the algorithm using coupled simple harmonic oscillators, and construct its physical model for the simplest case of four identical oscillators. The identification oracle is implemented as an elastic reflection of the desired oscillator, and the overrelaxation operation is realised as evolution of the system by half an oscillation period. I derive the equations of motion, and solve them both analytically and by computer simulation. I extend the ideal case analysis and explore the sensitivity of the algorithm to changes in the initial conditions, masses of springs and damping. The amplitude amplification provided by the algorithm enhances the energy of the desired oscillator, while running the algorithm backwards spreads out the energy of the perturbed oscillator among its partners. The former (efficient focusing of energy into a specific oscillator) can have interesting applications in processes that need crossing of an energy threshold for completion, and can be useful in nanotechnological devices and catalysis. The latter (efficient redistribution of energy) can be useful in processes requiring rapid dissipation of energy, such as shock-absorbers and vibrational shielding. I present some tentative proposals.
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.