A Classical Analog of Quantum Search

Quantum search is a quantum mechanical technique for searing N possibilities in only O( sq rt. 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 O(N) cycles. 

We show how by coupling the the oscillators together in a very simple way and letting them oscillate, it is possible to identify the different one in only O( sq. rt. N) cycles. In case there are multiple oscillators of a different frequency, we can count these in a time which is the square-root of that required by the sampling method. 

The same technique applies in quantum mechanical setting with trapped particles interacting with photons or phonons such as in an optical cavity or an ion trap. The algorithm in this paper is of interest both for its own sake and also for the insight it provides into the quantum search algorith .