So what exactly is a quantum computer? The answer to this question encompasses quantum mechanics (QM), quantum information theory (QIT) and computer science (CS). For our purposes, we will focus on the core of what makes a quantum computer distinct from classical computers: „A quantum computer is a device that leverages specific properties described by quantum mechanics to perform computation. Quantum computers use quantum bits -- qubits -- instead of classical bits for computation.“
More concretely, to build a quantum computer we need a series of qubits each of which is able to be in state 0 or 1 (just like a classical bit), but also in a linear combination of 0 and 1. In fact, there is an infinite number of such linear combinations; so a qubit has far more representational power than a classical bit. In fact, just 55 or so of these qubits can perform certain calculations that even a computer with billions of traditional bits could not accomplish in a short amount of time.
The possibility that we can leverage quantum mechanics to compute in new and interesting ways has been hiding in plain sight since the field’s early days; the principles of superposition and entanglement can form the basis of a very powerful form of computation. The trick is to build such a system that we can easily manipulate and measure.
Benioff demonstrated the theoretical basis
While Richard Feynman is often credited with the conception of quantum computers, there were several researchers who anticipated this idea. In 1979, Paul Benioff, a young physicist at Argonne National Labs, submitted a paper entitled “The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines”. In this paper, Benioff demonstrated the theoretical basis for quantum computing and then suggested that such a computer could be built. Yuri Manin also laid out the core idea of quantum computing in his 1980 book Computable and Non-Computable. The book was written in Russian, however, and only translated years later.
In 1981, Feynman gave a lecture entitled “Simulating Physics with Computers”. In this talk, he argued that a classical system could not adequately represent a quantum mechanical system: „...nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical, and by golly it’s a wonderful problem, because it doesn’t look so easy…“
He then set out the features that a quantum computer should have to be useful. At the time of this lecture, however, it was unclear to Feynman and the physics community how one could build such a machine. Once Benioff, Manin and Feynman opened the doors, researchers began to investigate the nature of the algorithms that could be run on QCs. David Deutsch, a physicist at Oxford, suggested a more comprehensive framework for quantum computing in his 1985 paper. In this work, he describes in detail what a quantum algorithm would look like and anticipates that “one day it will become technologically possible to build quantum computers.”
Deutsch then went on to develop an example of an algorithm that would run faster on a quantum computer. He then further generalized this algorithm in collaboration with Richard Jozsa. This Deutsch-Jozsa algorithm made it clear that one day quantum computers would outpace even the biggest classical computers.
Now Peter Shor enters the scene. In 1994, Shor was a researcher in the mathematical division of Bell Labs. Shor studied the work of Deutsch, Jozsa, and others and realized he could construct an algorithm for factoring large numbers into two prime factors; factoring large numbers is believed to be intractable on a classical computer, but Shor’s factoring algorithm runs quickly on a quantum computer.