Paul Bernays Lectures 2019
The 2019 Paul Bernays Lectures on the topic "Quantum computing and the fundamental limits of computation " were delivered by Professor Scott Aaronson.
Scott Aaronson, University of Texas at Austin, USA
Scott Joel Aaronson is an American theoretical computer scientist. He is David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin and the founding director of UT Austin's new Quantum Information Center. His primary areas of research are quantum computing and computational complexity theory.
Portrait on ETH News: Quantum computers and the future of computation
Video recordings
The recordings of all lectures are available on the ETH video portal.
Quantum computing and the fundamental limits of computation
Lecture 1: The Church-Turing thesis and physics
Monday, 2 September 2019, 5.00 p.m.
Abstract
Is nature computable? What should we even mean in formulating such a question? For generations, the identification of "computable" with "computable by a Turing machine" has been seen as either an arbitrary mathematical definition, or a philosophical or psychological claim. The rise of quantum computing and information, however, has brought a fruitful new way to look at the Church-Turing Thesis: namely, as a falsifiable empirical claim about the physical universe. This talk seeks to examine the computability of the laws of physics from a modern standpoint -- one that fully incorporates the insights of quantum mechanics, quantum field theory, quantum gravity, and cosmology. We'll critically assess 'hypercomputing' proposals involving (for example) relativistic time dilation, black holes, closed timelike curves, and exotic cosmologies, and will make a 21st-century case for the physical Church-Turing Thesis.
Lecture 2: The limits of efficient computation
Tuesday, 3 September 2019, 9.00 a.m.
Abstract
Computer scientists care about what's computable not only in principle, but within the resource constraints of the physical universe. Closely related, which types of problems are solvable using a number of steps that scales reasonably (say, polynomially) with the problem size? This lecture will examine whether the notorious NP-complete problems, like the Traveling Salesman Problem, are efficiently solvable using the resources of the physical world. We'll start with P=?NP problem of classical computer science -- its meaning, history, and current status. We'll then discuss quantum computers: how they work, how they can sometimes yield exponential speedups over classical computers, and why many believe that not even they will do so for the NP-complete problems. Finally, we'll critically assess proposals that would use exotic physics to go even beyond quantum computers, in terms of what they would render computable in polynomial time.
Lecture 3: The quest for quantum computational supremacy
Tuesday, 3 September 2019, 10.00 a.m.
Abstract
Can useful quantum computers be built in our world? This talk will discuss the current status of the large efforts currently underway at Google, IBM, and many other places to build noisy quantum devices, with 50-100 qubits, that can clearly outperform classical computers at least on some specialized tasks -- a milestone that's been given the unfortunate name of "quantum supremacy." We'll survey recent theoretical work (on BosonSampling, random circuit sampling, and more) that aims to tell us: which problems should we give these devices, that we're as confident as possible are hard for classical computers? And how should we check whether the devices indeed solved them? We'll end by discussing a new protocol, for generating certified random bits, that can be implemented almost as soon as quantum supremacy itself is achieved, and which might therefore become the firstapplication of quantum computing to be realized.
