Repulsive interactions in Bose-Einstein condensates accelerate quantum search via quantum walk

The quantum search algorithm allows a distinct element in an $N$-element database to be located in a time that scales as $\sqrt{N}$, proved to be optimal. In the quantum walk approach to the search problem, a single quantum walker can locate a marked vertex on several graphs at the optimal time scaling. Unfortunately, the quantum walk on the physical case of two- and three-dimensional square lattices fails to improve on the $N$ scaling for a classical search. Particles with linear dispersion have been shown to improve the performance, with the time scaling as $\sqrt{N}\log(N)$ and optimal, respectively. We show that Bose-Einstein condensates (BECs) with on-site repulsive interactions, whose (Bogoliubov) quasiparticle excitations are characterized by a linear dispersion relation at long wavelengths, accelerate the quantum search on these regular lattices. The performance in three dimensions approaches the optimal time scaling, indicating that interacting BECs in optical lattices that are widely realized today can implement an efficient and genuinely interesting quantum algorithm.