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

Computational matematics series/Computational mathematics series

From coupled pendulums to quantum search

Lov K. Grover, Anirvan M. Sengupta

Published Feb 14, 2002• 2 citations
Publisher

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 -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.

DOI
10.1201/9781420035377.pt3

Related papers

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

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

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

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

Quantum Search with Variable Times

Andris Ambainis

Since Grover’s seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items x 1,…,x n and we would like to find i:x i =1. We consider a new variant of this problem in which evaluating x i for different i may take a different number of time steps. Let t i be the number of time steps required to evaluate x i . If the numbers t i are known in advance, we give an algorithm that solves the problem in $O(\sqrt{t_{1}^{2}+t_{2}^{2}+\ldots+t_{n}^{2}})$ steps. This is optimal, as we also show a matching lower bound. The case, when t i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.

Theory of Computing Systems•Jun 2, 2009•40 citations
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 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\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.
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.
Since Grover’s seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items x 1,…,x n and we would like to find i:x i =1. We consider a new variant of this problem in which evaluating x i for different i may take a different number of time steps. Let t i be the number of time steps required to evaluate x i . If the numbers t i are known in advance, we give an algorithm that solves the problem in O(t12+t22+…+tn2)O(\sqrt{t_{1}^{2}+t_{2}^{2}+\ldots+t_{n}^{2}})O(t12​+t22​+…+tn2​​) steps. This is optimal, as we also show a matching lower bound. The case, when t i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.