From coupled pendulums to quantum search
Lov K. Grover, Anirvan M. Sengupta · 2002
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.