The success of the abstract model of classical computation in terms of bits, logical operations, algorithms, and programming language constructs makes it easy to forget that computation is a physical process. Our cherished notions of computation and information are grounded in classical mechanics, but the physics of our universe is quantum. A natural question to ask is how computation would change if we adopted a quantum mechanical, instead of a classical mechanical, model of computation.

In the early 80s, Richard Feynman, Yuri Manin, and others recognized that certain quantum effect could not be simulated efficiently on conventional computers. This observation led researchers to speculate that some difficult computational problems could be solved efficiently using these hard-to-simulate quantum effects. Slowly, a new picture of computation arose, one that gave rise to a variety of faster algorithms, novel cryptographic mechanisms, and alternative methods of communication.

In the first part of the talk, we will introduce key concepts underlying quantum computing and describe alternative quantum computational models. In the second half of the talk, we will discuss applications of quantum computing, known advantages and limitations, and briefly touch on the current state-of-the-art in building quantum computers, quantum error correction, and fault tolerance, and the many open research questions that remain.

Support for the Stanford Colloquium on Computer Systems Seminar Series provided by the Stanford Computer Forum. Speaker Abstract and Bio can be found here: http://web.stanford.edu/class/ee380/A...