Timeline of quantum computing
1981 - Richard Feynman gave the first proposal for using quantum phenomena
to perform computations. The speech was entitled "There's Plenty of Room at
the Bottom". It was in a talk he gave at the First Conference on the Physics
of Computation at MIT. He pointed out that it would probably take a
classical computer an extremely long time to simulate a simple experiment in
quantum physics. If so, then simple quantum systems are essentially
performing huge calculations all the time. It might even be possible to
harness that for something useful.
1985 - David Deutsch, at the University of Oxford, described the first
universal quantum computer. Just as a universal Turing machine can simulate
any other Turing machine efficiently, so the universal quantum computer is
able to simulate any other quantum computer with at most a polynomial
slowdown. This raised the hope that a simple device might be able to perform
many different quantum algorithms.
1994 - Peter Shor, at AT&T's Bell Labs in New Jersey, discovered a
remarkable algorithm. It allowed a quantum computer to factor large integers
quickly. It solved both the factoring problem and the discrete log problem.
Shor's algorithm could theoretically break many of the cryptosystems in use
today. Its invention sparked a tremendous interest in quantum computers,
even outside the physics community.
1995 - Shor proposed the first scheme for quantum error correction. This is
an approach to making quantum computers that can compute with large numbers
of qubits for long periods of time. Errors are always introduced by the
environment, but quantum error correction might be able to overcome those
errors. This could be a key technology for building large-scale quantum
computers that work. These early proposals had a number of limitations. They
could correct for some errors, but not errors that occur during the
correction process itself. A number of improvements have been suggested, and
active research on this continues. An alternative to quantum error
correction has been found. Instead of actively correcting the errors induced
by the interaction with the environment, special states that are immune to
the errors can be used. This approach, known as decoherence free subspaces,
assumes that there is some symmetry in the computer-environment interaction.
1996 - Lov Grover, at Bell Labs, invented the quantum database search
algorithm. The quadratic speedup isn't as dramatic as the speedup for
factoring, discrete logs, or physics simulations. However, the algorithm can
be applied to a much wider variety of problems. Any problem that had to be
solved by random, brute-force search, could now have a quadratic speedup.
1997 - David Cory, A.F. Fahmy and Timothy Havel, and at the same time Neil
Gershenfeld and Isaac Chuang at MIT published the first papers on quantum
computers based on bulk spin resonance, or thermal ensembles. The computer
is actually a single, small molecule, which stores qubits in the spin of its
protons and neutrons. Trillions of trillions of these can float in a cup of
water. That cup is placed in a nuclear magnetic resonance machine, similar
to the the magnetic resonance imaging machines used in hospitals. This
room-temperature (thermal) collection of molecules (ensemble) has massive
amounts of redundancy, which allows it to maintain coherence for thousands
of seconds, much better than many other proposed systems.
1998 - First working 2-qubit NMR computer demonstrated at University of
1999 - First working 3-qubit NMR computer demonstrated at IBM's Almaden
Research Center. First execution of Grover's algorithm.
2000 - First working 5-qubit NMR computer demonstrated at IBM's Almaden
Research Center. First execution of order finding (part of Shor's
2001 - First working 7-qubit NMR computer demonstrated at IBM's Almaden
Research Center. First execution of Shor's algorithm. The number 15 was
factored using 1018 identical molecules, each containing 7 atoms.