Talk by Scott Aaronson, 2015

Quantum Computing and the Limits of the Efficiently Computable

This talk will discuss how computational complexity---the study of what can and can't be feasibly computed ---has been interacting with physics in interesting and unexpected ways. This will include a crash course about computer science's P vs. NP problem, as well as about the capabilities and limits of quantum computers. It will also include critical discussion of speculative models of computation that would go even beyond quantum computers, using (for example) special relativity and time travel to the past.

About the speaker

Scott Aaronson is a theoretical computer scientist and an Associate Professor of the Electrical Engineering and Computer Science Department of the Massachusetts Institute of Technology. His research interests centre around the capabilities and limits of quantum computers, and more generally, on computational complexity theory.

This event is organised by the Centre for Quantum Technologies, National University of Singapore in partnership with the Science Centre Singapore.