Quantum Computing and the Limits of the Efficiently Computable

From International Center for Computational Logic

Quantum Computing and the Limits of the Efficiently Computable

Talk by Scott Aaronson
I'll offer a crash course on quantum computing, which seeks to exploit the strange rules of quantum physics to solve certain problems dramatically faster than we know how to solve them with any existing computer. I promise no hype: just a a sober summary of how a quantum computer would actually work (hint: it's not just by "trying every possible answer in parallel"), for which problems quantum computers are and aren't expected to provide an advantage, and the current status of the effort to make quantum computing practical. I'll also say something about the ultimate physical limits of computation, and about speculative proposals for going beyond even quantum computers.


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.