Nonlinear variants of quantum mechanics can solve tasks that are impossible

in standard quantum theory, such as perfectly distinguishing nonorthogonal

states. Here we derive the optimal protocol for distinguishing two states of a

qubit using the Gross-Pitaevskii equation, a model of nonlinear quantum

mechanics that arises as an effective description of Bose-Einstein condensates.

Using this protocol, we present an algorithm for unstructured search in the

Gross-Pitaevskii model, obtaining an exponential improvement over a previous

algorithm of Meyer and Wong. This result establishes a limitation on the

effectiveness of the Gross-Pitaevskii approximation. More generally, we

demonstrate similar behavior under a family of related nonlinearities, giving

evidence that the ability to quickly discriminate nonorthogonal states and

thereby solve unstructured search is a generic feature of nonlinear quantum

mechanics.