Algorithms & Randomness Center (ARC)
Scott Aaronson (UT Austin)
Monday, December 4, 2017
Klaus 1116 East & West - 11:00 am
Title: Black Holes, Firewalls, and the Limits of Quantum Computers
Abstract: 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 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 no speedups 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, I'll give a crash course on what computer science has learned about both the capabilities and the limitations of quantum computers. Then, in a final section, I'll describe a remarkable and unexpected connection -- made just within the last five years -- where the conjectured limitations of quantum computers have been applied to issues in fundamental physics. These include Hawking's black-hole information puzzle (in its modern incarnation as the "firewall paradox"), and understanding the growth of wormholes in the so-called gauge/gravity duality that emerged from string theory.
Bio: Scott Aaronson is David J. Bruton Centennial Professor of Computer Science at the University of Texas at Austin. He received his bachelor's from Cornell University and his PhD from UC Berkeley, and did postdoctoral fellowships at the Institute for Advanced Study as well as the University of Waterloo. Before coming to UT Austin, he spent nine years as a professor in Electrical Engineering and Computer Science at MIT. Aaronson's research in theoretical computer science has focused mainly on the capabilities and limits of quantum computers. His first book, Quantum Computing Since Democritus, was published in 2013 by Cambridge University Press. He’s received 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.
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836