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

Chapman & Hall/CRC eBooks

From coupled pendulums to quantum search

Lov K. Grover, Anirvan M. Sengupta

Published Feb 14, 2002• 8 citations
Publisher

Abstract

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.

DOI
10.1201/9781420035377-6

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

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•35 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•176 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.

arXiv:quant-ph/0609168•Theory of Computing Systems•Jun 2, 2009•61 citations

Quantum Search Algorithm

The quantum search algorithm was discovered by L. K. Grover in 1997, and is called Grover’s algorithm after his name. Let us consider how to find elements marked by a certain symbol out of a database consisting of N elements (say, multi-million elements). This problem is similar to how to find the name of the person from a telephone book knowing only his/her telephone number. This search takes by far more time than finding the phone number from the name of the person. The difference comes from the structure of the telephone book. In the telephone book, the names are arranged in the alphabetical order and constitute the structured database, while phone numbers do not form any structure in the telephone book. In classical computers, when we search one target element from the database with N elements, we need N/ 2 trials on average. Grover showed using the quantum search algorithm that N trials will be enough on average to find the target element from the database with N elements. Shor’s quantum computation algorithm was an epoch-making algorithm which made possible to solve the factorization problem in polynomial time, while the classical computers need exponentially increasing time to solve it. In comparison, Grover’s algorithm makes the data search possible by O ( N ) computation time, while it takes O ( N ) computation time by the classical computers. Concerning the reduction of computing time, Grover’s algorithm may look less powerful than Shor’s algorithm. However, it has good potentiality of application in the wide area such as NP-complete problems and structured databases.

WORLD SCIENTIFIC eBooks•Sep 24, 2020•0 citations

Fast quantum search algorithms in protein sequence comparisons: Quantum bioinformatics

Lloyd C. L. Hollenberg

Quantum search algorithms are considered in the context of protein sequence comparison in bioinformatics. Given a sample protein sequence of length m (i.e., m residues), the problem considered is to find an optimal match in a large database containing N residues. Initially, Grover's quantum search algorithm is applied to a simple illustrative case-namely, where the database forms a complete set of states over the 2(m) basis states of a m qubit register, and thus is known to contain the exact sequence of interest. This example demonstrates explicitly the typical O(square root of [N]) speedup on the classical O(N) requirements. An algorithm is then presented for the (more realistic) case where the database may contain repeat sequences, and may not necessarily contain an exact match to the sample sequence. In terms of minimizing the Hamming distance between the sample sequence and the database subsequences the algorithm finds an optimal alignment, in O(square root of [N]) steps, by employing an extension of Grover's algorithm, due to Boyer et al. for the case when the number of matches is not a priori known.

arXiv:quant-ph/0002076•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Nov 1, 2000•36 citations
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.
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.
The quantum search algorithm was discovered by L. K. Grover in 1997, and is called Grover’s algorithm after his name. Let us consider how to find elements marked by a certain symbol out of a database consisting of N elements (say, multi-million elements). This problem is similar to how to find the name of the person from a telephone book knowing only his/her telephone number. This search takes by far more time than finding the phone number from the name of the person. The difference comes from the structure of the telephone book. In the telephone book, the names are arranged in the alphabetical order and constitute the structured database, while phone numbers do not form any structure in the telephone book. In classical computers, when we search one target element from the database with N elements, we need N/ 2 trials on average. Grover showed using the quantum search algorithm that N trials will be enough on average to find the target element from the database with N elements. Shor’s quantum computation algorithm was an epoch-making algorithm which made possible to solve the factorization problem in polynomial time, while the classical computers need exponentially increasing time to solve it. In comparison, Grover’s algorithm makes the data search possible by O ( N ) computation time, while it takes O ( N ) computation time by the classical computers. Concerning the reduction of computing time, Grover’s algorithm may look less powerful than Shor’s algorithm. However, it has good potentiality of application in the wide area such as NP-complete problems and structured databases.
Quantum search algorithms are considered in the context of protein sequence comparison in bioinformatics. Given a sample protein sequence of length m (i.e., m residues), the problem considered is to find an optimal match in a large database containing N residues. Initially, Grover's quantum search algorithm is applied to a simple illustrative case-namely, where the database forms a complete set of states over the 2(m) basis states of a m qubit register, and thus is known to contain the exact sequence of interest. This example demonstrates explicitly the typical O(square root of [N]) speedup on the classical O(N) requirements. An algorithm is then presented for the (more realistic) case where the database may contain repeat sequences, and may not necessarily contain an exact match to the sample sequence. In terms of minimizing the Hamming distance between the sample sequence and the database subsequences the algorithm finds an optimal alignment, in O(square root of [N]) steps, by employing an extension of Grover's algorithm, due to Boyer et al. for the case when the number of matches is not a priori known.