David Meyer, University of California, San Diego
Abstract
Abrams & Lloyd (1998) showed that a nonlinear quantum mechanics 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. We consider, instead, 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. This is joint work with Tom Wong.