Abstract: The success of the abstract model of 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 perhaps such quantum effect could be used to speed up computation more generally. 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. 

 

For most computational problems, however, it is currently unknown whether quantum algorithms can provide an advantage, and if so by how much, or how to design quantum algorithms that realize such advantages. Many of the most challenging computational problems arising in the practical world are tackled today by heuristic algorithms that have not been mathematically proven to outperform other approaches but have been shown to be effective empirically. While quantum heuristic algorithms have been proposed, empirical testing becomes possible only as quantum computation hardware is built. The next decade promises to be exciting emerging hardware makes  empirical testing of quantum heuristic algorithms more and more feasible.

 

In the first part of the talk, I will introduce key concepts underlying quantum computing and correct common misconceptions. In the second half of the talk, I will discuss applications of quantum computing, known advantages and limitations, including work at NASA on quantum heuristics. I will 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.