  We present an algorithm that uses a single ancilla qubit that can evolve
nonlinearly, and show how to use it to efficiently solve generic nonlinear
Schr\"odinger equations, including nonlocal Hartree equations and the
Navier-Stokes equation for an irrotational, non-viscous flow. We propose a
realization of such nonlinear qubits via spin-spin coupling of neutral atom
qubits to a Bose-Einstein condensate. The results suggest that the use of
nonlinear ancillas can provide substantial speedups compared to exclusively
linear qubit devices.
