Although quantum mechanics is linear, there are nevertheless quantum systems with multiple interacting particles in which the effective evolution of a single particle is governed by a nonlinear equation. This includes Bose-Einstein condensates, which are governed by the Gross-Pitaevskii equation, which is a cubic nonlinear Schrödinger equation with a term proportional to /[psi]/ ²[psi] scaling of Grover's algorithm. Since the Gross- Pitaevskii equation effectively approximates the multi- particle Schrödinger equation, for which Grover's algorithm is optimal, our result leads to a quantum information-theoretic bound on the number of particles needed for this approximation to hold, asymptotically. The Gross-Pitaevskii equation is not the only nonlinearity of the form f(/[psi]/²)[psi] that arises in effective equations for the evolution of real quantum physical systems, however : The cubic-quintic nonlinear Schrödinger equation describes light propagation in nonlinear Kerr media with defocusing corrections, and the logarithmic nonlinear Schrödinger equation describes Bose liquids under certain conditions. Analysis of computation with such systems yields some surprising results; for example, when time-measurement precision is included in the resource accounting, searching a "database'' when there is a single correct answer may be easier than searching when there are multiple correct answers. These results lead to quantum information-theoretic bounds on the physical resources required for these effective nonlinear theories to hold, asymptotically. Furthermore, strongly regular graphs, which have no global symmetry, are sufficiently complete for quantum search on them to asymptotically behave like unstructured search. Certain sufficiently complete graphs retain the improved runtime and resource scalings for some nonlinearities, so our scheme for nonlinear, analog quantum computation retains its benefits even when some structure is introduced