Abstract
The optimal runtime of a quantum computer searching a database is typically
cited as the square root of the number of items in the database, which is
famously achieved by Grover's algorithm. With parallel oracles, however, it is
possible to search faster than this. We consider a many-body quantum system
that naturally effects parallel queries, and we show that its parameters can be
tuned to search a database in constant time, assuming a sufficient number of
interacting particles. In particular, we consider Bose-Einstein condensates
with pairwise and three-body interactions in the mean-field limit, which
effectively evolve by a nonlinear Schr\"odinger equation with cubic and quintic
nonlinearities. We solve the unstructured search problem formulated as a
continuous-time quantum walk searching the complete graph in constant time.
Depending on the number of marked vertices, however, the success probability
can peak sharply, necessitating high precision time measurement to observe the
system at this peak. Overcoming this, we prove that the relative coefficients
of the cubic and quintic terms can be tuned to eliminate the need for high
time-measurement precision by widening the peak in success probability or
having it plateau. Finally, we derive a lower bound on the number of atoms
needed for the many-body system to evolve by the effective nonlinearity.