Experimental implementation of a quantum random-walk search algorithm using strongly dipolar coupled spins

An important quantum search algorithm based on the quantum random walk performs an oracle search on a database of N items with O(root phN) calls, yielding a speedup similar to the Grover quantum search algorithm. The algorithm was implemented on a quantum information processor of three-qubit liquid-crystal nuclear magnetic resonance (NMR) in the case of finding 1 out of 4, and the diagonal elements' tomography of all the final density matrices was completed with comprehensible one-dimensional NMR spectra. The experimental results agree well with the theoretical predictions.