This is a timeline of quantum computing and communication.
1930s
1936
Erwin Schrödinger publishes a theorem setting the basis for quantum steering and the limits of quantum state purification. The theorem remained uncredited even after multiple expansions and rediscoveries.
1960s 1968/69/70 Stephen Wiesner invents conjugate coding.
1969 13 June – James L. Park (Washington State University, Pullman)'s paper is received by Foundations of Physics, in which he describes the non-possibility of disturbance in a quantum transition state in the context of a disproof of quantum jumps in the Bohr model of the atom.
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" (in Russian) 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 (the so-called semi-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,Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version: which (together with initialized ancilla bits) is functionally complete for reversible classical computation.
1981 At the first Conference on the Physics of Computation, held at the Massachusetts Institute of Technology (MIT) in May, Paul Benioff and Richard Feynman give talks on quantum computing. Benioff's talk built on his earlier 1980 work showing that a computer can operate under the laws of quantum mechanics. The talk was titled "Quantum mechanical Hamiltonian models of discrete processes that erase their own histories: application to Turing machines". In Feynman's talk, he observed that it appeared to be impossible to efficiently simulate the evolution of a quantum nature system on a classical computer, and he proposed a basic model for a quantum computer. Feynman's conjecture on a quantum simulating computer, published 1982, understood as – the reality of quantum mechanics expressed as an effective quantum system necessitates quantum computers, is conventionally accepted as a beginning of quantum computing.
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 Charles Bennett and Gilles Brassard employ Wiesner's conjugate coding for distribution of cryptographic keys. Reprinted as
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 (Church–Turing thesis), 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 (instead of climbing over using thermal excitations), suggesting the effectiveness of quantum annealing over classical simulated annealing.
1990s 1991 Artur Ekert at the University of Oxford, proposes entanglement-based secure communication.
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 (Garching) and shortly after at NIST (Boulder) 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 Daniel R. Simon, at Université de Montréal, Quebec, Canada, invents an oracle problem, Simon's problem, for which a quantum computer would be exponentially faster than a conventional computer. This algorithm introduces the main ideas which were then developed in Peter Shor's factorization algorithm.
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 (Boulder, Colorado) 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 (now part of the Army Research Laboratory) 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 (NMR) 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 (Gottesman–Knill theorem).
1999 Samuel L. Braunstein and collaborators show that none of the bulk NMR experiments performed to date contain any entanglement; the quantum states being too strongly mixed. This is seen as evidence that NMR computers would likely not yield a benefit over classical computers. It remains an open question, however, whether entanglement is necessary for quantum computational speedup. Gabriel Aeppli, Thomas Rosenbaum and colleagues demonstrate experimentally the basic concepts of quantum annealing in a condensed matter system. Yasunobu Nakamura and Jaw-Shen Tsai demonstrate that a superconducting circuit can be used as a qubit.
2000s 2000 Arun K. Pati and Samuel L. Braunstein prove the quantum no-deleting theorem. This is dual to the no-cloning theorem which shows that one cannot delete a copy of an unknown qubit. Together with the stronger no-cloning theorem, the no-deleting theorem has the implication that quantum information can neither be created nor be destroyed. The first working 5-qubit NMR computer is demonstrated at the Technical University of Munich, Germany.