Nature, Vol.393, No.6681, 143-146, 1998
Experimental realization of a quantum algorithm
Quantum computers(1-5) can in principle exploit quantum-mechanical effects to perform computations (such as factoring large numbers or searching an unsorted database) more rapidly than classical computers(1,2,6-8), But noise, loss of coherence, and manufacturing problems make constructing large-scale quantum computers difficult(9-13). Although ion traps and optical cavities offer promising experimental approaches(14,15), no quantum algorithm has yet been implemented with these systems. Here we report the experimental realization of a quantum algorithm using a bulk nuclear magnetic resonance technique(16-18), in which the nuclear spins act as 'quantum bits'(19). The nuclear spins are particularly suited to this role because of their natural isolation from the environment. Our simple quantum computer solves a purely mathematical problem in fewer steps than is possible classically, requiring fewer (function calls' than a classical computer to determine the global properties of an unknown function.