All Abstracts | Poster Abstracts | Talk Abstracts

Nonlinear Quantum Search

Thomas Wong, UC San Diego

(Session 7b : Friday from 3:30 - 4:00)

Abstract. Abrams & Lloyd (1998) showed that a nonlinear quantum theory could lead to unreasonable computational power, solving NP-Complete problems in polynomial time. To do so, they used a hard nonlinearity, which led to dynamics in which 0 amplitude for some state was an unstable fixed point, and thus extremely susceptible to noise. Instead, we consider a physically motivated, softer nonlinearity of the Gross-Pitaevskii type, which leads to dynamics that are only marginally unstable at 0. We show that with such a nonlinearity the unstructured search problem can be solved in constant time. Our algorithm, however, requires increasingly precise time measurement with increasing problem size, N, but since solving the problem more slowly reduces the necessary measurement precision, the resource requirements can be jointly optimized to scale as N^1/4. This is a significant, but not unreasonable, improvement over the N^1/2 scaling of Grover's algorithm. We conclude by considering the implications of such nonlinear dynamics arising as an approximation to the quantum evolution of multiple particles, and we arrive at a quantum information-theoretic argument for the number of particles needed for the Gross-Pitaevskii equation to accurately describe the linear, multi-particle dynamics of a Bose-Einstein condensate. This is joint work with David Meyer.