COMPUTER SCIENCE DEPARTMENT COLLOQUIUM SERIES PRESENTS
“The Ultimate Power of Physically Realizable Computation “
University of Maryland and the National Institute of Standards and Technology
In the popular imagination quantum computers are amazingly powerful– capable of solving hard optimization problems instantaneously by “trying all possible solutions in quantum superposition”. Reality, as might be expected, conveys a more subtle, but equally exciting picture. Although we have no evidence that quantum computers can solve NP-hard problems efficiently, Shor’s revolutionary quantum factoring algorithm demonstrates that quantum computers can break the core primitive behind currently implemented public-key cryptography schemes. This surprising power, combined with breathtaking recent advances in the experimental control of quantum systems, has profoundly challenged the most basic principles of computation. In the wake of these advances, quantum computation has become incredibly relevant both practically, in understanding the future of cryptography, and theoretically, in understanding foundational aspects of computational complexity theory. In this talk, we give an overview of the latest results toward characterizing the power and limitations of quantum computers. Our focus will be not only on understanding the power of quantum computers of the indefinite future but also on the desire to rigorously analyze the power of present-day existing quantum devices which are not yet fully scalable quantum computers. No prior background in computational complexity or quantum mechanics will be assumed.
Bill Fefferman is currently a postdoctoral researcher at QuICS, the joint center for quantum information and computer science at the University of Maryland and the National Institute of Standards and Technology. Before that, he defended his PhD in Computer Science under Alexei Kitaev and Christopher Umans at the California Institute of Technology. His research interests concern understanding computational complexity theory and cryptography in a fundamentally quantum mechanical world.
Date: Friday, February 17th, 2017
Time: 11:00am to 12:00pm
Location: ECS South 2.410
Refreshments will be served at 10:45am