Quantum computers are proposed devices that would exploit quantum mechanics to solve certain specific problems dramatically faster than we know how to solve them with today's computers. In the popular press, quantum computers are often presented not just as an exciting frontier of science and technology (which they are), but also as magic devices that would work by simply trying every possible solution in parallel. 

However, research over the past 25 years has revealed that the truth is much more subtle and problem-dependent. For some types of problems, quantum computers would offer only modest speedups or none at all. 

These limitations are entirely separate from the practical difficulties of building quantum computers (such as "decoherence") and apply even to the fully error-corrected quantum computers we hope will be built in the future. 

In this talk, Scott Aaronson will  give a crash course on what computer science has learned about the capabilities and limitations of quantum computers. Then he will describe a remarkable and unexpected connection, made just within the past five years, where the conjectured limitations of quantum computers have been applied to problems in fundamental physics. 

These include Hawking's black-hole information puzzle (in its modern incarnation as the "firewall paradox"), as well as the growth of wormholes in the so-called gauge/gravity duality that emerged from string theory.

About the Speaker  

Scott Aaronson is the David J. Bruton Centennial Professor of Computer Science at the University of Texas (UT), Austin. 

He received his bachelor's degree from Cornell University and his Ph.D. from the University of California, Berkeley. He did postdoctoral fellowships at the Institute for Advanced Study and the University of Waterloo. 

Before joining UT Austin, Aaronson spent nine years as a professor of electrical engineering and computer science at Massachusetts Institute of Technology (MIT).

Aaronson's research in theoretical computer science has focused on the capabilities and limits of quantum computers. His first book, "Quantum Computing Since Democritus," was published in 2013 by Cambridge University Press. 

He is the recipient of the National Science Foundation’s Alan T. Waterman Award, the United States PECASE Award, the Vannevar Bush Fellowship, and MIT's Junior Bose Award for Excellence in Teaching.

Editor's Note: This event was first announced by the Georgia Tech Algorithms and Randomness Center (ARC). For updates, check the original posting.