Colloquium: Scott Aaronson, Assistant Professor of Electrical Engineering and Computer Science

In the popular imagination, quantum computers would be almost magical devices, able to "solve impossible problems in an instant" by trying exponentially many solutions in parallel.  In this talk, I'll describe various results in quantum computing theory that directly challenge this view.  For example, at least in the "black-box model" that we know how to analyze, quantum computers would need exponential time to break cryptographic hash functions or find local optima, just as classical computers would.  As time permits, I'll also describe how studying the limitations of quantum computers can lead to new insights even into classical computation.