A Classical Analog of Quantum Search

Quantum search is a quantum mechanical technique for searching N possibilities in only O (square root of 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 oscillators together in a very simple way and letting them oscillate, it is possible to identify the different one in only O (square root of N) cycles. In case there are multiple oscillators of a different frequency, we can could these in a time which is the square-root of that required by the sampling method. The same technique applies in quantum mechanical settings 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 algorithm.