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

Abstract

An important quantum search algorithm based on the quantum random walk performs an oracle search on a database of $N$ items with $O(\sqrt{\mathit{ph}N})$ 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.