Timeline of quantum computing and communication

1960s

1968/69/70

1969

1970s

1973

• Alexander Holevo's paper is published. The Holevo bound describes a limit of the quantity of classical information which is possible to quanta encode.
• Charles H. Bennett shows that computation can be done reversibly.

  1975

• R. P. Poplavskii publishes "Thermodynamical models of information processing" which shows the computational infeasibility of simulating quantum systems on classical computers, due to the superposition principle.
• Roman Stanisław Ingarden, a Polish mathematical physicist, submits the paper "Quantum Information Theory" in Reports on Mathematical Physics, vol. 10, pp. 43–72, published 1976. It is one of the first attempts at creating a quantum information theory, showing that Shannon information theory cannot directly be generalized to the quantum case, but rather that it is possible to construct a quantum information theory, which is a generalization of Shannon's theory, within the formalism of a generalized quantum mechanics of open systems and a generalized concept of observables.

  1980s

1980

• Paul Benioff describes the first quantum mechanical model of a computer. In this work, Benioff showed that a computer could operate under the laws of quantum mechanics by describing a Schrödinger equation description of Turing machines, laying a foundation for further work in quantum computing. The paper was submitted in June 1979 and published in April 1980.
• Yuri Manin briefly motivates the idea of quantum computing.
• Tommaso Toffoli introduces the reversible Toffoli gate, which is functionally complete for reversible classical computation.

  1981

1982

• Paul Benioff further develops his original model of a quantum mechanical Turing machine.
• William Wootters and Wojciech H. Zurek, and independently Dennis Dieks rediscover the no-cloning theorem of James L. Park.

  1984

1985

• David Deutsch, at the University of Oxford, England, describes 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.
• Asher Peres points out the need for quantum error correction schemes and discusses a repetition code for amplitude errors.
• John Clarke, Michel Devoret and John M. Martinis demonstrate quantized energy levels in a Josephson junction.

  1988

• Yoshihisa Yamamoto and K. Igeta propose the first physical realization of a quantum computer, including Feynman's CNOT gate. Their approach uses atoms and photons and is the progenitor of modern quantum computing and networking protocols using photons to transmit qubits and atoms to perform two-qubit operations.

  1989

• Gerard J. Milburn proposes a quantum-optical realization of a Fredkin gate.
• Bikas Chakrabarti & collaborators from Saha Institute of Nuclear Physics, Kolkata, India, propose that quantum fluctuations could help explore rugged energy landscapes by escaping from local minima of glassy systems having tall but thin barriers by tunneling, suggesting the effectiveness of quantum annealing over classical simulated annealing.

  1990s

1991

1992

• David Deutsch and Richard Jozsa propose a computational problem that can be solved efficiently with the deterministic Deutsch–Jozsa algorithm on a quantum computer, but for which no deterministic classical algorithm is possible. This was perhaps the earliest result in the computational complexity of quantum computers, proving that they were capable of performing some well-defined computation more efficiently than any classical computer.
• Ethan Bernstein and Umesh Vazirani propose the Bernstein–Vazirani algorithm. It is a restricted version of the Deutsch–Jozsa algorithm where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function. The Bernstein–Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP.
• Research groups at Max Planck Institute of Quantum Optics and shortly after at NIST experimentally realize the first crystallized strings of laser-cooled ions. Linear ion crystals constitute the qubit basis for most quantum computing and simulation experiments with trapped ions.

  1993

1994

• Peter Shor, at AT&T's Bell Labs in New Jersey, publishes Shor's algorithm. It would allow a quantum computer to factor large integers quickly. It solves both the factoring problem and the discrete log problem. The algorithm can theoretically break many of the cryptosystems in use today. Its invention sparked tremendous interest in quantum computers.
• The first United States Government workshop on quantum computing is organized by NIST in Gaithersburg, Maryland, in autumn.
• Isaac Chuang and Yoshihisa Yamamoto propose a quantum-optical realization of a quantum computer to implement Deutsch's algorithm. Their work introduced dual-rail encoding for photonic qubits.
• In December, Ignacio Cirac, at University of Castilla–La Mancha at Ciudad Real, and Peter Zoller at the University of Innsbruck propose an experimental realization of the controlled NOT gate with cold trapped ions.

  1995

• The first United States Department of Defense workshop on quantum computing and quantum cryptography is organized by United States Army physicists Charles M. Bowden, Jonathan Dowling, and Henry O. Everitt; it took place in February at the University of Arizona in Tucson.
• Peter Shor proposes the first schemes for quantum error correction.
• Christopher Monroe and David J. Wineland at NIST experimentally realize the first quantum logic gate – the controlled NOT gate – with trapped ions, following the Cirac-Zoller proposal.
• Independently, Subhash Kak and Ronald Chrisley propose the first quantum neural network.

  1996

• Lov Grover, at Bell Labs, invents the quantum database search algorithm. The quadratic speedup is not 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 can be solved by random, brute-force search, may take advantage of this quadratic speedup in the number of search queries.
• The United States Government, particularly in a joint partnership of the Army Research Office and the National Security Agency, issues the first public call for research proposals in quantum information processing.
• Andrew Steane designs Steane code for error correction.
• David DiVincenzo, of IBM, proposes a list of minimal requirements for creating a quantum computer, now called DiVincenzo's criteria.
• Seth Lloyd proves Feynman's conjecture on quantum simulation.

  1997

• David G. Cory, Amr Fahmy and Timothy Havel, and at the same time Neil Gershenfeld and Isaac Chuang at MIT publish the first papers realizing gates for quantum computers based on bulk nuclear spin resonance, or thermal ensembles. The technology is based on a nuclear magnetic resonance machine, which is similar to the medical magnetic resonance imaging machine.
• Alexei Kitaev describes the principles of topological quantum computation as a method for dealing with the problem of decoherence.
• Daniel Loss and David DiVincenzo propose the Loss-DiVincenzo quantum computer, using as qubits the intrinsic spin-1/2 degree of freedom of individual electrons confined to quantum dots.

  1998

• The first experimental demonstration of a quantum algorithm is reported. A working 2-qubit NMR quantum computer was used to solve Deutsch's problem by Jonathan A. Jones and Michele Mosca at Oxford University and shortly after by Isaac L. Chuang at IBM's Almaden Research Center, in California, and Mark Kubinec and the University of California, Berkeley together with coworkers at Stanford University in California and MIT in Massachusetts.
• The first working 3-qubit NMR computer is reported.
• Bruce Kane proposes a silicon-based nuclear spin quantum computer, using nuclear spins of individual phosphorus atoms in silicon as the qubits and donor electrons to mediate the coupling between qubits.
• The first execution of Grover's algorithm on an NMR computer is reported.
• Hidetoshi Nishimori & colleagues from Tokyo Institute of Technology show that a quantum annealing algorithm can perform better than classical simulated annealing under certain conditions.
• Daniel Gottesman and Emanuel Knill independently prove that a certain subclass of quantum computations can be efficiently emulated with classical resources.