Abstract
Quantum computers 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. But noise, loss of coherence, and manufacturing problems make constructing large-scale quantum computers difficult. Although ion traps and optical cavities offer promising experimental approaches, 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, in which the nuclear spins act as 'quantum bits'. 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.