No label defined (Q4551209)

According to the authors, quantum search algorithms can be thought of as a resonance phenomenon, as illustrated by the following problem of clasical mechanics. \(N\) coupled pendulums, one of which is slightly shorter than the others, are given, and the problem is to determine which one is so. It is shown that by letting them oscillate on \(O(\sqrt N)\) cycles, a large portion of the energy can be transferred to the small pendulum of which the amplitude increases substantially. This property suggests a quantum search algorithm for the following archetype problem: a function \(f(x)\), \(x=1,2,\dots,N\) is known to be nonzero at a single point \(x_{0}\) and zero elsewhere. The problem is to determine \(x_{0}\). Applications to counting, classical mechanics and quantum mechanics are mentionned. For the entire collection see [Zbl 1077.81018].