Experimental implementation of a quantum random-walk search algorithm using strongly dipolar coupled spins
Dawei Lu, Jing Zhu, Ping Zou, Xinhua Peng, Yihua Yu, Shanmin Zhang, Qun Chen, Jiangfeng Du · Physical Review A · 2010
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.