Jan 1998 First quantum algorithms run on small NMR quantum computers

The NIST gate was a single step. A computation chains many such steps into an algorithm, and by 1997 nobody had run one on quantum hardware. Trapped ions and atoms in optical cavities had produced individual gates, but not yet a complete calculation.

A different route came from chemistry. In 1996 and 1997 two groups independently proposed using the nuclei of atoms within ordinary molecules as qubits. Each nucleus behaves like a tiny compass needle: in a strong field it lines up with it or against it, and pulses of radio waves can turn it. This is nuclear magnetic resonance (NMR), the physics behind hospital MRI scanners. A sample of liquid holds an enormous number of identical molecules, each a copy of the same small computer, and the instrument reads their combined signal.

In January 1998 the first quantum algorithms ran on such machines. At Oxford, Jonathan Jones and Michele Mosca used cytosine, one of the bases of DNA; Isaac Chuang's team at IBM, Stanford and MIT used chloroform, about a billion billion molecules in half a millilitre. Each machine had two qubits. Both solved Deutsch's problem in its simplest form: a hidden function turns one bit into another, and the task is to decide whether it always gives the same output. A classical computer needs two evaluations of the function; the quantum algorithm needs one.

The problem is deliberately trivial; what mattered was that quantum hardware had run a program from start to finish and returned the correct answer. By May the Oxford group had also run Grover's search algorithm. NMR, however, had a limit that its own proponents pointed out: the molecules start out in nearly random orientations, and the usable signal shrinks exponentially as qubits are added. The method could not be scaled much beyond a handful of qubits.

We demonstrate the use of an NMR quantum computer based on the pyrimidine base cytosine, and the implementation of a quantum algorithm to solve Deutsch's problem.