Lecture 1: Quantum Computing
Shortly after quantum mechanics was first formulated around 1930, the strangeness of the theory became evident. It took over 50 years, however, for people to realize just how pervasive its strangeness was.
Now, we know that information theory, the theory of computation, and the theory of cryptography all change substantially when we account for quantum mechanics. This strangeness can be used to accomplish tasks with quantum information processing that are not possible classically.
One example—the one that really drew attention to this phenomenon—was my discovery that quantum computers can factor large numbers into primes in manageable time frames, something that digital computers would take an inordinate amount of time to do.
The rapid factorization is only one example of the many strange impacts of quantum mechanics. We have discovered that the theory of information transmission changes substantially when information is transmitted over quantum channels rather than classical ones, as well as the existence of cryptographic protocols that use quantum information to perform tasks that are impossible classically.
I will discuss the factoring of primes and survey other discoveries in quantum computing—and offer recollections of my role in them.