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.
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.
Nevertheless, there is an increasing amount of investment in quantum computing by governments, established companies, and start-ups. 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.
