Follow
Quantum computing is the study of a non-classical model of computation. Whereas traditional models of computing such as the Turing machine or Lambda calculus rely on "classical" representations of computational memory, a quantum computation could transform the memory into a quantum superposition of possible classical states. A quantum computer is a device that could perform such computation.
Quantum computing began in the early 1980s when physicist Paul Benioff proposed a quantum mechanical model of the Turing machine. Richard Feynman and Yuri Manin later suggested that a quantum computer could perform simulations that are out of reach for regular computers. In 1994, Peter Shor developed a polynomial-time quantum algorithm for factoring integers. This was a major breakthrough in the subject: an important method of asymmetric key exchange known as RSA is based on the belief that factoring integers is computationally difficult. The existence of a polynomial-time quantum algorithm proves that one of the most widely used cryptographic protocols is vulnerable to an adversary who possesses a quantum computer.
Experimental efforts towards building a quantum computer began after a slew of results known as fault-tolerance threshold theorems. These theorems proved that a quantum computation could be efficiently corrected against the effects of large classes of physically realistic noise models. One early result demonstrated parts of Shor's algorithm in a liquid-state nuclear magnetic resonance experiment. Other notable experiments have been performed in superconducting systems, ion-traps, and photonic systems.
Despite rapid and impressive experimental progress, most researchers believe that "fault-tolerant quantum computing [is] still a rather distant dream". On 23 October 2019, Google AI, in partnership with the U.S. National Aeronautics and Space Administration (NASA), officially claimed that its Sycamore quantum processor completed in 200 seconds a task the equivalent of which would take a state-of-the-art supercomputer approximately 10,000 years to complete. In response, one prominent researcher declared that a quantum computing revolution equivalent to the modern digital computer will require "immense engineering, and probably further insights as well." There is an increasing amount of investment in quantum computing by governments, established companies, and start-ups. Current research focuses on building and using near-term intermediate-scale devices and demonstrating quantum supremacy alongside the long-term goal of building and using a powerful and error-free quantum computer.
The field of quantum computing is closely related to quantum information science, which includes quantum cryptography and quantum communication.