Dec 20, 2001 IBM and Stanford run Shor's algorithm on a 7-qubit computer to factor 15

Shor's algorithm was the main reason quantum computing had drawn so much attention, yet it had never been run. Even the smallest meaningful case requires several qubits working together through a long sequence of operations, well beyond the two-qubit machines of 1998.

At IBM's Almaden laboratory in California, Isaac Chuang's group, working with colleagues at Stanford, pushed NMR as far as it would go. They used a molecule synthesized for the purpose, in which seven atomic nuclei served as qubits, and controlled it with carefully timed radio-frequency pulses.

In December 2001 they reported in Nature that the molecule had found the prime factors of 15: 3 and 5. It was the simplest instance of Shor's algorithm, chosen so that a seven-qubit machine could manage it, and the answer was known in advance.

The result said nothing new about the number 15. What it showed was that the algorithm behaved on real hardware as Shor had predicted. It was also close to the ceiling of NMR, whose signal weakens with every qubit added: the method that ran the first quantum algorithms could not carry them much further.

Here we report an implementation of the simplest instance of Shor's algorithm: factorization of N = 15 (whose prime factors are 3 and 5). We use seven spin-1/2 nuclei in a molecule as quantum bits