Quantum Computing Concept
Feynman (1981) noted that classical computers cannot efficiently simulate quantum systems; Deutsch (1985) defined a universal quantum computer, the model behind Shor's algorithm and all later hardware.
Open in the interactive tree →Paul Benioff (1980) and Yuri Manin (1980) had sketched quantum models of computation. At the first Physics of Computation conference at MIT in May 1981, Richard Feynman observed that simulating a quantum system on a classical computer seems to need exponentially growing effort, and proposed a basic model of a computer that itself obeys quantum mechanics. In 1985 David Deutsch at Oxford published a quantum Turing machine in the Proceedings of the Royal Society and argued that such a machine could simulate any other quantum computer with at most a polynomial slowdown.
Prerequisites
- Quantum Mechanics1925Quantum systems are the thing to be simulated, and the physics a new machine would use.
- Turing Machine1936Deutsch rebuilt the Turing machine on quantum rules.
- Programmable Computer (Zuse Z3)1941Feynman's argument is about what classical computers cannot simulate.
- Bell Test of Entanglement1964Feynman argued with Bell-type correlations that classical machines cannot imitate quantum behavior.
Unlocks
- Shor's Algorithm (Quantum Factoring)1994Shor's algorithm is written for the quantum-computer model Deutsch defined.