Nonlinear (quantum) search*

Farhi and Gutmann's ``analog analogue'' of Grover's algorithm is simply the Schr\"odinger equation for the evolution of a particle hopping among $N$ sites, one of which is marked by the presence of a potential well. When the particle is initialized in a state with equal amplitude at each site, after $O(N^{1/2})$ time its amplitude is concentrated at the marked site, and a measurement will detect it there with probability 1. A nonlinear Schr\"odinger equation with a cubic nonlinear term arises as the Gross-Pitaevskii equation approximately describing the collective evolution of the many quantum particles in a Bose-Einstein condensate (BEC), a novel---but experimentally observed---form of matter in which all the particles are in the same quantum state. Including such a nonlinear term into the continuous time evolution of the particle hopping among $N$ sites, one of which is marked, constitutes a nonlinear (quantum) search algorithm. If the relative strength of the nonlinear term varies correctly with time, the state concentrates at the marked site at time $\pi/2$ for {\sl any\/} $N$. This is a {\sl constant time\/} algorithm---immensely faster than $O(N^{1/2})$. The state concentrates at the marked site for shorter and shorter times as $N\to\infty$, however, which means the measurement time must be determined with increasing precision. Accounting correctly for the physical resources necessary to measure time sufficiently precisely, the total resources for this algorithm scale as $O(N^{1/2})$, no better than Farhi and Gutmann's linear quantum algorithm. But jointly optimizing these resource requirements results in an overall scaling of $N^{1/4}$. This is a significant, but not unreasonable, improvement over the $N^{1/2}$ scaling of the linear algorithm. Since the Gross-Pitaevskii equation approximates the multi-particle (linear) Schr\"odinger equation, for which Grover's algorithm is optimal, this gives a quantum information-theoretic lower bound on the number of particles needed for the approximation to hold, asymptotically. This is joint work with Tom Wong.